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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Implementable consensus in anonymous asynchronous systems with non-atomic shared memory

José Luis López-Presa, Ernesto Jiménez, Marta Moreno-Cuesta, Marta Patiño-Martínez
The Journal of Supercomputing
Distributed systems and fault tolerance
article

Implementable consensus in anonymous asynchronous systems with non-atomic shared memory

José Luis López-Presa, Ernesto Jiménez, Marta Moreno-Cuesta, Marta Patiño-Martínez
article en

Abstract

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.

The Journal of SupercomputingVol. 82(17)
Universidad Politécnica de Madrid (ES)
European Commission, Ministerio de Asuntos Económicos y Transformación Digital, Gobierno de España, Agencia Estatal de Investigación, NextGenerationEU
Distributed systems and fault tolerance
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon