Computationally Light "Multi-Speed" Atomic Memory

Authors Antonio Fernández Anta, Theophanis Hadjistasi, Nicolas Nicolaou



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.29.pdf
  • Filesize: 1.06 MB
  • 17 pages

Document Identifiers

Author Details

Antonio Fernández Anta
Theophanis Hadjistasi
Nicolas Nicolaou

Cite AsGet BibTex

Antonio Fernández Anta, Theophanis Hadjistasi, and Nicolas Nicolaou. Computationally Light "Multi-Speed" Atomic Memory. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.29

Abstract

Communication demands are usually the leading factor that defines the efficiency of operations on a read/write shared memory emulation in the message-passing environment. In the quest for minimizing the communication demands, the algorithms proposed either require restrictions in the system or incur high computation demands. As a result, such solutions may be not suitable to be used in practice. In this paper we focus on the practicality of implementations of atomic read/write shared memory emulation in the message-passing environment. In particular we investigate implementations that reduce both communication and computation demands. We first examine the shortcomings of the best two (in terms of communication demands) known algorithms that implement atomic single-writer multiple-reader (SWMR) atomic memory. The algorithm ccFast proposed by A. Fernández et al., achieves optimal communication by allowing each operation to complete in one round trip, with light computation requirements. Unfortunately, it relies on strict limitations on the number of readers. On the other hand, algorithm OhSam, imposes no restrictions on the system, but provides operations that require one and a half communication rounds. In the light of these shortcomings, we present two algorithms that implement multi-speed operations with light computation, and without imposing any restriction on the system. In particular, algorithm ccHybrid adopts the fast (one-round) writes and makes clients to switch to a slow (two-round) mode whenever the system is congested. On the other hand, algorithm OhFast, pushes the responsibility of deciding for the speed switch to the servers. This allows the algorithm to utilize the fast operations, and the slow one-and-a-half-rounds operations of the algorithm presented by T. Hadjistasi et al., whenever is necessary. We prove that both new algorithms preserve atomicity. To evaluate the new algorithms we implement five different atomic memory algorithms in the NS3 simulator, and we compare their performance in terms of operation latency, and ratio of slow over fast operations performed. We test the algorithms over different: (i) topologies, and (ii) operation loads. Our results support that the newly presented algorithms increase the practicality of atomic read/write atomic shared memory implementations in the message-passing, asynchronous environment.
Keywords
  • atomicity
  • read/write objects
  • shared memory
  • operation latency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message passing systems. Journal of the ACM, 42(1):124-142, 1996. Google Scholar
  2. P. Dutta, R. Guerraoui, R. R. Levy, and A. Chakraborty. How fast can a distributed atomic read be? In Proceedings of the 23rd ACM symposium on Principles of Distributed Computing (PODC04), pages 236-245, 2004. Google Scholar
  3. A. Fernández Anta, N. Nicolaou, and A. Popa. Making "fast" atomic operations computationally tractable. In Proceedings 19th International Conference On Principle Of DIstributed Systems (OPODIS 15), 2015. Google Scholar
  4. Chryssis Georgiou, Nicolas C. Nicolaou, and Alexander A. Shvartsman. On the robustness of (semi) fast quorum-based implementations of atomic shared memory. In DISC'08: Proceedings of the 22nd international symposium on Distributed Computing, pages 289-304, Berlin, Heidelberg, 2008. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-540-87779-0_20.
  5. Chryssis Georgiou, Nicolas C. Nicolaou, and Alexander A. Shvartsman. Fault-tolerant semifast implementations of atomic read/write registers. Journal of Parallel and Distributed Computing, 69(1):62-79, 2009. URL: http://dx.doi.org/10.1016/j.jpdc.2008.05.004.
  6. T. Hadjistasi, N. Nicolaou, and A. A. Schwarzmann. Brief announcement: Oh-ram! one and a half round read/write atomic memory. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC'16, pages 353-355, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933057.2933073.
  7. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. URL: http://dx.doi.org/10.1145/78969.78972.
  8. Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess progranm. IEEE Transactions on Computers, 28(9):690-691, 1979. URL: http://dx.doi.org/10.1109/TC.1979.1675439.
  9. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996. Google Scholar
  10. Nancy A. Lynch and Alexander A. Shvartsman. Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. In Proceedings of Symposium on Fault-Tolerant Computing, pages 272-281, 1997. Google Scholar
  11. NS3 network simulator. URL: https://www.nsnam.org/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail