Christopher Hodsdon will present his general exam on Tuesday, January 22, 2019 at 3pm in CS 302.  The members of his committee are as follows: Wyatt Lloyd (Adviser), Michael Freedman, and Amit Levy. 

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.

Title: "Holeless, Fault Tolerant, and Scalable Sequencing"

Abstract:

Some recent distributed systems use a monolithic sequencer, a single server handing out sequence numbers, as a building block for ordering operations in the system. Monolithic sequencers can simplify the design of distributed systems by replacing complex distributed ordering protocols, such as two-phase locking and Paxos, with a single round trip to the sequencer. Sequencers can also improve system throughput by ordering operations before they are executed, reducing contention. However, existing monolithic sequencers have two limitations. First, they allow holes in the sequence, which makes it difficult to build correct and efficient systems. Second, they impose a scalability ceiling on the system.

We present CATS, a sequencing subsystem that overcomes these limitations while still providing the simplicity and throughput benefits of a monolithic sequencer. CATS provides a holeless sequence with a specialized reliable transport protocol, a sequencer recovery protocol, and a replicated layer of proxies interposed between clients and the sequencer. CATS also leverages the replicated layer of proxies to provide infinitely scalable throughput through two complementary scaling mechanisms.

-------

Reading List:

Balakrishnan, Mahesh, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobber, Michael Wei, and John D. Davis. "Corfu: A shared log design for flash clusters." In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation, pp. 1-1. USENIX Association, 2012.

Wei, Michael, Amy Tai, Christopher J. Rossbach, Ittai Abraham, Maithem Munshed, Medhavi Dhawan, Jim Stabile, Udi Wieder, Scott Fritchie, Steven Swanson, Michael J. Freedman, and Dahlia Malkhi. "vCorfu: A Cloud-Scale Object Store on a Shared Log." In NSDI, pp. 35-49. 2017.

Li, Jialin, Ellis Michael, and Dan RK Ports. "Eris: Coordination-free consistent transactions using in-network concurrency control." In Proceedings of the 26th Symposium on Operating Systems Principles, pp. 104-120. ACM, 2017.

Li, Jialin, Ellis Michael, Naveen Kr Sharma, Adriana Szekeres, and Dan RK Ports. "Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering." In OSDI, pp. 467-483. 2016.

Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16, no. 2 (1998): 133-169.

Liskov, Barbara, and James Cowling. "Viewstamped replication revisited." (2012).

Moraru, Iulian, David G. Andersen, and Michael Kaminsky. "Egalitarian paxos." In ACM Symposium on Operating Systems Principles. 2012.

Kapritsos, Manos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. "All about Eve: Execute-Verify Replication for Multi-Core Servers." In OSDI, vol. 12, pp. 237-250. 2012.

Schneider, Fred B. "Implementing fault-tolerant services using the state machine approach: A tutorial." ACM Computing Surveys (CSUR) 22, no. 4 (1990): 299-319.

Lamport, Leslie. "Time, clocks, and the ordering of events in a distributed system." Communications of the ACM 21, no. 7 (1978): 558-565.

Textbook:

Tanenbaum, Andrew S., and Maarten Van Steen. Distributed systems: principles and paradigms. Prentice-Hall, 2007.