Date Added: Sep 2010
The popularity of wide-area computer services has generated a compelling need for efficient algorithms that provide high reliability. Byzantine Fault-Tolerant (BFT) algorithms can be used with this purpose because they allow replicated systems to continue to provide a correct service even when some of their replicas fail arbitrarily, either accidentally or due to malicious faults. Current BFT algorithms perform well on LANs but when the replicas are distributed geographically their performance is affected by the lower bandwidth and the higher and more heterogeneous network latencies. This paper proposes and evaluates a novel BFT algorithm for WANs that requires fewer communication steps, fewer replicas and has better throughput and latency than others in the literature.