Browsing by Author "Przytycka, Teresa"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemOpen AccessA SIMPLE, EFFICIENT ALGORITHM FOR MAXIMUM FINDING ON RINGS(1992-12-01) Higham, Lisa; Przytycka, TeresaThe 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.