Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers

DOI10.1007/s00446-017-0301-7zbMath1451.68039OpenAlexW2997829659MaRDI QIDQ1741965

Michel Raynal, Zohir Bouzid, Pierre Sutra

Publication date: 11 April 2018

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-017-0301-7

zbMATH Keywords

upper boundfault tolerancedistributed algorithmconsensusasynchronous system\(k\)-set agreementdistributed computabilityprocess crashatomic read/write registeranonymous processesbounded number of registerscolorless taskobstruction freedomrepeated \(k\)-set agreement

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items (7)

A visit to mutual exclusion in seven dates ⋮ Agreeing within a few writes ⋮ Leader-based de-anonymization of an anonymous read/write memory ⋮ A complexity-based classification for multiprocessor synchronization ⋮ Unnamed Item ⋮ Mutual exclusion in fully anonymous shared memory systems ⋮ Election in fully anonymous shared memory systems: tight space bounds and algorithms

Cites Work

• Anonymous asynchronous systems: the case of failure detectors
• Computing with infinitely many processes
• On interprocess communication. I: Basic formalism
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Specifying concurrent problems: beyond linearizability and up to tasks (extended abstract)
• Computing in totally anonymous asynchronous shared memory systems
• Anonymous and fault-tolerant shared-memory computing
• On the Space Complexity of Set Agreement
• The topological structure of asynchronous computability
• Concurrent Programming: Algorithms, Principles, and Foundations
• The complexity of obstruction-free implementations
• Fast randomized consensus using shared memory
• Contention-Sensitive Data Structures and Algorithms
• Impossibility of distributed consensus with one faulty process
• Concurrent Reading While Writing
• Concurrent reading and writing
• Atomic snapshots of shared memory
• The weakest failure detector for solving consensus
• Asynchronous Agreement and Its Relation with Error-Correcting Codes
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• The BG distributed simulation algorithm
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A tight space bound for consensus
• Distributed Computing
• On the optimal space complexity of consensus for anonymous processes
• Wait-free solvability of colorless tasks in anonymous shared-memory model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers