We identify three key challenges in designing large-scale fault tolerant services. The first is keeping stable best-case performance in presence of failures, which are increasingly becoming commonplace. The second is that worst-case failures should not result in major service disruptions and needs to be tolerated. The third is minimizing the costs of replicating a large number of services. While most previous work has focused on addressing the first two challenges, we propose new approaches to reduce the replication costs of BFT replication in large-scale services. © ACM 2008.