License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.20
URN: urn:nbn:de:0030-drops-100805
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10080/
Go to the corresponding LIPIcs Volume Portal

Nédelec, Brice ; Molli, Pascal ; Mostéfaoui, Achour

Causal Broadcast: How to Forget?

pdf-format:
LIPIcs-OPODIS-2018-20.pdf (0.7 MB)

Abstract

Causal broadcast constitutes a fundamental communication primitive of many distributed protocols and applications. However, state-of-the-art implementations fail to forget obsolete control information about already delivered messages. They do not scale in large and dynamic systems. In this paper, we propose a novel implementation of causal broadcast. We prove that all and only obsolete control information is safely removed, at cost of a few lightweight control messages. The local space complexity of this protocol does not monotonically increase and depends at each moment on the number of messages still in transit and the degree of the communication graph. Moreover, messages only carry a scalar clock. Our implementation constitutes a sustainable communication primitive for causal broadcast in large and dynamic systems.

BibTeX - Entry

@InProceedings{ndelec_et_al:LIPIcs:2018:10080,
  author =	{Brice N{\'e}delec and Pascal Molli and Achour Most{\'e}faoui},
  title =	{{Causal Broadcast: How to Forgetl}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10080},
  URN =		{urn:nbn:de:0030-drops-100805},
  doi =		{10.4230/LIPIcs.OPODIS.2018.20},
  annote =	{Keywords: Causal broadcast, complexity trade-off, large and dynamic systems}
}

Keywords: Causal broadcast, complexity trade-off, large and dynamic systems
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI