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.
