Condition-based consensus solvability: a hierarchy of conditions and efficient protocols.

The condition-based approach for consensus solvability consists 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. This paper investigates $\mathcal{C}_f$ , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that $\mathcal{C}_f$ is made up of a hierarchy of classes of conditions, $\mathcal{C}^{[d]}_f$ where d is a parameter (called degree of the condition), starting with $d = \min(n-f,\allowbreak f)$ and ending with d = 0, where $\mathcal{C}^{[0]}_f = \mathcal{C}_f$ . We prove that each one is strictly contained in the previous one: $\mathcal{C}^{[d]}_f\subset\mathcal{C}^{[d-1]}_f$ . Various properties of the hierarchy are also derived. 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. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, $C\in\mathcal{C}^{[d]}_f$ , and requires at most $(2n + 1) \lceil{\log_2(\lceil{(f-d)/2\rceil} + 1)}$ shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value ( f- d) represents the ? difficulty? of the class $\mathcal{C}^{[d]}_f$ . An improvement of the protocol for the conditions in $\mathcal{C}^{[0]}_f$ is also presented. [ABSTRACT FROM AUTHOR]