An infection algorithm for leader election: Experimental results for a chain

A variant of the population protocol model is used in [1] to describe a probabilistic algorithm for leader election (choosing one of the agents to have special authority) in a collection of autonomous numbered agents, with only simple, pairwise interactions allowed between them. Earlier results have shown that leader election for a collection of numbered agents can be accomplished via a probabilistic infection algorithm. The algorithm uses no external or global timers to decide when the election is completed. Here we consider agents distributed through different locations in space. We consider agents as being located on various nodes of a graph and allow only those agents at the same node of the graph to interact. Experimental results using various sizes of chain graph [2] illustrate that the probabilistic algorithm presented in [1], [3] can be successfully applied in this generalized setting.