Anonymous and fault-tolerant shared-memory computing

DOI10.1007/s00446-007-0042-0zbMath1266.68054OpenAlexW2067397086MaRDI QIDQ1954238

Rachid Guerraoui, Eric Ruppert

Publication date: 20 June 2013

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

Full work available at URL: http://infoscience.epfl.ch/record/269474

zbMATH Keywords

snapshotsshared memoryconsensusanonymoustimestamps

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

A visit to mutual exclusion in seven dates ⋮ The space complexity of unbounded timestamps ⋮ Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ Byzantine agreement with homonyms in synchronous systems ⋮ Agreeing within a few writes ⋮ On the uncontended complexity of anonymous agreement ⋮ Leader-based de-anonymization of an anonymous read/write memory ⋮ Uniform reliable broadcast in anonymous distributed systems with fair lossy channels ⋮ Efficient Bounded Timestamping from Standard Synchronization Primitives ⋮ The computational power of population protocols ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ A complexity-based classification for multiprocessor synchronization ⋮ Unnamed Item ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ Byzantine agreement with homonyms ⋮ Mutual exclusion in fully anonymous shared memory systems ⋮ A Tight Space Bound for Consensus ⋮ Election in fully anonymous shared memory systems: tight space bounds and algorithms

Cites Work

• Unnamed Item
• Space efficient processor identity protocol
• The processor identity problem
• Computing in totally anonymous asynchronous shared memory systems
• On the importance of having an identity or, is consensus really universal?
• Relationships between broadcast and shared memory in reliable anonymous distributed systems
• Composite registers
• Computation in networks of passively mobile finite-state sensors
• Time-space tradeoffs for implementations of snapshots
• Polylog randomized wait-free consensus
• The topological structure of asynchronous computability
• The Space Complexity of Unbounded Timestamps
• Wait-free consensus with infinite arrivals
• Atomic snapshots of shared memory
• The Las-Vegas Processor Identity Problem (How and When to Be Unique)
• Randomized wait-free concurrent objects (extended abstract)
• Distributed Computing
• Distributed Computing