A simple object that spans the whole consensus hierarchy

DOI10.1142/S0129626418500068zbMATH Open1490.68051arXiv1802.00678OpenAlexW2963218051MaRDI QIDQ5087841FDOQ5087841

Authors: Achour Mostefaoui, Matthieu Perrin, Michel Raynal 

Publication date: 4 July 2022

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

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.

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

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

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)

Cites Work

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

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)