Failure detectors in homonymous distributed systems (with an application to consensus)

• This paper presents Failure Detectors for Homonymous Systems (FDHS).
• Implementations of FDHS are introduced here.
• Two realistic implementations of consensus with FDHS are presented.

This paper is on homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership (“homonymous” means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes HΩHΩ and HΣHΣ are introduced that are the homonymous counterparts of the classes ΩΩ and ΣΣ, respectively. (Recall that the pair 〈Ω,Σ〉〈Ω,Σ〉 defines the weakest failure detector to solve consensus.) Then, the paper shows how HΩHΩ and HΣHΣ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with 〈HΩ,HΣ〉〈HΩ,HΣ〉, while the other uses only HΩHΩ, but needs a majority of correct processes.Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class HΩHΩ can be implemented with partial synchrony (i.e., all messages sent after some bounded time GSTGST will be received after at most an unknown bounded latency δδ), while the analogous class AΩAΩ defined for anonymous systems cannot be implemented (even in synchronous systems). Hence, the paper provides the first consensus algorithm for anonymous systems with this model of partial synchrony and a majority of correct processes.