World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Simple Object that Spans the Whole Consensus Hierarchy

    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. Y. Afek, F. Ellen and R. Gafni, 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. H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics 2nd edn. (Wiley-Interscience, 2004), 414 pp. CrossrefGoogle Scholar
    • 3. K. Censor-Hillel, E. Petrank and S. Timnat, Help!, in Proc. 34th ACM Int. Symposium on Principles of Distributed Computing (PODC’15) (ACM Press, 2015), pp. 241–250. Google Scholar
    • 4. F. Ellen, R. Gelashvili, N. Shavit and L. Zhu, 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. M. J. Fischer, N. A. Lynch and M. S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM 32(2) :374–382 (1985). Crossref, ISIGoogle Scholar
    • 6. M. P. Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems 13(1) :124–149 (1991). Crossref, ISIGoogle Scholar
    • 7. M. Herlihy, S. Rajsbaum and M. Raynal, Power and limits of distributed computing shared memory models, Theoretical Computer Science, 509 :3–24 (2013). Crossref, ISIGoogle Scholar
    • 8. M. P. Herlihy and J. M. Wing, Linearizability: A correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems 12(3) :463–492 (1990). Crossref, ISIGoogle Scholar
    • 9. D. Imbs and M. Raynal, 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. T. T. Kuo, H. E. Kim and L. Ohno-Machado, Blockchain distributed ledger technologies for biomedical and healthcare applications, Journal of the American Medical Informatics Association 24(6) :1211–1220 (2017). Crossref, ISIGoogle Scholar
    • 11. L. Lamport, On interprocess communication, Part I: Basic formalism, Distributed Computing 1(2) :77–85 (1986). Crossref, ISIGoogle Scholar
    • 12. M. Loui and H. Abu-Amara, Memory requirements for agreement among unreliable asynchronous processes, Advances in Computing Research 4 :163–183 (JAI Press, 1987). Google Scholar
    • 13. N. A. Lynch Distributed Algorithms (Morgan Kaufmann Pub., San Francisco (CA), 1996), 872 pp. Google Scholar
    • 14. J. Misra, Axioms for memory access in asynchronous hardware systems, ACM Transactions on Programming Languages and Systems 8(1) :142–153 (1986). Crossref, ISIGoogle 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. M. Raynal, Concurrent Programming: Algorithms, Principles and Foundations (Springer, 2013), 515 pp. CrossrefGoogle Scholar
    • 18. M. Raynal, Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach (Springer, 2018), 550 pp. CrossrefGoogle Scholar
    • 19. G. Taubenfeld, Synchronization Algorithms and Concurrent Programming (Pearson Prentice-Hall, 2006), 423 pp. Google Scholar
    • 20. A. M. Turing, On computable numbers with an application to the Entscheidungsproblem, Proc. of the London Mathematical Society 42 :230–265 (1936). CrossrefGoogle Scholar
    • 21. G. Wood, Ethereum: A secure decentralised generalised transaction ledger (2014). http://bitcoinaffiliatelist.com/wp-content/uploads/ethereum.pdf. Google Scholar