François Bonnet will receive the best student paper award at DISC’10 for the paper entitled “Anonymous Asynchronous Systems: the Case of Failure Detectors” (co-authored with Michel Raynal).
This paper proposes the first analysis of the failure detector approach in the context of anonymous systems. Failure detectors are abstractions that allow to capture the additional power required to solve unsolvable distributed problems (like the well-known consensus problem). The paper has three main contributions. First it introduces new “anonymous” failure detectors and then studies their relative power. Interestingly the hierarchies of detectors are different in non-anonymous systems and anonymous systems. The third contribution of the paper is a consensus algorithm, based on two failure detectors, that relies on a new mechanism involving multiple sub-phases.