Brief Announcement: Leader Election in the ADD Communication Model

摘要

A channel from a process p to a process q satisfies the ADD property if there are two constants K and D, unknown to the processes, such that in any sequence of K consecutive messages sent by a process p to a process q, at least one of them is delivered to q at most D time units after it has been sent. This paper studies implementations of an eventual leader, namely an Ω failure detector, in a (not necessarily complete) connected network of eventual ADD channels, where processes may fail by crashing. It presents an algorithm that assumes that the processes initially know n, the total number of processes, sending messages of size O(log n).