Efficient Byzantine-Resilient Reliable Multicast on a Hybrid Failure Model

Miguel Correia, Lau Cheuk Lung, Nuno Ferreira Neves, Paulo Veríssimo

21st Symposium on Reliable Distributed Systems, Suita, Japan, October 2002

Keywords: Intrusion Tolerance, Fault-Tolerant Protocols, Secure Systems, Distributed Fault-Tolerance, Byzantine Protocols, Security, Dependability

Abstract

The paper presents a new reliable multicast protocol that tolerates arbitrary faults, including Byzantine faults. This protocol is developed using a novel way of designing secure protocols which is based on a well-founded hybrid failure model. Despite our claim of arbitrary failure resilience, the protocol
needs not necessarily incur the cost of ``Byzantine agreement'', in number of participants and round/message complexity. It can rely on the existence of a simple distributed security kernel -- the TTCB -- where the participants only execute crucial parts of the protocol operation, under the protection of a crash failure model. Otherwise, participants follow an arbitrary failure model.

The TTCB provides only a few basic services, which allow our protocol to have an efficiency similar to that of accidental fault-tolerant protocols: for f faults, our protocol requires f+2 processes, instead of 3f+1 in Byzantine systems. Besides, the TTCB (which is synchronous) allows secure operation of timed protocols, despite the unpredictable time behavior of the environment (possibly due to attacks on timing assumptions).

BibTeX

@InProceedings{Correia:02b,
    author = "M. Correia and L. C. Lung and N. F. Neves and P. Ver\'{\i}ssimo",
    title       = "Efficient Byzantine-Resilient Reliable Multicast on a Hybrid Failure Model",
    booktitle = "Proc. of the 21st Symposium on Reliable Distributed Systems",
    address = "Suita, Japan",
    month       = oct,
    year    = 2002
}

Extended report

Download the zip postscript or the postscript .