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

clock synchronizationconsensuscoveringimplementationsindistinguishabilityinformation theory argumentslower boundsmutual exclusionscalingscenario argumentsshiftingsimulationssnapshotstimestampsvalency reductions

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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

(20)

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

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)