Anonymous Asynchronous Systems: Failure Detectors and Consensus

Due the multiplicity of loci of control, a main issue distributed systems have to cope with lies in the uncertainty on the system state created by the adversaries that are asynchrony, failures, dynamicity, mobility, etc. Considering message-passing systems, this talk studies the uncertainty created by the net effect of three of these adversaries, namely, asynchrony, failures, and anonymity. This means that, in addition to be asynchronous and crash-prone, the processes have no identity. Trivially, agreement problems (e.g., consensus) that cannot be solved in presence of asynchrony and failures cannot be solved either when adding anonymity. The talk consequently presents anonymous failure detectors (FD) to circumvent these impossibilities. The talk proposes mainly the three following contributions:

1. The definition of anonymous failure detectors. These new FDs are (non-trivially) equivalent to their non-anonymous counterparts in non-anonymous systems.
2. The price of anonymity. Any anonymous consensus algorithm requires twice as many messages as non-anonymous algorithms.
3. The hierarchy of failure detectors. FDs can be ranked depending on their computational power (which problems they allow to solve). In the context of anonymous systems, new interesting problems appear.