Agreement and consistency without knowing the number of processes

Reviewer: Bruce E. Litow

This paper investigates three classical problems in distributed computation-leader election, atomic registers, and consensus-under carefully defined assumptions about synchrony/asynchrony and knowledge about the number of processes. Before proceeding with the review of this interesting paper, I should point out that apart from its abstract and algorithms that are in English, the text of the paper is in French. The paper considers the possibility of each of these three classical distributed computations, when the number of processors is unknown but each process has a unique ID. The authors consider three things: (1)Synchronous systems, where a central source that synchronizes process clocks and communication is synchronous (carried out in rounds with an upper bound on message delay). (2)Partially synchronous systems, where the central clock exists but communication is asynchronous. (3)Asynchronous systems, where no assumption other than ultimate delivery of a message is made; this assumption can be changed if faults are admitted. The authors derive possibility/impossibility results for all cases, also allowing or disallowing faults. The results are summarized in Table 1. A notion of reducibility is given. The idea of a detector is introduced, where a detector has as output a set of process IDs. A detector Y is weaker than a detector ω if every output of ω can be transformed into an output of Y . The authors do not specify details of the transformation, but it appears to amount to simple reinterpretation. This notion of reducibility is applied to two detectors, O and S . O has an output that is the ID of a single process. This output is invariable and is known to all processes. In effect, O elects a leader. S is fault detection by quorum, where two quorums, at distinct times, have a nonempty intersection and, at some time, the corresponding quorum contains the ID of a faulty process. It is shown that for the asynchronous case, S is the weakest detector, enabling realization of atomic registers, and O×S (ordered pair of IDs as output) is the weakest detector, enabling realization of consensus. Online Computing Reviews Service