Average Case Behavior of Distributed Extrema-Finding Algorithms
Paul Everhardt · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1984
Much work has been done on the problem of circular extrema-finding on a unidirectional ring of dis tributed processors.The solution proposed by Peterson requires 0(nlog2n) messages to elect the leader.Peterson's algorithm may be improved by incorporating modifications suggested by Dolev, Klawe and Rodeh.This modified algorithm is simplified and described explicitly for the first time.Both the original and the modified algorithm are examined for their average case behavior.It is found that, for large n, the average number of messages required is .94nlog2n.