[talks] S Sen general exam

Melissa Lawson mml at CS.Princeton.EDU
Thu May 14 14:05:37 EDT 2009


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.



More information about the talks mailing list