Hundreds of impossibility results for distributed computing (Q5138488)

scientific article; zbMATH DE number 7281998

Language	Label	Description	Also known as
English	Hundreds of impossibility results for distributed computing	scientific article; zbMATH DE number 7281998

Statements

instance of

scholarly article

0 references

title

Hundreds of impossibility results for distributed computing (English)

0 references

0 references

0 references

Distributed Computing

0 references

publication date

4 December 2020

0 references

zbMATH Keywords

distributed computing

0 references

complexity lower bounds

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s00446-003-0091-y

0 references

cites work

The Bit Complexity of Randomized Leader Election on a Ring

0 references

Randomized function evaluation on a ring

0 references

Tight lower bounds for probabilistic solitude verification on anonymous rings

0 references

The complexity of end-to-end communication in memoryless networks

0 references

Atomic snapshots of shared memory

0 references

Q4234103

0 references

Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

0 references

Computing with faulty shared objects

0 references

The power of multiobjects.

0 references

Optimal Time–Space Tradeoff for Shared Memory Leader Election

0 references

Mixed consistency

0 references

A simple bivalency proof that $t$-resilient consensus requires $t+1$ rounds

0 references

Causal memory: definitions, implementation, and programming

0 references

Average and Randomized Complexity of Distributed Problems

0 references

Time-Adaptive Algorithms for Synchronization

0 references

Contention-free complexity of shared memory algorithms

0 references

On the message complexity of binary Byzantine agreement under crash failures

0 references

Time/contention trade-offs for multiprocessor synchronization

0 references

Composite registers

0 references

An improved lower bound for the time complexity of mutual exclusion

0 references

Algorithms for the Certified Write-All Problem

0 references

Efficiency of Synchronous Versus Asynchronous Distributed Systems

0 references

Time- and Space-Efficient Randomized Consensus

0 references

Lower bounds for distributed coin-flipping and randomized consensus

0 references

Spreading Rumors Rapidly Despite an Adversary

0 references

Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor

0 references

Renaming in an asynchronous environment

0 references

Time bounds for decision problems in the presence of timing uncertainty and failures

0 references

Bounds on the time to reach agreement in the presence of timing uncertainty

0 references

A Correctness Condition for High-Performance Multiprocessors

0 references

Computing in totally anonymous asynchronous shared memory systems

0 references

Optimal Clock Synchronization under Different Delay Assumptions

0 references

Are wait-free algorithms fast?

0 references

Language complexity on the synchronous anonymous ring

0 references

Efficiency of semisynchronous versus asynchronous networks

0 references

The Combinatorial Structure of Wait-Free Solvable Tasks

0 references

Better computing on the anonymous ring

0 references

Computing on an anonymous ring

0 references

Q4398822

0 references

Efficient asynchronous consensus with the weak adversary scheduler

0 references

Complexity of network synchronization

0 references

A trade-off between information and communication in broadcast protocols

0 references

Reliable broadcasts and communication models: tradeoffs and lower bounds

0 references

A tight lower bound for randomized synchronous consensus

0 references

Simplifying fault-tolerance

0 references

Closed form bounds for clock synchronization under simple uncertainty assumptions

0 references

A combinatorial characterization of the distributed 1-solvable tasks

0 references

Q4028117

0 references

Tight bounds on the round complexity of distributed 1-solvable tasks

0 references

New lower bound techniques for distributed leader finding and other problems on rings of processors

0 references

The distributed bit complexity of the ring: From the anonymous to the non-anonymous case

0 references

Computing anonymously with arbitrary knowledge

0 references

Q4436038

0 references

Generalized FLP impossibility result for t-resilient asynchronous computations

0 references

Immediate atomic snapshots and fast renaming

0 references

A simple algorithmically reasoned characterization of wait-free computation (extended abstract)

0 references

The BG distributed simulation algorithm

0 references

On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes

0 references

Asynchronous consensus and broadcast protocols

0 references

Bounds on shared memory for mutual exclusion

0 references

Data Requirements for Implementation of N -Process Mutual Exclusion Using a Single Shared Variable

0 references

Parallel Algorithms with Processor Failures and Delays

0 references

Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract)

0 references

On the impossibility of group membership

0 references

Unreliable failure detectors for reliable distributed systems

0 references

The weakest failure detector for solving consensus

0 references

A polylog time wait-free construction for closed objects

0 references

Q4692502

0 references

More $choices$ allow more $faults$: Set consensus problems in totally asynchronous systems

0 references

Tight bounds for k -set agreement

0 references

Wait-free implementations in message-passing systems

0 references

Bounds on the Costs of Multivalued Register Implementations

0 references

Simple constant-time consensus protocols in realistic failure models

0 references

Solvability in Asynchronous Environments II: Finite Interactive Tasks

0 references

Message terminating algorithms for anonymous rings of unknown size

0 references

The Distributed Firing Squad Problem

0 references

Simultaneity is harder than agreement

0 references

Transaction commit in a realistic timing model

0 references

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

0 references

Q4137124

0 references

On k -set consensus problems in asynchronous systems

0 references

The Byzantine generals strike again

0 references

On the minimal synchronism needed for distributed consensus

0 references

On the possibility and impossibility of achieving clock synchronization

0 references

An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

0 references

Reaching approximate agreement in the presence of faults

0 references

Bounds on information exchange for Byzantine agreement

0 references

Early stopping in Byzantine agreement

0 references

Authenticated Algorithms for Byzantine Agreement

0 references

Q2782251

0 references

Two lower bounds in asynchronous distributed computation

0 references

Contention in shared memory algorithms

0 references

Knowledge and common knowledge in a Byzantine environment: Crash failures

0 references

Space-optimal multi-writer snapshot objects are slow

0 references

A tight time lower bound for space-optimal implementations of multi-writer snapshots

0 references

The impossibility of implementing reliable communication in the face of crashes

0 references

Asynchronous approximate agreement

0 references

An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement

0 references

Lower bounds for convergence function based clock synchronization

0 references

On the space complexity of randomized synchronization

0 references

Q2766858

0 references

Q3666268

0 references

A lower bound for the time to assure interactive consistency

0 references

Easy impossibility proofs for distributed consensus problems

0 references

Impossibility of distributed consensus with one faulty process

0 references

The Wakeup Problem

0 references

Electing a leader in a synchronous ring

0 references

Implementing hybrid consistency with high-level synchronization operations

0 references

Round-by-round fault detectors (extended abstract)

0 references

Three-Processor Tasks Are Undecidable

0 references

On the complexity of global computation in the presence of link failures

0 references

An algorithm for the asynchronous Write-All problem based on process collision

0 references

Q4318989

0 references

Message-optimal protocols for Byzantine Agreement

0 references

Simple extensions of 1-writer atomic variable constructions to multiwriter ones

0 references

Optimal precision in the presence of uncertainty

0 references

Knowledge and common knowledge in a distributed environment

0 references

Q5137896

0 references

Set consensus using arbitrary objects (preliminary version)

0 references

Algebraic spans

0 references

Computer science today. Recent trends and developments

0 references

Q4527026

0 references

A classification of wait-free loop agreement tasks

0 references

Q4941899

0 references

Unifying synchronous and asynchronous message-passing models

0 references

The topological structure of asynchronous computability

0 references

Linearizable counting networks

0 references

Q2766860

0 references

Asymptotically Optimal Election on Weighted Rings

0 references

Towards a topological characterization of asynchronous complexity

0 references

Q4250795

0 references

The time complexity of updating snapshot memories

0 references

Symmetry breaking in distributed networks

0 references

Robust wait-free hierarchies

0 references

A lower bound on the local time complexity of universal constructions

0 references

Solvability of Consensus: Composition Breaks Down for NonDeterministic Types

0 references

A time complexity lower bound for randomized implementations of some shared objects

0 references

Fault-tolerant wait-free shared objects

0 references

Time and Space Lower Bounds for Nonblocking Implementations

0 references

Crash failures can drive protocols to arbitrary states

0 references

Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability

0 references

Efficient parallel algorithms can be made robust

0 references

Q4344152

0 references

Resource bounds and combinations of consensus objects

0 references

The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors

0 references

Optimal lower bounds for some distributed algorithms for a complete network of processors

0 references

Q4267802

0 references

Efficient synchronization of multiprocessors with shared memory

0 references

Lower Bounds for Randomized Mutual Exclusion

0 references

Counting protocols for reliable end-to-end transmission

0 references

A new solution of Dijkstra's concurrent programming problem

0 references

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

0 references

The Weak Byzantine Generals Problem

0 references

The mutual exclusion problem

0 references

On interprocess communication. II: Algorithms

0 references

Synchronizing clocks in the presence of faults

0 references

The Byzantine Generals Problem

0 references

More on t-resilience vs. wait-freedom (extended abstract)

0 references

All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust

0 references

On the power of shared object types to implement one-resilient Consensus

0 references

Distributed MST for constant diameter graphs

0 references

Closed schedulers: a novel technique for analyzing asynchronous protocols

0 references

An upper and lower bound for clock synchronization

0 references

Q3126969

0 references

On describing the behavior and implementation of distributed systems

0 references

Q2766890

0 references

The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels

0 references

On the bit complexity of distributed computations in a ring with a leader

0 references

On the Complexity of Certified Write-All Algorithms

0 references

Linearizable read/write objects

0 references

Q4437125

0 references

A Lower Bound on Wait-Free Counting

0 references

Concurrent counting

0 references

Gap Theorems for Distributed Computation

0 references

A Layered Analysis of Consensus

0 references

Programming simultaneous actions using common knowledge

0 references

Conditions on input vectors for consensus solvability in asynchronous distributed systems

0 references

What Can be Computed Locally?

0 references

Distributed consensus revisited

0 references

Automatically increasing the fault-tolerance of distributed algorithms

0 references

A Model for Asynchronous Shared Memory Parallel Computation

0 references

A lower bound for probabilistic distributed algorithms

0 references

A theory of clock synchronization (extended abstract)

0 references

Reaching Agreement in the Presence of Faults

0 references

A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction

0 references

An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem

0 references

The choice coordination problem

0 references

Q4000351

0 references

Q3787484

0 references

The impact of time on the session problem

0 references

Q5681937

0 references

Q5658452

0 references

Consensus numbers of multi-objects

0 references

Determining Consensus Numbers

0 references

Lower bounds for leader election and collective coin-flipping in the perfect information model

0 references

Comparison of initial conditions for distributed algorithms on anonymous networks

0 references

Optimal Space Distributed Order-Preserving Lists

0 references

Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

0 references

Time is not a healer

0 references

Q4252757

0 references

Leader election in complete networks

0 references

Initial failures in distributed computations

0 references

Possibility and impossibility results in a shared memory environment

0 references

An inherent bottleneck in distributed counting

0 references

Simulating synchronous processors

0 references

A new fault-tolerant algorithm for clock synchronization

0 references

Computing functions on asynchronous anonymous networks

0 references

Identifiers

zbMATH Open document ID

1448.68095

0 references

DOI

10.1007/s00446-003-0091-y

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5138488