What Can be Computed in a Distributed System?
DOI10.1007/978-3-642-54848-2_14zbMath1416.68025OpenAlexW58683544MaRDI QIDQ5170751
Publication date: 24 July 2014
Published in: From Programs to Systems. The Systems perspective in Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-54848-2_14
environmentfault-tolerancedistributed computingconcurrencyconsensusagreementasynchronous systemsynchronous systematomicitycrash failureuniversal constructionwait-freedomdistributed computabilitymessage-passing systemimpossibilitydistributed complexitymessage adversaryprogress conditionindulgenceread/write system
Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The weakest failure detector to implement a register in asynchronous systems with hybrid communication
- Power and limits of distributed computing shared memory models
- The renaming problem in shared memory systems: an introduction
- The minimum information about failures for solving non-local tasks in message-passing systems
- The complexity of updating snapshot objects
- A timing assumption and two \(t\)-resilient protocols for Implementing an eventual leader service in asynchronous shared memory systems
- A simple proof of the necessity of the failure detector \(\Sigma \) to implement an atomic register in asynchronous message-passing systems
- On interprocess communication. I: Basic formalism
- The weakest failure detectors to boost obstruction-freedom
- Synchronous condition-based consensus
- Agreement in synchronous networks with ubiquitous faults
- Distributed computation in dynamic networks
- Every problem has a weakest failure detector
- The topological structure of asynchronous computability
- Concurrent Programming: Algorithms, Principles, and Foundations
- Conditions on input vectors for consensus solvability in asynchronous distributed systems
- Renaming in an asynchronous environment
- Tight failure detection bounds on atomic object implementations
- Impossibility of distributed consensus with one faulty process
- Reaching Agreement in the Presence of Faults
- Locality in Distributed Graph Algorithms
- Time, clocks, and the ordering of events in a distributed system
- Atomic snapshots of shared memory
- Sharing memory robustly in message-passing systems
- Unreliable failure detectors for reliable distributed systems
- The weakest failure detector for solving consensus
- Distributed Computing: A Locality-Sensitive Approach
- Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
- On asymmetric progress conditions
- Indulgent algorithms (preliminary version)
- What can be computed locally?
- New combinatorial topology bounds for renaming
- Towards a complexity theory for local distributed computing
- What cannot be computed locally!
This page was built for publication: What Can be Computed in a Distributed System?
