We show the relationship between the number of messages and timenfor leader election in general networks. Specifically, the paper provesnthat every O(D)1 time algorithm for leader election inngeneral networks requires Ω(m log D) messages. We show that thisnlower bound is tight by presenting a simple O(m log D) messagencomplexity and O(D) time distributed algorithm for leader election inngeneral networks. Finally, B. Awerbuch (1987) presented an O(m+n log n)nmessage and O(n) time distributed algorithm for leader election inngeneral networks, which is optimal for the number of messages. Wenpresent another algorithm that matches Awerbuch's complexities, but ournalgorithm is simpler than Awerbuch's algorithm
展开▼
