Semantically Reliable Broadcast: Sustaining High Throughput in Reliable Distributed Systems.

J. Pereira, L. Rodrigues and R. Oliveira

This report will be published as a chapter of the following book: Concurrency in Dependable Computing, Paul Ezhilchelvan and Alexander Romanovsky (eds.), Chapter 10. 2002 Kluwer Academic Publishers. (to appear)


Replicated services are often required to sustain high loads of multiple concurrent requests. This requirement is hard to balance with strong consistency. Typically, to ensure inter-replica consistency, all replicas should receive all updates. Unfortunately, in this case, a single slow replica may degrade the performance of the whole system. This paper proposes a novel reliable broadcast primitive that uses semantic knowledge to weaken reliable delivery guarantees while, at the same time, ensuring strong consistency at the semantic level. By allowing some obsolete messages to be dropped, the protocol that implements this primitive is able to sustain a higher throughput than a fully reliable broadcast protocol. The usefulness of the primitive and the performance of the protocol are illustrated through a concrete example.

Not available online

Luís Rodrigues