Tolerating Byzantine Faulty Clients in a Quorum System

Download: pdf .

“Tolerating Byzantine Faulty Clients in a Quorum System” by Barbara Liskov and Rodrigo Rodrigues. In Proceedings of the 26th IEEE International Confererence on Distributed Computing SYstems (ICDCS06), (Lisbon, Portugal), July 2006.

Abstract

Byzantine quorum systems have been proposed that work properly even when up to f replicas fail arbitrarily. How- ever, these systems are not so successful when confronted with Byzantine faulty clients. This paper presents novel protocols that provide atomic semantics despite Byzantine clients. Our protocols prevent Byzantine clients from interfering with good clients: bad clients cannot prevent good clients from completing reads and writes, and they cannot cause good clients to see inconsistencies. In addition we also prevent bad clients that have been removed from operation from leaving behind more than a bounded number of writes that could be done on their behalf by a colluder. Our protocols are designed to work in an asynchronous system like the Internet and they are highly efcient. We require 3f + 1 replicas, and either two or three phases to do writes; reads normally complete in one phase and require no more than two phases, no matter what the bad clients are doing. We also present strong correctness conditions for systems with Byzantine clients that limit what can be done on behalf of bad clients once they leave the system. Furthermore we prove that our protocols are both safe (they meet those conditions) and live.

Download: pdf .

BibTeX entry:

@inproceedings{ICDCS06,
   author = {Barbara Liskov and Rodrigo Rodrigues},
   title = {Tolerating Byzantine Faulty Clients in a Quorum System},
   booktitle = {Proceedings of the 26th IEEE International Confererence on
	Distributed Computing SYstems (ICDCS06)},
   address = {Lisbon, Portugal},
   month = jul,
   year = {2006}
}