Eventual leader election in infinite arrival message-passing system model with bounded concurrency

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. © 2010 IEEE.