How to Tolerate Half Less One Byzantine Nodes in Practical Distributed Systems

Miguel Correia, Nuno Ferreira Neves, Paulo Veríssimo

In Proceedings of the 23rd IEEE Symposium on Reliable Distributed Systems. Florianopolis, Brasil, pages 174-183, October 2004.


Keywords: Intrusion Tolerance, Fault-Tolerant Protocols, Active Replication, State Machine Approach, Secure Systems, Distributed Fault-Tolerance, Byzantine Protocols, Security, Dependability


Abstract

The application of dependability concepts and techniques to the design of secure distributed systems is raising a considerable amount of interest in both communities under the designation of intrusion tolerance. However, practical intrusion-tolerant replicated systems based on the state machine approach (SMA) can handle at most f Byzantine components out of a total of n = 3f + 1, which is the maximum resilience in asynchronous systems.

This paper extends the normal asynchronous system with a special distributed oracle called TTCB. Using this extended system we manage to implement an intrusion-tolerant service based on the SMA with only 2f + 1 replicas. Albeit a few other papers in the literature present intrusion-tolerant services with this approach, this is the first time the number of replicas is reduced from 3f + 1 to 2f + 1. Another interesting characteristic of the described service is a low time complexity.
 


BibTeX

@InProceedings{srds:04,
    author = "M. Correia and N. F. Neves and P. Ver\'{\i}ssimo",
    title = "How to Tolerate Half Less One {B}yzantine Nodes in Practical Distributed Systems ",
    booktitle = "Proceedings of the 23rd {IEEE} Symposium on Reliable Distributed Systems",
    year = "2004",
    pages = "174--183",
    month = oct
}


Preprint

Download the pdf.