Answers are grounded in this paper and cite their sources.
The Consensus problem is a fundamental abstraction in the coordination of concurrent and distributed systems, underpinning many fault-tolerant mechanisms. Its resolution becomes particularly challenging in asynchronous environments with crash–prone and anonymous processes, where inherent limitations—such as the impossibility of symmetry breaking and the non-implementability of certain failure detectors—restrict traditional approaches. This paper addresses these challenges in the context of shared memory systems with anonymous processes under weak consistency. We present AC A C , the first deterministic algorithm that solves the Consensus problem in an asynchronous shared memory system with anonymous, crash–prone processes using a failure detector of class A ' A Ω ′ , which is implementable. To support this result, we introduce AA ' A A Ω ′ , the first algorithm that implements the A ' A Ω ′ failure detector in a partially synchronous anonymous shared memory system with crashes, and we formally prove its correctness. It is known that the classical read–write (RW) model is insufficient to implement the mechanisms required for Consensus in anonymous systems—such as counting or leader coordination—and we propose a read-modify-write model (RW+) that incorporates an increment operation under weak consistency. On top of this model, we design a fault-tolerant implementation based on message passing that preserves process anonymity. Finally, we provide an implementation of the adopt-commit object tailored to our model, which simplifies the design of the consensus algorithm AC A C . Our results demonstrate that Consensus can be achieved in anonymous asynchronous crash–prone systems by leveraging implementable failure detectors and appropriate memory abstractions, thereby advancing the state of the art in fault-tolerant concurrent and distributed computing.
No takes yet. Share an insight, caveat, or question.
Jiménez et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: