Equitable probabilistic elections in ring networks

A probabilistic algorithm for leader election in ring networks is described and analyzed. The election is based on comparison of random priority numbers drawn independently by each station from a globally defined finite integer range, with ties resolved by additional election rounds, and with all stations having equal chances of being elected. The algorithm is shown to be partially correct and to terminate with probability 1. The main result of the paper is an explicit formula for the probability distribution of election time (i.e., the number of rounds). It is also shown that all moments of the distribution exist. A distinctive feature of the underlying ring model is the assumption that each receiving station can distinguish its own messages from those of others, but that the stations are otherwise indistinguishable and use no global information. This assumption is motivated by a reliability argument based on reconfigurable local area netwroks of ring topology.