Computing in totally anonymous asynchronous shared memory systems

DOI10.1006/inco.2001.3119zbMath1009.68012OpenAlexW1977549931MaRDI QIDQ1854512

Alla Gorbach, Shlomo Moran, Hagit Attiya

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/93b1afa9c1947beeba3a8e1135fb89ba83979609

Mathematics Subject Classification ID

Distributed systems (68M14)

Related Items

A visit to mutual exclusion in seven dates, Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms, Byzantine agreement with homonyms in synchronous systems, Computing with infinitely many processes, Agreeing within a few writes, Leader-based de-anonymization of an anonymous read/write memory, On the importance of having an identity or, is consensus really universal?, Relationships between broadcast and shared memory in reliable anonymous distributed systems, Anonymous and fault-tolerant shared-memory computing, The computational power of population protocols, Hundreds of impossibility results for distributed computing, A knowledge-based analysis of global function computation, Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers, Efficient algorithms for anonymous Byzantine agreement, Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects, Wait-free solvability of colorless tasks in anonymous shared-memory model, Byzantine agreement with homonyms, Mutual exclusion in fully anonymous shared memory systems, Fault-Tolerant Consensus with an Abstract MAC Layer., Election in fully anonymous shared memory systems: tight space bounds and algorithms, Fast rendezvous on a cycle by agents with different speeds

Cites Work

• Unnamed Item
• Bounds on shared memory for mutual exclusion
• Possibility and impossibility results in a shared memory environment
• On the space complexity of randomized synchronization
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• Computing on an anonymous ring
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• A Lower Bound on Wait-Free Counting
• Time and Space Lower Bounds for Nonblocking Implementations
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• The Wakeup Problem