Power and limits of distributed computing shared memory models

DOI10.1016/j.tcs.2013.03.002zbMath1358.68038OpenAlexW2037266632MaRDI QIDQ392187

Sergio Rajsbaum, Michel Raynal, Maurice P. Herlihy

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.002

zbMATH Keywords

snapshotlivenessrecursiontopologyfault-toleranceconcurrencyagreementasynchronous systemcrash failureresiliencewait-freedomdistributed computabilityfailure detectoradversaryBorowsky-Gafni (BG) simulationdistributed computing modeliterated modelmodel equivalenceshared-memory systemtask

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (9)

From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ Extending the wait-free hierarchy to multi-threaded systems ⋮ A Simple Object that Spans the Whole Consensus Hierarchy ⋮ Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement ⋮ About informatics, distributed computing, and our job: a personal view ⋮ What Can be Computed in a Distributed System? ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ t-Resilient Immediate Snapshot Is Impossible

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The renaming problem in shared memory systems: an introduction
• The disagreement power of an adversary
• Help when needed, but no more: efficient read/write partial snapshot
• An impossibility about failure detectors in the iterated immediate snapshot model
• Classifying rendezvous tasks of arbitrary dimension
• On interprocess communication. I: Basic formalism
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• A classification of wait-free loop agreement tasks
• The Heard-Of model: computing in distributed systems with benign faults
• The \(k\)-simultaneous consensus problem
• A Layered Analysis of Consensus
• Unifying synchronous and asynchronous message-passing models
• Simulations and reductions for colorless tasks
• Locality and Checkability in Wait-Free Computing
• The Combinatorial Structure of Wait-Free Solvable Tasks
• 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
• The Iterated Restricted Immediate Snapshot Model
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Concurrent Computing and Shellable Complexes
• The Computational Structure of Progress Conditions
• Reaching approximate agreement in the presence of faults
• Impossibility of distributed consensus with one faulty process
• The Byzantine Generals Problem
• Three-Processor Tasks Are Undecidable
• Atomic snapshots of shared memory
• Unreliable failure detectors for reliable distributed systems
• The weakest failure detector for solving consensus
• Atomic Snapshots in O (n log n) Operations
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The BG distributed simulation algorithm
• The extended BG-simulation and the characterization of t-resiliency
• The multiplicative power of consensus numbers
• On asymmetric progress conditions
• The topology of shared-memory adversaries
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A completeness theorem for a class of synchronization objects
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• Practical implementations of non-blocking synchronization primitives
• Immediate atomic snapshots and fast renaming
• Brief announcement

This page was built for publication: Power and limits of distributed computing shared memory models