Just Enough Synchrony for Message Passing k-Set Agreement
Martin Biely, Peter Robinson, Ulrich Schmid · 2009
This report presents necessary and sufficient conditions for solving the k-set agreement problem in message passing systems. To this end, we in-troduce two weak communication predicates Psrcs(k) and Pmov-dom(k) for round-based message passing systems using the Heard-Of (HO) Model by Charron-Bost and Schiper, and present and prove correct a novel algorithm that solves k-set agreement in a system where Psrcs(k) holds. The algorithm works by approximating a synchrony graph, which is defined by the timely links between processes. In addition, we show that Psrcs(k) is tight, in the sense that there is no algorithm for (k−1)-set agreement with Psrcs(k). Fur-thermore, we prove that any HO predicate that allows to solve k-set agree-ment is at least as strong as Pmov-dom(k), which itself is sufficient for solving k-set agreement. Finally, we show that Psrcs(k) naturally corresponds to a new class of partially synchronous modelsM2-source(k) with weak timely link assumptions.