Wyatt Lloyd will present his research seminar/general exam on Friday May 8 at 10AM in Room 302 (note room). The members of his committee are: Mike Freedman, advisor, Jennifer Rexford, and Larry Peterson. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------------------------- Abstract: Byzantine fault-tolerant (BFT) replication, while offering robustness in the face of arbitrary failures, arguably has not been widely adopted due to its performance overhead. System designers often opt for protocols that sacrifice consistency or avoid replicating work, at the cost of correctness in the face of failures. By using historical information, however, I will argue that stronger consistency and high performance are not mutually exclusive. This talk will present Prophecy, a system that interposes itself between clients and any replicated service to minimize request replication when results are historically consistent. At the core of Prophecy is a trusted sketcher component, designed to replace the semi-trusted load balancer that mediates access to a service. The sketcher maintains a compact history table of request/response pairs that allows it to perform fast, load-balanced reads when state transitions do not occur, and slow, replicated reads otherwise. Despite its simplicity, the sketcher provides a new form of consistency called delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. A prototype implementation demonstrates Prophecy's high throughput compared to BFT systems, and its competitiveness with traditional load-balancing. I will also describe and evaluate Prophecy's ability to scale-out to support large replica groups. As Prophecy is most effective when state transitions are rare, I will finally present a measurement study of popular websites that demonstrates a high extent of static data. Reading List: __Papers__ [1] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Sys., 4(3), 1982. [2] Castro, M. and Liskov, B. Practical byzantine fault tolerance. In OSDI, 1999. [3] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine fault tolerance. In SOSP, 2007. [4] A. Clement, E. Wong, L. Alvisi, and M. Dahlin. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In NSDI, 2009. [5] M. P. Herlihy, and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Sys. 12(3), 1990. [6] B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. In VLDB, 2008. [7] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, 2007. [8] Fitzpatrick, B. 2004. Distributed caching with memcached. Linux Journal, 124, 2004. [9] J. Karlin, S. Forrest, and J. Rexford. Pretty Good BGP: Improving BGP by cautiously adopting routes. In ICNP, Nov. 2006. [10] L. Poole, and V.S. Pai. ConfiDNS: leveraging scale and history to detect compromise. In USENIX Annual, June 2008. __Textbook__ K. P. Birman, Reliable Distributed Systems, Springer, 2008. Part III and Chapter 24.6.