2026-08-13T03:07:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10080 2024-03-06T10:45:34Z ddc:004 open_access

Causal Broadcast: How to Forget? Nédelec, Brice Molli, Pascal Mostéfaoui, Achour Causal broadcast complexity trade-off large and dynamic systems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Brice Nédelec and Pascal Molli and Achour Mostéfaoui 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.20 urn:nbn:de:0030-drops-100805 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode