José Orlando Roque Nascimento Pereira

Semantically Reliable Grup Communication.

Dissertação submetida para provas de doutoramento em Informática Departamento de Informática, Faculdade do Minho, Julho de 2002.


Current usage of computers and data communication networks for a variety of daily tasks, calls for widespread deployment of fault tolerance techniques with inexpensive off-the-shelf hardware and software. Group communication is in this context a particularly appealing technology, as it provides to the application programmer reliability guarantees that highly simplify many fault tolerance techniques.

It has however been reported that the performance of group communication toolkits in large and heterogeneous systems is frequently disappointing. Although this can be overcome by relaxing reliability guarantees, the resulting protocol is often much less useful than group communication, in particular, for strong consistent replication. The challenge is thus to relax reliability and still provide a convenient set of guarantees for fault tolerant programming.

This thesis addresses models and mechanisms that by selectively relaxing reliability guarantees, offer both the convenience of group communication for fault tolerant programming and high performance. The key to our proposal is to use knowledge about the semantics of messages exchanged to determine which messages need to be reliably delivered, hence semantic reliability. In many applications, some messages implicitly convey or overwrite other messages sent recently before, making them obsolete while still in transit. By omitting only the delivery of obsolete messages, performance can be improved without impact in the correctness of the application.

Specifications and algorithms for a complete semantically reliable group communication protocol suite are introduced, encompassing ordered and view synchronous multicast. The protocols are then evaluated with analytical and simulation models and with a prototype implementation. The discussion of a concrete application illustrates the resulting programming interface and performance.

Selected Publications

Semantically Reliable Multicast: Definition, Implementation and Performance Evaluation.
J. Pereira, L. Rodrigues and R. Oliveira.
IEEE Transactions on Computers, Special Issue on Reliable Distributed Systems, 2003 (to appear).
Available BibTeX, abstract (html).
Semantically Reliable Grup Communication
J. Pereira.
PhD Thesis. Departamento de Informática da Universidade do Minho
Julho, 2002.
Available pdf.
Reducing the Cost of Group Communication with Semantic View Synchrony.
J. Pereira, L. Rodrigues and R. Oliveira
In Proceedings of The International Conference on Dependable Systems and Networks (DSN), pp. 293-302, Washington, DC, June, 2002.
Available BibTeX, abstract and extended report(gzip postscript), (pdf).
Semantically Reliable Broadcast: Sustaining High Throughput in Reliable Distributed Systems.
J. Pereira, L. Rodrigues and R. Oliveira
In Concurrency in Dependable Computing, Paul Ezhilchelvan and Alexander Romanovsky (eds.), Chapter 10. 2002 Kluwer Academic Publishers, June 2002, ISBN 1-4020-7043-8.
Available BibTeX, abstract.
Semantically Reliable Multicast Protocols
J. Pereira, L. Rodrigues and R. Oliveira.
in Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems, pp. 60-69, Nurnberg, Germany, October 2000.
Available BibTeX, abstract (html) and extended report (gzip postscript), (pdf).


Luís Rodrigues