Hundreds of impossibility results for distributed computing

DOI10.1007/S00446-003-0091-YzbMATH Open1448.68095OpenAlexW2038924034MaRDI QIDQ5138488FDOQ5138488

Authors: Eric Ruppert, Faith E. Fich 

Publication date: 4 December 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-003-0091-y

Recommendations

• scientific article; zbMATH DE number 1696663
• What can be computed in a distributed system?
• Impossibility results for distributed computing
• scientific article; zbMATH DE number 1559574
• Power and limits of distributed computing shared memory models

zbMATH Keywords

distributed computingcomplexity lower bounds

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) 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?)
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Self-stabilization
• Computing anonymously with arbitrary knowledge
• Title not available (Why is that?)
• Better computing on the anonymous ring
• A trade-off between information and communication in broadcast protocols
• Renaming in an asynchronous environment
• Electing a leader in a synchronous ring
• Computing on an anonymous ring
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• Unreliable failure detectors for reliable distributed systems
• Closed form bounds for clock synchronization under simple uncertainty assumptions
• Complexity of network synchronization
• Title not available (Why is that?)
• Causal memory: definitions, implementation, and programming
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• On interprocess communication. II: Algorithms
• Computer science today. Recent trends and developments
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Efficiency of Synchronous Versus Asynchronous Distributed Systems
• Efficiency of semisynchronous versus asynchronous networks
• Computing with faulty shared objects
• Leader election in complete networks
• The impact of time on the session problem
• Initial failures in distributed computations
• Composite registers
• The time complexity of updating snapshot memories
• Authenticated Algorithms for Byzantine Agreement
• Early stopping in Byzantine agreement
• The Weak Byzantine Generals Problem
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• The Byzantine generals strike again
• Atomic snapshots of shared memory
• Are wait-free algorithms fast?
• The weakest failure detector for solving consensus
• Knowledge and common knowledge in a distributed environment
• A new solution of Dijkstra's concurrent programming problem
• Optimal precision in the presence of uncertainty
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• The topological structure of asynchronous computability
• Title not available (Why is that?)
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes
• Bounds on shared memory for mutual exclusion
• On the space complexity of randomized synchronization
• Time and Space Lower Bounds for Nonblocking Implementations
• A lower bound for the time to assure interactive consistency
• A layered analysis of consensus
• Unifying synchronous and asynchronous message-passing models
• Tight bounds for \(k\)-set agreement
• A combinatorial characterization of the distributed 1-solvable tasks
• Three-Processor Tasks Are Undecidable
• Bounds on the time to reach agreement in the presence of timing uncertainty
• Title not available (Why is that?)
• Set consensus using arbitrary objects (preliminary version)
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Immediate atomic snapshots and fast renaming
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• Distributed MST for constant diameter graphs
• Message terminating algorithms for anonymous rings of unknown size
• Computing in totally anonymous asynchronous shared memory systems
• A classification of wait-free loop agreement tasks
• Time/contention trade-offs for multiprocessor synchronization
• Contention-free complexity of shared memory algorithms
• The Combinatorial Structure of Wait-Free Solvable Tasks
• Automatically increasing the fault-tolerance of distributed algorithms
• Reaching approximate agreement in the presence of faults
• Asynchronous consensus and broadcast protocols
• Data Requirements for Implementation of N -Process Mutual Exclusion Using a Single Shared Variable
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for the Certified Write-All Problem
• Title not available (Why is that?)
• An algorithm for the asynchronous \textit{Write-All} problem based on process collision
• The BG distributed simulation algorithm
• Symmetry breaking in distributed networks
• Programming simultaneous actions using common knowledge
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• On the possibility and impossibility of achieving clock synchronization
• Easy impossibility proofs for distributed consensus problems
• A theory of clock synchronization (extended abstract)
• Optimal Clock Synchronization under Different Delay Assumptions
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• Contention in shared memory algorithms
• Title not available (Why is that?)
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Simplifying fault-tolerance, providing the abstraction of crash failures
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Title not available (Why is that?)
• Bounds on information exchange for Byzantine agreement
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• Title not available (Why is that?)
• On the Complexity of Certified Write-All Algorithms
• Time is not a healer (preliminary version)
• Asymptotically Optimal Election on Weighted Rings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Solvability in Asynchronous Environments II: Finite Interactive Tasks
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Resource bounds and combinations of consensus objects
• More on t-resilience vs. wait-freedom (extended abstract)
• Space-optimal multi-writer snapshot objects are slow
• A time complexity lower bound for randomized implementations of some shared objects
• Efficient asynchronous consensus with the weak adversary scheduler
• Comparison of initial conditions for distributed algorithms on anonymous networks
• Computing functions on asynchronous anonymous networks
• An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
• The mutual exclusion problem
• Efficient parallel algorithms can be made robust
• Possibility and impossibility results in a shared memory environment
• Simple extensions of 1-writer atomic variable constructions to multiwriter ones
• Synchronizing clocks in the presence of faults
• Title not available (Why is that?)
• Simulating synchronous processors
• Reliable broadcasts and communication models: tradeoffs and lower bounds
• An inherent bottleneck in distributed counting
• Concurrent counting
• What Can be Computed Locally?
• Parallel Algorithms with Processor Failures and Delays
• Wait-free implementations in message-passing systems
• A tight time lower bound for space-optimal implementations of multi-writer snapshots
• Lower Bounds for Randomized Mutual Exclusion
• Spreading Rumors Rapidly Despite an Adversary
• Time bounds for decision problems in the presence of timing uncertainty and failures
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Time- and Space-Efficient Randomized Consensus
• Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor
• Language complexity on the synchronous anonymous ring
• Asynchronous approximate agreement
• A lower bound for probabilistic distributed algorithms
• The Bit Complexity of Randomized Leader Election on a Ring
• The Distributed Firing Squad Problem
• Tight bounds on the round complexity of distributed 1-solvable tasks
• Randomized function evaluation on a ring
• An upper and lower bound for clock synchronization
• The impossibility of implementing reliable communication in the face of crashes
• A new fault-tolerant algorithm for clock synchronization
• Title not available (Why is that?)
• Simple constant-time consensus protocols in realistic failure models
• Message-optimal protocols for Byzantine Agreement
• Simultaneity is harder than agreement
• On describing the behavior and implementation of distributed systems
• The choice coordination problem
• Two lower bounds in asynchronous distributed computation
• New lower bound techniques for distributed leader finding and other problems on rings of processors
• Lower bounds for distributed coin-flipping and randomized consensus
• Fault-tolerant wait-free shared objects
• On the message complexity of binary Byzantine agreement under crash failures
• Time-Adaptive Algorithms for Synchronization
• Efficient synchronization of multiprocessors with shared memory
• A tight lower bound for randomized synchronous consensus
• Transaction commit in a realistic timing model
• On the bit complexity of distributed computations in a ring with a leader
• Robust wait-free hierarchies
• Determining Consensus Numbers
• Linearizable counting networks
• Algebraic spans
• A Correctness Condition for High-Performance Multiprocessors
• Towards a topological characterization of asynchronous complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels
• Counting protocols for reliable end-to-end transmission
• Linearizable read/write objects
• A Model for Asynchronous Shared Memory Parallel Computation
• Mixed consistency
• Distributed consensus revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implementing hybrid consistency with high-level synchronization operations
• Gap Theorems for Distributed Computation
• Title not available (Why is that?)
• Lower bounds for convergence function based clock synchronization
• Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability
• The Wakeup Problem
• Computable obstructions to wait-free computability
• Title not available (Why is that?)
• The power of multiobjects.
• An improved lower bound for the time complexity of mutual exclusion
• Consensus numbers of multi-objects
• A Lower Bound on Wait-Free Counting
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• Crash failures can drive protocols to arbitrary states
• On the impossibility of group membership
• Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract)
• Solvability of Consensus: Composition Breaks Down for NonDeterministic Types
• All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust
• Conditions on input vectors for consensus solvability in asynchronous distributed systems
• Lower bounds for leader election and collective coin-flipping in the perfect information model
• Bounds on the Costs of Multivalued Register Implementations
• A polylog time wait-free construction for closed objects
• Optimal Time–Space Tradeoff for Shared Memory Leader Election
• On k -set consensus problems in asynchronous systems
• On the power of shared object types to implement one-resilient consensus
• A lower bound on the local time complexity of universal constructions
• Title not available (Why is that?)
• The complexity of end-to-end communication in memoryless networks
• On the complexity of global computation in the presence of link failures: the case of uni-directional faults
• Average and Randomized Complexity of Distributed Problems
• Title not available (Why is that?)
• Optimal Space Distributed Order-Preserving Lists

Cited In (21)

• Power and limits of distributed computing shared memory models
• Impossibility results for distributed computing
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Wait-free solvability of colorless tasks in anonymous shared-memory model
• Graph searching with advice
• Tree exploration with advice
• Communication algorithms with advice
• Node labels in local decision
• Tight bounds for parallel randomized load balancing
• On the cost of uniform protocols whose memory consumption is adaptive to interval contention
• Networks cannot compute their diameter in sublinear time
• Title not available (Why is that?)
• Automata, Languages and Programming
• On the inherent weakness of conditional primitives
• On the impact of link faults on Byzantine agreement
• Impossibility results for distributed transactional memory
• On the round complexity of Byzantine agreement without initial set-up
• The computational structure of progress conditions and shared objects
• A topological view of partitioning arguments: reducing \(k\)-set agreement to consensus
• Disaster avoidance mechanism for content-delivering service
• Anonymous processors with synchronous shared memory: Monte Carlo algorithms

This page was built for publication: Hundreds of impossibility results for distributed computing

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