a hierarchy of conditions for consensus solvability
In a previous paper we introduced the condition-based approach, consisting of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes, and characterized this set of conditions, @@@@ wk f . Here, we investigate @@@@ wk f from the complexity perspective, and show that this class consists of a hierarchy of classes of conditions, @@@@ [ d ] f , where d , 0 &lne; d &lne; f , is the degree of the condition, each one strictly contained in the previous one. The value f - d represents the  difficulty  of the class @@@@ [ d ] f : we present a generic condition-based protocol that can be instantiated with any C ? @@@@ [ d ] f , and solve consensus with (2 n + 1) [log 2 ([( f - d )/2] + 1)] shared memory read/write operations per process. For each d we present two natural conditions, C 1 [ d ] f and C 2 [ d ] f , that might be useful in practice, and we use them to show that the class containments stated above are strict. Various properties of the hierarchy are also derived. Mainly, it is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties.
consensus snapshot fault-tolerance asynchronous shared memory step complexity