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 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 is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with d = min(n-f,f) and ending with d = 0, where C_f~[0]. We prove that each one is strictly contained in the previous one: C_f~[d] is contained in C_f~[d-1]. 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 ∈ C_f~[d], and requires at most 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 C_f~[d] . An improvement of the protocol for the conditions in is also presented.