A Communication-Efficient Causal Broadcast Protocol

Abstract : A causal broadcast ensures that messages are delivered to all nodes (processes) preserving causal relation of the messages. In this paper, we propose a causal broadcast protocol for distributed systems whose nodes are logically organized in a virtual hypercube-like topology called VCube. Messages are broadcast by dynamically building spanning trees rooted in the message's source node. By using multiple trees, the contention bottleneck problem of a single root spanning tree approach is avoided. Furthermore , different trees can intersect at some node. Hence, by taking advantage of both the out-of-order reception of causally related messages at a node and these paths intersections, a node can delay to one or more of its children in the tree, the forwarding of the messages whose some causal dependencies it knows that the children in question can not satisfy yet. Such a delay does not induce any overhead. Experimental evaluation conducted on top of PeerSim simulator confirms the communication effectiveness of our causal broadcast protocol in terms of latency and message traffic reduction.
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal.inria.fr/hal-01924741
Contributor : Pierre Sens <>
Submitted on : Friday, November 16, 2018 - 11:27:01 AM
Last modification on : Friday, July 5, 2019 - 3:26:03 PM
Long-term archiving on : Sunday, February 17, 2019 - 1:34:35 PM

File

icpp2018-hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01924741, version 1

Citation

João Paulo de Araujo, Luciana Arantes, Elias Duarte Júnior, Luiz Rodrigues, Pierre Sens. A Communication-Efficient Causal Broadcast Protocol. ICPP 2018 - 47th International Conference on Parallel Processing, Aug 2018, Eugene, Oregon, United States. ⟨hal-01924741⟩

Share

Metrics

Record views

82

Files downloads

350