The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash, and Anonymity
This article addresses the consensus problem in asynchronous systems prone to process crashes, where additionally the processes are anonymous (they cannot be distinguished one from the other: they have no name and execute the same code). To circumvent the three computational adversaries (asynchrony, failures, and anonymity) each process is provided with a failure detector of a class denoted psi, that gives it an upper bound on the number of processes that are currently alive (in a nonanonymous system, the classes psi and P-the class of perfect failure detectors-are equivalent). The article first presents a simple psi-based consensus algorithm where the processes decide in 2t + 1 asynchronous rounds (where t is an upper bound on the number of faulty processes). It then shows one of its main results, namely 2t + 1 is a lower bound for consensus in the anonymous systems equipped with psi. The second contribution addresses early-decision. The article presents and proves correct an early-deciding algorithm where the processes decide in min(2 f + 2, 2t + 1) asynchronous rounds (where f is the actual number of process failures). This leads us to think that anonymity doubles the cost (with respect to synchronous systems) and it is conjectured that min(2 f + 2, 2t + 1) is the corresponding lower bound. The article finally considers the k-set agreement problem in anonymous systems. It first shows that the previous psi-based consensus algorithm solves the k-set agreement problem in R(t) = 2left perpendiculart/kright perpendicular + 1 asynchronous rounds. Then, considering a family of failure detector classes {psi(l)}0 <= l<k that generalizes the class psi(= psi(0)), the article presents an algorithm that solves the k-set agreement in R(t,l) = 2left perpendiculart/k-lright perpendicular + 1 asynchronous rounds. This last formula relates the cost (R(t,l)), the coordination degree of the problem (k), the maximum number of failures (t), and the the strength (l) of the underlying failure detector. Finally the article concludes by presenting problems that remain open.
anonymity consensus asynchronous systems failure detector algorithms theory message passing system