Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects

DOI10.1137/130936828zbMath1338.68020OpenAlexW2336858153MaRDI QIDQ2802146

Michel Raynal, Damien Imbs, Sergio Rajsbaum, Armando Castañeda

Publication date: 25 April 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130936828

zbMATH Keywords

symmetry breaking coordination nondeterminism agreement crash failure wait-freedom distributed computability set agreement concurrent object renaming asynchronous read/write model decision task problem hierarchy

Mathematics Subject Classification ID

Distributed systems (68M14)

Related Items (2)

From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ A distributed computing perspective of unconditionally secure information transmission in Russian cards problems

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
The renaming problem in shared memory systems: an introduction
On set consensus numbers
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
Computing in totally anonymous asynchronous shared memory systems
A classification of wait-free loop agreement tasks
Wait-free algorithms for fast, long-lived renaming
The $k$-simultaneous consensus problem
Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks
The Combinatorial Structure of Wait-Free Solvable Tasks
The topological structure of asynchronous computability
Renaming in an asynchronous environment
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
The Committee Decision Problem
Bit complexity of breaking and achieving symmetry in chains and rings
Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus
Reaching approximate agreement in the presence of faults
Impossibility of distributed consensus with one faulty process
Atomic snapshots of shared memory
Sharing memory robustly in message-passing systems
Unreliable failure detectors for reliable distributed systems
Counting-Based Impossibility Proofs for Renaming and Set Agreement
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
The BG distributed simulation algorithm
Sporadic Solutions to Zero-One Exclusion Tasks
The topology of shared-memory adversaries
Generalized FLP impossibility result for t-resilient asynchronous computations
Set consensus using arbitrary objects (preliminary version)
Distributed Computing
New combinatorial topology bounds for renaming

This page was built for publication: Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects