An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

Algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner, disprove Hirschberg and Sinclair's conjecture that O ( n 2 ) is a lower bound on the number of messages passed in undirectional algorithms.

Abstract

In this paper we present algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner .We begin with a simple unidirectional algorithm, in which the number of messages passed is bounded by 2n log n + 0(n) .By making several improvements to the simple algorithm, we obtain a unidirectional algorithm in which the number of messages passed is bounded by 1 .5nlogn + 0(n) .These algorithms disprove Hirschberg and Sinclair's'conjecture that 0(n 2 ) is a lower bound on the number of messages passed in undirectional algorithms for this problem .At the end of the paper we indicate how our methods can be used to improve an algorithm due to Peterson, to obtain a unidirectional algorithm using at most 1 .356nlog n + 0(n) messages.This is the best bound so far on the number of messages passed in both the bidirectional and unidirectional cases . . INTRODUCTIONConsider a circular arrangement . of n asynchronous communicating processes in which communication occurs only between neighbors around the circle .All processes have the same program, and differ only by having distinct numbers (known only to the owners) stored in their local (nonshared) memory .Our objective is to obtain an efficient algorithm which finds the maximum of these numbers .Rapid progress has been made on this problem during the last few years.In 1977 LeLann [6] presented an algorithm which requires 0(n 2 ) messages.Chang and Roberts [2] in 1979, proposed an improved algorithm which uses only 0(n log n) messages on the average (assuming that all permutations of the data are equiprobable) ; however, their algorithm still requires 0(n 2 ) messages in the worst case .Also in 1979, Gallager et al. [3] obtained, as part of an O(e + n log n) algorithm for finding a minimum spanning tree in a