Implementable consensus in anonymous asynchronous systems with non-atomic shared memory
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 $$\mathcal {A}_C$$ 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\varOmega '$$ A Ω ′ , which is implementable. To support this result, we introduce $$\mathcal {A}_{A\varOmega '}$$ A A Ω ′ , the first algorithm that implements the $$A\varOmega '$$ 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 $$\mathcal {A}_C$$ 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.
Authors
- José Luis López-Presa (ORCID: https://orcid.org/0000-0003-3050-1212)
- Ernesto Jiménez (ORCID: https://orcid.org/0000-0003-2006-2690)
- Marta Moreno-Cuesta (ORCID: https://orcid.org/0009-0001-0885-7450)
- Marta Patiño-Martínez (ORCID: https://orcid.org/0000-0003-2997-3722)
Institutions
- Universidad Politécnica de Madrid (ES)
Publication Details
- Journal
- The Journal of Supercomputing
- Published
- 2026-11-18
- DOI
- https://doi.org/10.1007/s11227-026-08955-y
- Primary Topic
- Distributed systems and fault tolerance
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- European Commission
- Ministerio de Asuntos Económicos y Transformación Digital, Gobierno de España
- Agencia Estatal de Investigación
- NextGenerationEU