Impossibility Results for Distributed Computing

DOI10.2200/S00551ED1V01Y201311DCT012zbMath1396.68004MaRDI QIDQ4568311

Hagit Attiya, Faith Ellen

Publication date: 19 June 2018

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

zbMATH Keywords

coveringscalingsnapshotssimulationslower boundsindistinguishabilityconsensusmutual exclusionclock synchronizationtimestampsshiftingimplementationsinformation theory argumentsscenario argumentsvalency reductions

Mathematics Subject Classification ID

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

Related Items (8)

Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement ⋮ 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 ⋮ Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes ⋮ On the optimal space complexity of consensus for anonymous processes ⋮ Recent Results on Fault-Tolerant Consensus in Message-Passing Networks ⋮ A Tight Space Bound for Consensus

This page was built for publication: Impossibility Results for Distributed Computing