Válter Emanuel Trecitano da Costa Santos

Localized Reliable Causal Multicast

Tese submetida para provas de mestrado em Engenharia Informática e de Computadores Instituto Superior Técnico, Universidade de Lisboa.


This thesis addresses the problem of offering reliable causal multicast in a setting where nodes are or- ganized in an overlay network and use this network to disseminate information among each other. The use of overlay networks for this purpose is widely used when the number of nodes is large. For instance, many publish-subscribe system use an overlay of message brokers to support the exchange of informa- tion among publishers and subscribers. To the best of our knowledge, previous multicast algorithms for overlay networks either do not enforce causal order or, in order to do so, require nodes to keep metadata (for instance, sequence numbers) for all senders and are, therefore, inherently non-scalable. In this the- sis we propose a novel localized algorithm to implement reliable causal multicast, where each node is only required to keep metadata regarding nodes in its neighbourhood (with a radius that is a function of the number of faults that need to be tolerated). Experimental results show that our algorithm can achieve significant improvements over non-localized alternatives, and can even outperform localized algorithms that do not offer causal order.


Localized Reliable Causal Multicast
Válter Emanuel Trecitano da Costa Santos
MSc Thesis. Instituto Superior Técnico, Universidade de Lisboa.
November, 2019.
Available BibTeX, MSC Thesis, and extended abstract, and mid-term report.
Difusão em Grupo Tolerante a Faltas com Ordem Causal Usando Informação Localizada.
V. Santos and L. Rodrigues
Actas do décimo primeiro Simpósio de Informática (Inforum), Guimarães, Portugal, Sep. 2019.
Available BibTeX, extended report (pdf).
Localized Reliable Causal Multicast.
V. Santos and L. Rodrigues.
Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA 2017), Cambridge (MA), USA, September 2019.

Luís Rodrigues