A leader election protocol for eventually synchronous shared memory systems

While protocols that elect an eventual common leader in asynchonous message-passing systems have been proposed, to our knowledge, no such protocol has been proposed for the shared memory communication model. This paper presents a leader election protocol suited to the shared memory model. In addition to its design simplicity, the proposed protocol has two noteworthy properties, namely, it does not use timers, and is optimal with respect to the number of processes that have to write forever the shared memory: a single process has to do it (namely, the leader that is eventually elected). Among the many possible uses of such a leader protocol, one is Lamport´s Paxos protocol. Paxos is an asynchronous consensus algorithm that relies on an underlying eventual leader abstraction. As recently, several versions of Paxos have been designed for asynchronous shared memory systems (the shared memory being an abstraction of a physically shared memory or a set of commodity disks that can be read and written by the processes), the proposed leader protocol makes Paxos effective in these systems