A simple object that spans the whole consensus hierarchy

DOI10.1142/S0129626418500068MaRDI QIDQ5087841zbMATH OpenOpenAlexFDO

Authors Achour Mostefaoui, Matthieu Perrin, Michel Raynal

Publication date 4 July 2022

Published in Parallel Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.00678

zbMATH Keywords

asynchronous systemdistributed computabilityprocess crashatomic registerconsensus numberledger object

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Abstract: This paper presents a simple generalization of the basic atomic read/write register object, whose genericity parameter spans the whole set of integers and is such that its k-parameterized instance has exactly consensus number k. This object, whose definition is pretty natural, is a sliding window register of size k. Its interest lies in its simplicity and its genericity dimension which provides a global view capturing the whole consensus hierarchy. Hence, this short article must be seen as a simple pedagogical introduction to Herlihy's consensus hierarchy.

Recommendations

• An informal visit to the wonderful land of consensus numbers and beyond
• On the viability of the deterministic consensus hierarchy
• scientific article; zbMATH DE number 7561269
• Determining Consensus Numbers
• A note on atomicity: boosting Test\&Set to solve consensus

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• Axioms for memory access in asynchronous hardware systems
• Concurrent programming: algorithms, principles, and foundations.
• Deterministic objects: life beyond consensus
• Fault-tolerant message-passing distributed systems. An algorithmic approach
• Impossibility of distributed consensus with one faulty process
• On interprocess communication. I: Basic formalism
• Power and limits of distributed computing shared memory models
• The multiplicative power of consensus numbers

Cited in

(2)

• Less Is More: Consensus Gaps Between Restricted and Unrestricted Objects
• An informal visit to the wonderful land of consensus numbers and beyond

This page was built for publication: A simple object that spans the whole consensus hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087841)