What can be computed in a distributed system?

DOI10.1007/978-3-642-54848-2_14zbMATH Open1416.68025OpenAlexW58683544MaRDI QIDQ5170751FDOQ5170751

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• 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)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

Cited In (3)

• What Can be Computed Locally?
• Initial failures in distributed computations
• Title not available (Why is that?)

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)