Communication and time complexity of a distributed election protocol

we evaluate several variants of a standard election algorithm on a ring of processors. The performance measures of interest are the number of messages exchanged (communication complexity) and the execution time (time complexity). Classical models use a synchronism assumption according to which all processors start at the same time and message delays are constant.We attempt to capture the essential asynchronism of this class of algorithms by using probabilistic models. Two such models are discussed, one in discrete and one in continuous time. In each case, both the uni- and the bidirectional cases are studied and compared. We obtain expressions for the distributions of the number of exchanged messages and derive their asymptotic behavior whenn, the number of processors in the ring, grows large. The results show how the communication complexity actually depends on the speed of communcations on the ring, and what is the interest of having bidirectional communications.We also address in part the evaluation of the completion time of the algorithm. This time decomposes into astartup time and anexploration time. We show that the average of the startup time is of the order of logn.