A Simple Object that Spans the Whole Consensus Hierarchy
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 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 should be seen as a simple pedagogical introduction to Herlihy’s consensus hierarchy. The paper also shows that the consensus number of a ledger object is .
References
- 1. , Deterministic objects: Life beyond consensus, in Proc. 35th ACM Int. Symposium on Principles of Distributed Computing (PODC’16) (ACM Press, 2016), pp. 97–106. Google Scholar
- 2. , Distributed Computing: Fundamentals, Simulations and Advanced Topics 2nd edn. (Wiley-Interscience, 2004), 414 pp. Crossref, Google Scholar
- 3. , Help!, in Proc. 34th ACM Int. Symposium on Principles of Distributed Computing (PODC’15) (ACM Press, 2015), pp. 241–250. Google Scholar
- 4. , A complexity-based hierarchy for multiprocessor synchronization, in Proc. 35th ACM Int. Symposium on Principles of Distributed Computing (PODC’16) (ACM Press, 2016), pp. 97–106. Google Scholar
- 5. , Impossibility of distributed consensus with one faulty process, Journal of the ACM 32(2) :374–382 (1985). Crossref, ISI, Google Scholar
- 6. , Wait-free synchronization, ACM Transactions on Programming Languages and Systems 13(1) :124–149 (1991). Crossref, ISI, Google Scholar
- 7. , Power and limits of distributed computing shared memory models, Theoretical Computer Science, 509 :3–24 (2013). Crossref, ISI, Google Scholar
- 8. , Linearizability: A correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems 12(3) :463–492 (1990). Crossref, ISI, Google Scholar
- 9. , The multiplicative power of consensus numbers, in Proc. 29th ACM Int’l Symposium on Principles of Distributed Computing (PODC’10) (ACM Press, 2010), pp. 26–35. Google Scholar
- 10. , Blockchain distributed ledger technologies for biomedical and healthcare applications, Journal of the American Medical Informatics Association 24(6) :1211–1220 (2017). Crossref, ISI, Google Scholar
- 11. , On interprocess communication, Part I: Basic formalism, Distributed Computing 1(2) :77–85 (1986). Crossref, ISI, Google Scholar
- 12. , Memory requirements for agreement among unreliable asynchronous processes, Advances in Computing Research 4 :163–183 (JAI Press, 1987). Google Scholar
- 13. Distributed Algorithms (Morgan Kaufmann Pub., San Francisco (CA), 1996), 872 pp. Google Scholar
- 14. , Axioms for memory access in asynchronous hardware systems, ACM Transactions on Programming Languages and Systems 8(1) :142–153 (1986). Crossref, ISI, Google Scholar
- 15. S. Nakamoto, Bitcoin: a peer-to-peer electronic cash system (2008). https://bitcoin.org/bitcoin.pdf. Google Scholar
- 16. M. Perrin, Spécification des objets partagés dans le systèmes répartis sans attente, PhD Thesis (2016), 201 pp. Google Scholar
- 17. , Concurrent Programming: Algorithms, Principles and Foundations (Springer, 2013), 515 pp. Crossref, Google Scholar
- 18. , Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach (Springer, 2018), 550 pp. Crossref, Google Scholar
- 19. , Synchronization Algorithms and Concurrent Programming (Pearson Prentice-Hall, 2006), 423 pp. Google Scholar
- 20. , On computable numbers with an application to the Entscheidungsproblem, Proc. of the London Mathematical Society 42 :230–265 (1936). Crossref, Google Scholar
- 21. G. Wood, Ethereum: A secure decentralised generalised transaction ledger (2014). http://bitcoinaffiliatelist.com/wp-content/uploads/ethereum.pdf. Google Scholar


