What can be computed in a distributed system?

DOI10.1007/978-3-642-54848-2_14MaRDI QIDQ5170751zbMATH OpenOpenAlexFDO

Authors Michel Raynal

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

zbMATH Keywords

agreementdistributed computingconsensusfault-toleranceconcurrencyasynchronous systemsynchronous systematomicityenvironmentcrash failuredistributed computabilityuniversal constructionwait-freedommessage-passing systemimpossibilitydistributed complexitymessage adversaryprogress conditionindulgenceread/write system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• A pleasant stroll through the land of distributed machines, computation, and universality
• scientific article; zbMATH DE number 1696663
• Impossibility results for distributed computing
• Power and limits of distributed computing shared memory models
• Initial failures in distributed computations

Cites work

• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• A simple proof of the necessity of the failure detector \(\Sigma \) to implement an atomic register in asynchronous message-passing systems
• A timing assumption and two \(t\)-resilient protocols for Implementing an eventual leader service in asynchronous shared memory systems
• Agreement in synchronous networks with ubiquitous faults
• Algorithmics. The spirit of computing
• Atomic snapshots of shared memory
• Concurrent programming: algorithms, principles, and foundations.
• Conditions on input vectors for consensus solvability in asynchronous distributed systems
• Distributed Computing: A Locality-Sensitive Approach
• Distributed computation in dynamic networks
• Distributed computing through combinatorial topology
• Every problem has a weakest failure detector
• Impossibility of distributed consensus with one faulty process
• Indulgent algorithms (preliminary version)
• Locality in Distributed Graph Algorithms
• New combinatorial topology bounds for renaming: the upper bound
• On asymmetric progress conditions
• On interprocess communication. I: Basic formalism
• Power and limits of distributed computing shared memory models
• Reaching Agreement in the Presence of Faults
• Renaming in an asynchronous environment
• Sharing memory robustly in message-passing systems
• Synchronous condition-based consensus
• Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
• The complexity of updating snapshot objects
• The minimum information about failures for solving non-local tasks in message-passing systems
• The renaming problem in shared memory systems: an introduction
• The topological structure of asynchronous computability
• The weakest failure detector for solving consensus
• The weakest failure detector to implement a register in asynchronous systems with hybrid communication
• The weakest failure detectors to boost obstruction-freedom
• Tight failure detection bounds on atomic object implementations
• Time, clocks, and the ordering of events in a distributed system
• Towards a complexity theory for local distributed computing
• Unreliable failure detectors for reliable distributed systems
• What can be computed locally?
• What cannot be computed locally!

Cited in

(5)

• Power and limits of distributed computing shared memory models
• Hundreds of impossibility results for distributed computing
• What Can be Computed Locally?
• Initial failures in distributed computations
• scientific article; zbMATH DE number 1696663 (Why is no real title available?)

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)