The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity

This paper 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 non-anonymous system, the classes "psi" and P -the class of perfect failure detectors- are equivalent). The paper 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 paper presents and proves correct an early-deciding algorithm where the processes decide in min(2f+2,2t+1) asynchronous rounds (where f is the actual number of process failures). This leads to think that anonymity doubles the cost (wrt synchronous systems) and it is conjectured that min(2f+2,2t+1) is the corresponding lower bound. The paper 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 2 (t div k}+1 asynchronous rounds. Then, considering a family of failure detector classes "psi(ell)" that generalizes the class "psi". the paper presents an algorithm that solves the k-set agreement in 2 \(t div k-ell+1) +1 asynchronous rounds. This last formula relates the cost (R(t,ell), the coordination degree of the problem (k), the maximum number of failures (t) and the the strength (ell) of the underlying failure detector. Finally the paper concludes by presenting problems that remain open