DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.34

Analysis of Bounds on Hybrid Vector Clocks

Authors: Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{yingchareonthawornchai_et_al:LIPIcs.OPODIS.2015.34,
  author =	{Yingchareonthawornchai, Sorrachai and Kulkarni, Sandeep S. and Demirbas, Murat},
  title =	{{Analysis of Bounds on Hybrid Vector Clocks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.34},
  URN =		{urn:nbn:de:0030-drops-66771},
  doi =		{10.4230/LIPIcs.OPODIS.2015.34},
  annote =	{Keywords: Vector Clocks, Physical Clocks, Large Scale Systems}
}

Search Results

Documents authored by Demirbas, Murat

Analysis of Bounds on Hybrid Vector Clocks

Abstract

Cite as

Thanks for your feedback!

Could not send message