Conditions for Set Agreement with an Application to Synchronous Systems

The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. While this problem cannot be solved in an asynchronous system prone to t process crashes when t ≥ k, it can always be solved in a synchronous system; is then a lower bound on the number of rounds (consecutive communication steps) for the non-faulty processes to decide. The condition-based approach has been introduced in the consensus context. Its aim was to both circumvent the consensus impossibility in asynchronous systems, and allow for more efficient consensus algorithms in synchronous systems. This paper addresses the condition-based approach in the context of the k-set agreement problem. It has two main contributions. The first is the definition of a framework that allows defining conditions suited to the k-set agreement problem and the second is a generic synchronous k-set agreement algorithm based on conditions. This work was supported by the European Network of Excellence ReSIST. A previous version of this paper has appeared in the Proceedings of the 28th IEEE Int. Conference on Distributed Computing Systems (ICDCS'08), June 2008.