What Can be Computed in a Distributed System?
DOI10.1007/978-3-642-54848-2_14zbMATH Open1416.68025OpenAlexW58683544MaRDI QIDQ5170751FDOQ5170751
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
agreementdistributed computingconsensusfault-toleranceconcurrencyasynchronous systemsynchronous systematomicityenvironmentcrash failuredistributed computabilityuniversal constructionwait-freedommessage-passing systemimpossibilitydistributed complexitymessage adversaryprogress conditionindulgenceread/write system
Analysis of algorithms and problem complexity (68Q25) 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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Renaming in an asynchronous environment
- Unreliable failure detectors for reliable distributed systems
- Distributed Computing: A Locality-Sensitive Approach
- On interprocess communication. I: Basic formalism
- Distributed computation in dynamic networks
- Locality in Distributed Graph Algorithms
- Time, clocks, and the ordering of events in a distributed system
- What cannot be computed locally!
- Impossibility of distributed consensus with one faulty process
- Reaching Agreement in the Presence of Faults
- Atomic snapshots of shared memory
- The weakest failure detector for solving consensus
- The weakest failure detectors to boost obstruction-freedom
- The topological structure of asynchronous computability
- Concurrent Programming: Algorithms, Principles, and Foundations
- Every problem has a weakest failure detector
- Tight failure detection bounds on atomic object implementations
- A simple proof of the necessity of the failure detector \(\Sigma \) to implement an atomic register in asynchronous message-passing systems
- Conditions on input vectors for consensus solvability in asynchronous distributed systems
- The weakest failure detector to implement a register in asynchronous systems with hybrid communication
- Power and limits of distributed computing shared memory models
- Sharing memory robustly in message-passing systems
- The renaming problem in shared memory systems: an introduction
- On asymmetric progress conditions
- Synchronous condition-based consensus
- Indulgent algorithms (preliminary version)
- Agreement in synchronous networks with ubiquitous faults
- Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
- New combinatorial topology bounds for renaming
- What can be computed locally?
- 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
- Towards a complexity theory for local distributed computing
Cited In (2)
This page was built for publication: What Can be Computed in a Distributed System?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5170751)
