A modular technique for the design of efficient distributed leader finding algorithms
Explore this paper's citation graph
Summary
A general, modular technique for designing efficient leader finding algorithms in distributed, asynchronous networks is developed, and in some cases the message complexity of the resulting algorithms is better by a constant factor than that of previously known algorithms.
- Type
- article
- Published
- 1990-01-03
- Cited by
- 115
- References
- 32
- Access
- Open access
- OpenAlex
- https://openalex.org/W2024606983
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:9175968
Keywords
Computer science, Algorithm, Node (physics), Traverse, Time complexity
References
- An O(n log n) Unidirectional Distributed Algorithm for Extrema Finding in a Circle
- Time and message bounds for election in synchronous and asynchronous complete networks
- The impact of synchronous communication on the problem of electing a leader in a ring
- Lower Bounds for Distributed Maximum-Finding Algorithms
- An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem
- Distributed elections in an archimedean ring of processors
- Distributed algorithms for finding centers and medians in networks
- Distributed network protocols
- Election and traversal in unidirectional networks
- Matching, Euler tours and the Chinese postman
- Selecting a leader in a clique in 0(N log N) messages
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A Fully Distributed (Minimal) Spanning Tree Algorithm
- Tight lower and upper bounds for some distributed algorithms for a complete network of processors
- A compositional approach to superimposition
- Decentralized Extrema- Finding in Circular Configurations of Processors
- Graph Algorithms
- Computer networks
- Distributed Algorithms on Graphs
- On Composition
Cited by
- Faults and fault-tolerance in distributed computing systems: the election problem
- Selecting and commanding groups of robots using a Vision-based natural user interface
- Distributed Random Walks and the Design of a Self-Stabilizing Random Spanning Tree
- Easy and Hard Testbeds for Real-Time Search Algorithms
- Uniform self-stabilizing leader election, 1: Complete graph protocols
- Design and analysis of distributed algorithms
- RFDMon: A Real-time and Fault-tolerant Distributed System Monitoring Approach
- Bounded model checking for asynchronous concurrent systems
- Hybrid Algorithms for On-Line Search and Combinatorial Optimization Problems
- Rendezvous of Agents with Different Speeds
- Minuet: Rethinking Concurrency Control in Storage Area Networks
- Sense of direction in distributed computing
- On the impact of sense of direction in arbitrary networks
- Systematic Cooperation in P2P Grids
- Fast rendezvous on a cycle by agents with different speeds
- Efficient deadlock-free routing
- Clustering of wireless sensor and actor networks based on sensor distribution and connectivity
- Graph learning with a nearest neighbor approach
- Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
- Electing a Leader in Wireless Networks Quickly Despite Jamming
Related papers
- A Tight Bound for Set Disjointness in the Message-Passing Model
- An Asynchronous Message-Passing Distributed Algorithm for the Global Critical Section Problem
- Gossip-Based Aggregate Computation with Low Communication Overhead
- Distributed MIS with Low Energy and Time Complexities
- Consensus with Bounded Space and Minimal Communication
- Multiparty Communication Complexity and Threshold Circuit Size of AC^0
- Inner Product and Set Disjointness: Beyond Logarithmically Many Parties.