Impossibility results for distributed computing

DOI10.2200/S00551ED1V01Y201311DCT012MaRDI QIDQ4568311zbMATH OpenFDO

Authors Hagit Attiya, Faith Ellen

Publication date 19 June 2018

Published in Synthesis Lectures on Distributed Computing Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2200/S00551ED1V01Y201311DCT012

zbMATH Keywords

simulationslower boundsconsensuscoveringclock synchronizationscalingindistinguishabilitymutual exclusiontimestampsshiftingsnapshotsimplementationsinformation theory argumentsscenario argumentsvalency reductions

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Hundreds of impossibility results for distributed computing
• Power and limits of distributed computing shared memory models
• scientific article; zbMATH DE number 1179121
• scientific article; zbMATH DE number 1696663
• Distributed Systems

Cited in

(19)

• Power and limits of distributed computing shared memory models
• Nearly-optimal consensus tolerating adaptive omissions: why a lot of randomness is needed?
• Determining recoverable consensus numbers
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Hundreds of impossibility results for distributed computing
• The computational structure of progress conditions
• Recent results on fault-tolerant consensus in message-passing networks
• The space complexity of consensus from swap
• scientific article; zbMATH DE number 1696663 (Why is no real title available?)
• Fast agreement in networks with Byzantine nodes
• About informatics, distributed computing, and our job: a personal view
• An impossibility result for virtual implementation with status quo
• Fundamental limitation on achievable decentralized performance
• Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
• A tight space bound for consensus
• Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement
• Why Extension-Based Proofs Fail
• What can be computed in a distributed system?

This page was built for publication: Impossibility results for distributed computing

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