Condition-Based Protocols for Set Agreement Problems

摘要

A condition C is a set of input vectors to a problem. A class of conditions that allow to solve κ-set agreement in spite of f crashes in an asynchronous system is identified. A κ-set agreement protocol that is always safe is described: it is guaranteed to terminate when the input vector belongs to C and it always decides on at most k different values, even if the input vector does not belong to C. While there are simple so-lutions when f < κ, it is known that the fc-set agreement problem has no solution when f ≥κ. Thus, the paper identifies classes of conditions that allow to solve this problem even when f ≥κ. The paper gives evidence that these are the only conditions that allow to solve set agreement, by proving the wait-free case. Two natural concrete conditions that belong to such a class are described. Finally, a more efficient κ-set agreement protocol with only linear complexity (does not use snapshots), for any C that allows to solve consensus, when κ ≤ f/(n ― f) + 1 is presented. This shows how to trade fault-tolerance for agreement precision using the condition based approach.