Date Added: Jun 2010
Existing Byzantine-resilient replication protocols satisfy two standard correctness criteria, safety and liveness, even in the presence of Byzantine faults. The runtime performance of these protocols is most commonly assessed in the absence of processor faults and is usually good in that case. However, in some protocols faulty processors can significantly degrade performance, limiting the practical utility of these protocols in adversarial environments. This paper demonstrates the extent of performance degradation possible in some existing protocols that do satisfy liveness and that do perform well absent Byzantine faults. The authors propose a new performance oriented correctness criterion that requires a consistent level of performance, even when the system exhibits Byzantine faults.