Document Open Access Logo

Analysis of Bounds on Hybrid Vector Clocks

Authors Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, Murat Demirbas

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.34.pdf
  • Filesize: 0.88 MB
  • 17 pages

Document Identifiers

Author Details

Sorrachai Yingchareonthawornchai
Sandeep S. Kulkarni
Murat Demirbas

Cite As Get BibTex

Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas. Analysis of Bounds on Hybrid Vector Clocks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.34

Abstract

Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases.

Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.

Subject Classification

Keywords
  • Vector Clocks
  • Physical Clocks
  • Large Scale Systems

Metrics

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

References

  1. J. Almeida, P. Almeida S. Paulo, and C. Baquero. Bounded version vectors. Distributed Computing: 18th International Conference, DISC 2004, pages 102-116, 2004. Google Scholar
  2. M. Bravo, N. Diegues, J. Zeng, P. Romano, and L. Rodrigues. On the use of clocks to enforce consistency in the cloud. IEEE Data Eng. Bull, 38(1):18-31, 2015. Google Scholar
  3. B. Charron-Bost. Concerning the size of logical clocks in distributed systems. Inf. Process. Lett., 39(1):11-16, 1991. Google Scholar
  4. Cockroachdb: A scalable, transactional, geo-replicated data store. http://cockroachdb.org/. Google Scholar
  5. J. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, JJ. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google’s globally-distributed database. Proceedings of OSDI, 2012. Google Scholar
  6. M. Demirbas and S. Kulkarni. Beyond truetime: Using augmentedtime for improving google spanner. LADIS'13: 7th Workshop on Large-Scale Distributed Systems and Middleware, 2013. Google Scholar
  7. J. Du, S. Elnikety, A. Roy, and W. Zwaenepoel. Orbe: Scalable causal consistency using dependency matrices and physical clocks. In Proceedings of the 4th Annual Symposium on Cloud Computing, SOCC'13, pages 11:1-11:14, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2523616.2523628.
  8. R. Escriva, A. Dubey, B. Wong, and E.G. Sirer. Kronos: The design and implementation of an event ordering service. EuroSys, 2014. Google Scholar
  9. M. Ahamad F. J. Torres-Rojas. Plausible clocks: Constant size logical clocks for distributed systems. Proceedings of WDAG, pages 71-88, 1996. Google Scholar
  10. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference, 10(1):56-66, Feb 1988. Google Scholar
  11. S. Kulkarni, M. Demirbas, D. Madappa, B. Avva, and M. Leone. Logical physical clocks. In Principles of Distributed Systems, pages 17-32. Springer, 2014. Google Scholar
  12. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558-565, July 1978. Google Scholar
  13. F. Mattern. Virtual time and global states of distributed systems. Parallel and Distributed Algorithms, pages 215-226, 1989. Google Scholar
  14. S. Meldal, S. Sankar, and J. Vera. Exploiting locality in maintaining potential causality. In Proceedings of Principles of Distributed Computing (PODC), pages 231-239, 1991. URL: http://dx.doi.org/10.1145/112600.112620.
  15. D. Mills. A brief history of ntp time: Memoirs of an internet timekeeper. ACM SIGCOMM Computer Communication Review, 33(2):9-21, 2003. Google Scholar
  16. D. S. Parker, G. J. Popek, G. Rudisin, A. Stoughton, B. J. Walker, E. Walton, J. M. Chow, D. Edwards, S. Kiser, and C. Kline. Detection of mutual inconsistency in distributed systems. IEEE Transactions on Software Engineering, SE-9(3):240-247, May 1983. URL: http://dx.doi.org/10.1109/TSE.1983.236733.
  17. Y. Saito. Unilateral version vector pruning using loosely synchronized clocks. Technical report, HP Labs, 2002. Google Scholar
  18. M. Singhal and A. Kshemkalyani. An efficient implementation of vector clocks. Information Processing Letters, 43:47-52, 1992. Google Scholar
  19. W. Vogels. Eventually consistent. Communications of the ACM, 52(1):40-44, 2009. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact