Optimal Message-Driven Implementation of Omega with Mute Processes

摘要

We consider the complexity of algorithms in message-driven models, i.e., models of distributed computations where events can only be caused by message receptions but not by the passage of time. Hutle and Widder (2005) have shown that there is no self-stabilizing implementation of the eventually strong failure detector, and thus the eventual leader oracle Ω in such models under certain assumptions. Under stronger assumptions it was shown that even the eventually perfect failure detector can be implemented in systems consisting of at least f + 2 processes — f being the upper bound on the number of processes that crash during an execution. In this paper we show that f + 2 is in fact a lower bound in message-driven systems, even if non stabilizing algorithms are considered. This contrasts time-driven models where f + 1 is sufficient for failure detector implementations. After that, we provide an efficient message-driven implementation of Ω. Our algorithm is efficient in the sense that not all processes have to send messages forever, which is an improvement to previous message-driven failure detector implementations.