Eventual Leader Election in Infinite Arrival Message-Passing System Model with Bounded Concurrency
Sara Tucci-Piergiovanni, Roberto Baldoni · 2010
We study the failure detection problem in a message-passing system that may dynamically change over time, so that the number of processes which make progress during a computation may grow to infinity as time tends to infinity but the number of concurrently up processes do not exceed a known bound. We first propose the specification of a new oracle, called HB*, able to give hints on which processes are making progress in the system. A possible HB* implementation is given. Then, we show how to use HB* to implement the oracle Ω that eventually identifies a unique leader in the system. To the best of our knowledge this is the first implementation of Ω running in a message passing system with infinitely many processes.