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