Generalized symmetry breaking tasks and nondeterminism in concurrent objects

DOI10.1137/130936828MaRDI QIDQ2802146zbMATH OpenOpenAlexFDO

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

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

agreementcoordinationnondeterminismsymmetry breakingcrash failuredistributed computabilitywait-freedomset agreementconcurrent objectrenamingasynchronous read/write modeldecision taskproblem hierarchy

Mathematics Subject Classification ID

Distributed systems (68M14)

Recommendations

• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• The renaming problem in shared memory systems: an introduction
• Counting-based impossibility proofs for renaming and set agreement

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• scientific article; zbMATH DE number 1559574 (Why is no real title available?)
• A classification of wait-free loop agreement tasks
• Atomic snapshots of shared memory
• Bit complexity of breaking and achieving symmetry in chains and rings
• Computing in totally anonymous asynchronous shared memory systems
• Counting-based impossibility proofs for renaming and set agreement
• Distributed Computing
• Distributed computing through combinatorial topology
• Exploring Gafni’s Reduction Land: From Ω k to Wait-Free Adaptive $(2p-\lceil\frac{p}{k}\rceil)$ -Renaming Via k-Set Agreement
• From adaptive renaming to set agreement
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Impossibility of distributed consensus with one faulty process
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• New combinatorial topology bounds for renaming: the lower bound
• New combinatorial topology bounds for renaming: the upper bound
• On set consensus numbers
• Reaching approximate agreement in the presence of faults
• Renaming in an asynchronous environment
• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• Set consensus using arbitrary objects (preliminary version)
• Sharing memory robustly in message-passing systems
• Sporadic solutions to zero-one exclusion tasks
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• The BG distributed simulation algorithm
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The Committee Decision Problem
• The \(k\)-simultaneous consensus problem
• The renaming problem in shared memory systems: an introduction
• The topological structure of asynchronous computability
• The topology of shared-memory adversaries
• Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus
• Unreliable failure detectors for reliable distributed systems
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Wait-free algorithms for fast, long-lived renaming

Cited in

(3)

• A distributed computing perspective of unconditionally secure information transmission in Russian cards problems
• Structure theory of flip graphs with applications to weak symmetry breaking
• From wait-free to arbitrary concurrent solo executions in colorless distributed computing

This page was built for publication: Generalized symmetry breaking tasks and nondeterminism in concurrent objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802146)