There are many interesting applications of partial order theory in distributed and parallel systems. These include testing and monitoring the concurrent behavior of the system. The optimal chain partition and width of a partially ordered set (poset for short) play a key role in the analysis of a distributed computation when the trace is modeled as such. In this paper, we discuss the decision problem of testing the width of a poset, and finding the optimal chain partition in an online manner.
We present an O(wsn) online algorithm for finding the optimal chain partition, where w is the width, n the number of elements, and s the number of {\itshape relevant elements} defined in section 4. We implement two of the previously known chain reduction algorithms in both online and offline manner. In particular, we compare the experimental performance of our online optimal chain partition algorithm with the offline ones and show that our algorithm performs better when the input poset has small width.