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