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 breakingcoordinationnondeterminismagreementcrash failurewait-freedomdistributed computabilityset agreementconcurrent objectrenamingasynchronous read/write modeldecision taskproblem 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