Sid Sen will present his research seminar/general exam on Wednesday May 20 at 1:30PM in Room 402. The members of his committee are: Mike Freedman and Bob Tarjan, co-advisors, and Jen Rexford. 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 -------- We work at the boundary of systems and theory with the goal of designing data structures and algorithms for scalable, fault-tolerant distributed systems and other applications. This talk presents foundational progress on both sides, guided by a common theme: simplicity. That is, we allow complexity in the analysis of our designs, not their implementations. On the theory side, we present two new data structures for organizing information: the rank-pairing heap and the rank-balanced tree. Rank-pairing heaps use the minimum balance information possible in arguably the simplest way, matching the performance guarantees of Fibonacci heaps with no cascading structural changes. Rank-balanced trees support insertion and deletion in O(1) amortized time and at most two rotations worst-case, improving on red-black trees. A novel analysis based on an exponential potential function shows that nodes in a rank-balanced tree are rebalanced exponentially infrequently in their heights. We are conducting a thorough experimental evaluation of these data structures, with promising preliminary results. On the systems side, we propose a simple architecture for making fault tolerant protocols scalable and efficient in the wide area. We present Prophecy, a system that interposes itself between clients and a service replica group to minimize request replication when results are historically consistent. Prophecy uses compact sketching and load-balancing to provide what we call delay-once consistency: informally, faulty nodes can return only stale (not arbitrary) data and only for an exponentially-small number of times. We have implemented Prophecy and demonstrated its high throughput and scalability compared to Byzantine fault-tolerant (BFT) and quorum-based systems. We also present a measurement study of popular websites that demonstrates a high extent of static (historically- consistent) data. Reading list ------------ Books: 1. Thomas. H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, 2nd edition, 2001. [Chapters 1-26, 34-35] 2. Andrew S. Tanenbaum and Maarten van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002. [Chapters 7-8] Papers: [1] R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6:306-318, 1985. [2] Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. [3] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. [4] M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111-129, 1986. [5] Robert E. Tarjan. Efficiency of a good but not linear set union algorithm. J. of the ACM, 22(2):215-225, 1975. [6] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. [7] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. [8] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, pages 173-186, 1999. [9] Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Edmund L. Wong. Zyzzyva: speculative byzantine fault tolerance. In SOSP, pages 45-58, 2007. [10] Yanhua Mao, Flavio Paiva Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machine for WANs. In OSDI, pages 369-384, 2008. [11] Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno Jacobsen, Nick Puz, Daniel Weaver, and Ramana Yerneni. PNUTS: Yahoo!'s hosted data serving platform. VLDB, 1(2):1277-1288, 2008. [12] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon's highly available key-value store. In SOSP, pages 205-220, 2007.