Some Optimal Algorithms for Decomposed Partially Ordered Sets

We describe two problems and their optimal solutions for partially ordered sets. We first describe an optimal algorithm for computing the largest anti-chain of a partially ordered set given its decomposition into its chains. Our algorithm requires O(n 2 m) comparisons where n is the number of chains and m is the maximum number of elements in any chain. We also give an adversary argument to prove that this is a lower bound. Our second problem requires us to find if the given poset is a total order. Our optimal algorithm requires O(mn log n) comparisons. These algorithms have applications in distributed debugging and recovery in distributed systems. Keywords: Partially-ordered sets, Distributed debugging 1. Introduction Let (S; !) be any partially ordered finite set. We are given a decomposition of S into n sets P 0 ; :::P n\Gamma1 such that for any i, P i is a chain of size at most m. We call such a structure a decomposed poset. These structures arise in distributed systems, becau..