Faults and fault-tolerance in distributed computing systems: the election problem
Explore this paper's citation graph
Summary
This dissertation examines some issues concerning fault tolerance in distributed computing systems using the election problem as a test bed and shows that a good lower bound is most useful in designing algorithms with good worst-case message complexity.
- Type
- article
- Published
- 1994-01-01
- Cited by
- 1
- References
- 37
- OpenAlex
- https://openalex.org/W44501767
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:59733477
Keywords
Upper and lower bounds, Leader election, Computer science, Fault tolerance, Asynchronous communication
References
- Distributed Systems - Towards a Formal Approach
- Message complexity of simple ring-based election algorithms-an empirical analysis
- An O(n log n) Unidirectional Distributed Algorithm for Extrema Finding in a Circle
- Sense of direction, topological awareness and communication complexity
- Time and message bounds for election in synchronous and asynchronous complete networks
- Average Number of Messages for Distributed Leader-Finding in Rings of Processors
- Fault-Tolerant Distributed Algorithms for Agreement and Election
- The impact of synchronous communication on the problem of electing a leader in a ring
- An improved algorithm for decentralized extrema-finding in circular configurations of processes
- Lower Bounds for Distributed Maximum-Finding Algorithms
- Analysis of a Distributed Algorithm for Extrema Finding in a Ring
- An Efficient Algorithm for Byzantine Agreement without Authentication
- An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem
- A modular technique for the design of efficient distributed leader finding algorithms
- Detecting global termination conditions in the face of uncertainty
- Authenticated Algorithms for Byzantine Agreement
- Impossibility of distributed consensus with one faulty process
- The effects of link failures on computations in asynchronous rings
- Symmetry breaking in distributed networks
- Elections in a Distributed Computing System
Cited by
Related papers
- The Do-All problem with Byzantine processor failures
- Bounds on Fundamental Problems in Parallel and Distributed Computation
- Some communication complexity issues in asynchronous algorithms
- Lower bounds for asynchronous consensus
- Message Lower Bounds via Efficient Network Synchronization
- Soft real-time analysis of asynchronous agreement algorithms using Petri nets
- A Crash-tolerant Consensus Algorithm in Presence of Probabilistic Message Omission
- Reaching approximate agreement with multiple fault-modes