Technical Report CS0327

Title: A Unified Approach to the Construction of Efficient Distributed Leader Finding Algorithms
Authors: Shay Kutten
Abstract: This study discusses an algorithm for finding a leader in certain sets of undirected graphs in O(n*logn) messages. Santoro has shown that in a general graph at least O(|E|+n*logn) messages are needed for finding a leader. However several algorithms which work in O(n* logn) messages for some restricted sets of graphs, do exist. Each of this algorithms specializes in one such set. We introduce here the property all these known "n logn graphs" have in common and suggest one algorithm which achieves O(n logn) messages leader finding in all the known special cases, as well in some new ones. The algorithm is the same for all those cases. The special features of the given case is taken advantage of in a lower layer (servant) protocol which is used to pass the messages (this layering is common in communication networks). As we will see- the constructlon of the lower layer protocol in the known special cases is straightforward. At last we generalize the result for O(f(n) logn) for graphs for which an O(f(n)) auxiliary algorithm (similar to the one we use) can be constructed. Then there exists a distributed leader finding algorithm.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion