The time complexity of consensus under oblivious message adversaries

DOI10.1007/S00453-024-01209-4MaRDI QIDQ6547208zbMATH OpenFDO

Authors Kyrill Winkler, Ami Paz, Hugo Rincon-Galeana, Stefan Schmid, Ulrich Schmid

Publication date 30 May 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-024-01209-4

zbMATH Keywords

consensusdynamic networksoblivious message adversariestime complexity

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A characterization of oblivious message adversaries for which consensus is solvable
• A combinatorial characterization of the distributed 1-solvable tasks
• A non-topological proof for the impossibility of \(k\)-set agreement
• A topological perspective on distributed network algorithms
• Agreement in synchronous networks with ubiquitous faults
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• Bounds on the step and namespace complexity of renaming
• Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Consensus in rooted dynamic networks with short-lived stability
• Coordinated consensus in dynamic networks
• Distributed computation in dynamic networks
• Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
• scientific article; zbMATH DE number 7150620 (Why is no real title available?)
• Impossibility of distributed consensus with one faulty process
• Impossibility Results and Lower Bounds for Consensus under Link Failures
• On linear-time data dissemination in dynamic rooted trees
• On the radius of nonsplit graphs and information dissemination in dynamic networks
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• Synchronous consensus under hybrid process and link failures
• The Heard-Of model: computing in distributed systems with benign faults
• Tight bounds for asymptotic and approximate consensus
• Time is not a healer (preliminary version)
• Timeliness, failure-detectors, and consensus performance
• Topological Characterization of Consensus under General Message Adversaries

Cited in

(2)

• Keynote: Time is not a healer: before and after
• The complexity of full-information iterated protocols

This page was built for publication: The time complexity of consensus under oblivious message adversaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6547208)