Generalized symmetry breaking tasks and nondeterminism in concurrent objects

DOI10.1137/130936828zbMATH Open1338.68020OpenAlexW2336858153MaRDI QIDQ2802146FDOQ2802146

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Distributed systems (68M14)

Cites Work

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

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)