Optimal lower bounds for some distributed algorithms for a complete network of processors

DOI10.1016/0304-3975(89)90103-5zbMath0681.68067OpenAlexW2091422818MaRDI QIDQ1823691

Shlomo Moran, Ephraim Korach, Shmuel Zaks

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90103-5

zbMATH Keywords

lower boundsdistributed algorithmsprocessorscomplete network ofleader election problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)

Related Items (17)

Labeled versus unlabeled distributed Cayley networks ⋮ Improved deterministic leader election in diameter-two networks ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Efficient leader election using sense of direction ⋮ Hundreds of impossibility results for distributed computing ⋮ Sublinear bounds for randomized leader election ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ Tight bounds on the round complexity of distributed 1-solvable tasks ⋮ Wang tilings and distributed verification on anonymous torus networks ⋮ The complexity of leader election in diameter-two networks ⋮ Move-optimal gossiping among mobile agents ⋮ Communication algorithms with advice ⋮ The power of multimedia: Combining point-to-point and multi-access networks ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ On the Complexity of Universal Leader Election

Cites Work

• On the message complexity of distributed problems
• Electing a leader in a synchronous ring
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• A Distributed Algorithm for Minimum-Weight Spanning Trees

This page was built for publication: Optimal lower bounds for some distributed algorithms for a complete network of processors