João Carlos Antunes Leitão


Gossip-Based Broadcast Protocols


Tese submetida para provas de mestrado em Engenharia Informática Departamento de Informática Faculdade de Ciências da Universidade de Lisboa, Maio de 2007.

Abstract

Gossip, or epidemic, protocols have emerged as a powerful strategy to implement highly scalable and resilient reliable broadcast primitives. Due to scalability reasons, each participant in a gossip protocol maintains only a partial view of the system, from which they select peers to perform gossip exchanges. On the other hand the natural redundancy of gossip protocols makes them less efficient than other approaches that rely in some sort of structured overlay network.

The thesis addresses gossip protocols and the problem of building partial views to support their operation. For that purpose, the thesis presents and evaluates a new scalable membership protocol, which is called HyParView, that provides a number of properties, such as degree distribution, accuracy and clustering coefficient, that are highly useful to the construction of efficient gossip protocols.

The thesis also introduce two new gossip protocols, based on HyParView, that provide high reliability with small message redundancy. One is an eager push gossip protocol while the other is a tree based gossip broadcast protocol. Simulations results show that, in comparison with other existing protocols, HyParView-based gossip protocols not only provide better reliability but also support higher percentages of node failures, and are able to recover faster from these failures.


Publicações

Gossip-Based Broadcast Protocols.
J. Leitão
Tese de Mestrado. Departamento de Informática Faculdade de Ciências da Universidade de Lisboa
Maio, 2007.
Available BibTeX, thesis (pdf).
HyParView: a membership protocol for reliable gossip-based broadcast.
J. Leitão, J. Pereira, and L. Rodrigues.
Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. Edinburgh, UK, June, 2007.
Available BibTeX, abstract (html) and report (pdf).
Epidemic Broadcast Trees.
J. Leitão, J. Pereira, and L. Rodrigues.
Proceedings of the 26th IEEE International Symposium on Reliable Distributed Systems. Beijing, China, October 10-12, 2007.
Available BibTeX, abstract (html) and report (pdf).

Localização actual

O João Leitão é investigador do INESC-ID. Veja a sua página para mais pormenores.


Luís Rodrigues