Fault-tolerant consensus with an abstract MAC layer
From MaRDI portal
Publication:5090931
DOI10.4230/LIPICS.DISC.2018.38zbMATH Open1497.68048arXiv1810.02848OpenAlexW2894815634MaRDI QIDQ5090931FDOQ5090931
Authors:
Publication date: 21 July 2022
Abstract: In this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract MAC layer model, which captures the basic interface and communication guarantees provided by most wireless MAC layers. Our algorithms work for any number of failures, require no advance knowledge of the network participants or network size, and guarantee termination with high probability after a number of broadcasts that are polynomial in the network size. Our first algorithm satisfies the standard agreement property, while our second trades a faster termination guarantee in exchange for a looser agreement property in which most nodes agree on the same value. These are the first known fault-tolerant consensus algorithms for this model. In addition to our main upper bound results, we explore the gap between the abstract MAC layer and the standard asynchronous message passing model by proving fault-tolerant consensus is impossible in the latter in the absence of information regarding the network participants, even if we assume no faults, allow randomized solutions, and provide the algorithm a constant-factor approximation of the network size.
Full work available at URL: https://arxiv.org/abs/1810.02848
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Unreliable failure detectors for reliable distributed systems
- Maximal independent sets in multichannel radio networks
- \textsc{Maximal Independent Sets} in radio networks
- Impossibility of distributed consensus with one faulty process
- Early consensus in an asynchronous system with a weak failure detector
- Broadcasting algorithms in radio networks with unknown topology
- Broadcasting in undirected ad hoc radio networks
- Faster communication in known topology radio networks
- Analysis 2.
- Anonymous asynchronous systems: the case of failure detectors
- Computing in totally anonymous asynchronous shared memory systems
- Failure detection and consensus in the crash-recovery model
- Distributed agreement in dynamic peer-to-peer networks
- Polylog randomized wait-free consensus
- Fault Tolerance in Networks of Bounded Degree
- The price of being near-sighted
- Title not available (Why is that?)
- The Abstract MAC Layer
- The abstract MAC layer
- Distributed deterministic broadcasting in wireless networks of weak devices
- Efficient and modular consensus-free reconfiguration for fault-tolerant storage
- Scalable leader election
- Fast deterministic consensus in a noisy environment
- The part-time parliament
- Wireless connectivity and capacity
- Consensus with an abstract MAC layer
Cited In (5)
- An efficient communication abstraction for dense wireless networks
- Recent results on fault-tolerant consensus in message-passing networks
- Consensus with an abstract MAC layer
- Randomization can be a healer: consensus with dynamic omission failures
- Consensus and collision detectors in wireless ad hoc networks
This page was built for publication: Fault-tolerant consensus with an abstract MAC layer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090931)
