How to tolerate half less one byzantine nodes in practical distributed systems

Miguel Correia, Nuno Ferreira Neves, Paulo Veríssimo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

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 3/ + 1 to 2f + 1. Another interesting characteristic of the described service is a low time complexity. © 2004 IEEE.
Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Symposium on Reliable Distributed Systems
PublisherIEEE Computer Society
Pages174-183
Number of pages10
DOIs
StatePublished - Jan 1 2004
Externally publishedYes

Cite this