A SIMPLE, EFFICIENT ALGORITHM FOR MAXIMUM FINDING ON RINGS
Date
1992-12-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science