文章基本信息

标题：Causal Broadcast: How to Forget?
本地全文：下载
作者：Brice Ndelec ; Pascal Molli ; Achour Mostfaoui 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：125
页码：1-16
DOI：10.4230/LIPIcs.OPODIS.2018.20
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Causal broadcast; complexity trade-off; large and dynamic systems