The renaming problem in shared memory systems: an introduction

DOI10.1016/j.cosrev.2011.04.001zbMath1298.68049OpenAlexW2028117109MaRDI QIDQ465682

Sergio Rajsbaum, Armando Castañeda, Michel Raynal

Publication date: 24 October 2014

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

Full work available at URL: https://hal.inria.fr/inria-00537914/file/PI-1960.pdf

zbMATH Keywords

algebraic topologyrecursionlower boundssymmetry breakingconcurrencyconsensusasynchronous systemcrash failurewait-freedomobstruction-freedomset agreementrenamingatomic snapshotread/write shared memory systemsplittertest\&setwrite-snapshot

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed systems (68M14)

Related Items

A visit to mutual exclusion in seven dates ⋮ Unnamed Item ⋮ Power and limits of distributed computing shared memory models ⋮ Tasks in modular proofs of concurrent algorithms ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Waiting in concurrent algorithms ⋮ A closer look at fault tolerance ⋮ Bounds on the Step and Namespace Complexity of Renaming ⋮ What Can be Computed in a Distributed System? ⋮ A simplicial complex model for dynamic epistemic logic to study distributed task computability ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ A distributed computing perspective of unconditionally secure information transmission in Russian cards problems ⋮ Asynchronous Coordination Under Preferences and Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New combinatorial topology bounds for renaming: the lower bound
• From adaptive renaming to set agreement
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Wait-free algorithms for fast, long-lived renaming
• Adaptive and Efficient Algorithms for Lattice Agreement and Renaming
• Failure detectors in loosely named systems
• New combinatorial topology upper and lower bounds for renaming
• Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing - PODC '94
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Renaming in an asynchronous environment
• A combinatorial characterization of the distributed 1-solvable tasks
• Exploring Gafni’s Reduction Land: From Ω k to Wait-Free Adaptive $(2p-\lceil\frac{p}{k}\rceil)$ -Renaming Via k-Set Agreement
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Help When Needed, But No More: Efficient Read/Write Partial Snapshot
• Impossibility of distributed consensus with one faulty process
• Atomic snapshots of shared memory
• Unreliable failure detectors for reliable distributed systems
• Atomic Snapshots in O (n log n) Operations
• Algebraic spans
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Failure detectors and the wait-free hierarchy (extended abstract)
• Immediate atomic snapshots and fast renaming
• Group-Solvability