DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.20

Causal Broadcast: How to Forget?

Authors: Brice Nédelec, Pascal Molli, and Achour Mostéfaoui

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

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.

Cite as

Brice Nédelec, Pascal Molli, and Achour Mostéfaoui. Causal Broadcast: How to Forget?. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nedelec_et_al:LIPIcs.OPODIS.2018.20,
  author =	{N\'{e}delec, Brice and Molli, Pascal and Most\'{e}faoui, Achour},
  title =	{{Causal Broadcast: How to Forget?}},
  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 =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.20},
  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}
}

Search Results

Documents authored by Nédelec, Brice

Causal Broadcast: How to Forget?

Abstract

Cite as

Thanks for your feedback!

Could not send message