A SIMPLE, EFFICIENT ALGORITHM FOR MAXIMUM FINDING ON RINGS

Abstract

The maximum finding problem is: given a network of processors with distinct identifiers, find that processor with the maximum identifier. We present a new deterministic algorithm for maximum finding on asynchronous undirectional rings. To date the maximum finding algorithm with the best message complexity uses at most 1.356\fIn log n + O(n)\fR messages in the worst case. This algorithm is somewhat involved and its analysis is quite complicated. Our algorithm is simple, has a very much simpler analysis and achieves a lower worst case message complexity (less than 1.271\fIn log n + O(n)\fR messages). An additional contribution of this paper is a new perspective on this problem that exhibits its structure thus permitting a better understanding of various message saving mechanisms.