Amy Tai will present her Generals on May 12, 2015 at 2pm in CS 301. Committee Members: Mike Freedman (adviser), Kai Li, and Andrea LaPaugh. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. abstract: Tango is a framework that allows clients to use distributed data structures without worrying about the underlying implementation. Tango achieves this through an underlying distributed log, called Corfu. Corfu currently has a bottleneck in the single sequencer that all requests must go through in order to write to the log. To overcome this bottleneck, we propose modifying Corfu to employ multiple sequencers. We show that in order to preserve Corfu's linearizability guarantee, the system on average only achieves a fractional additional throughput with each additional sequencer. Due to this result, we shift our analysis to the Tango layer of abstraction; we prove that the transactions in Tango with multiple sequencers still achieve strict serializability. We implement multiple sequencers in Tango and show that performance can increase almost linearly with additional sequencers, up to 3, as long as the read fraction of the workload is low. As expected, multiple sequencers have similar throughput to a single sequencer when all transactions contain reads. reading list: | 1. BALAKRISHNAN, M., MALKHI, D., WOBBER, T., WU, M., PRABHAKARAN, V., | WEI, M., DAVIS, J. D., RAO, S., ZOU, T., AND ZUCK, A. 2013. Tango: | Distributed data structures over a shared log. In Proceedings of the | ACM Symposium on Operating Systems Principles (SOSP). ACM, New York. | 2. Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted | Wobber, Michael Wei, and John Davis, CORFU: A Shared Log Design for | Flash Clusters , in 9th USENIX Symposium on Networked Systems Design | and Implementation (NSDI '12) , USENIX, April 2012. | 3. Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., | Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts | in Bayou, a weakly connected replicated storage system. In | Proceedings of the Fifteenth ACM Symposium on Operating Systems | Principles. ACM Press, New York, NY. | 4. B. Liskov and J. Cowling. Viewstamped replication revisited. | Technical report, MIT CSAIL, Cambridge, MA, 2012. | 5. ONGARO, D., AND OUSTERHOUT, J. In Search of an Understandable | Consensus Algorithm. In Proc. ATC’14, USENIX Annual Technical | Conference (2014), USENIX | 6. J. Terrace and M. J. Freedman. Object storage on CRAQ: | High-throughput chain replication for read-mostly workloads. In | Proc. USENIX Annual Technical Conference, June 2009. | 7. Tanenbaum, Andrew S., Van Steen, Maarten. Distributed Systems: | Principles and Paradigms. Prentice Hall, 2nd Ed. 2006. | 8. Thomson, A., Diamond, T., Shu-Chun Weng, T. D., Ren, K., Shao, P., | and Abadi, D. J. 2012. Calvin: Fast distributed transactions for | partitioned database systems. In Proceedings of the ACM SIGMOD | International Conference on Management of Data. | 9. SCHNEIDER, F. B. 1990. Implementing fault tolerant services using | the state machine approach: A tutorial. ACM Computing Surveys 22, 4 | (Dec.), 299–319. | 10. BERNSTEIN, P. A., SHIPMAN, D. W., AND WONO, W.S. "Formal Aspects | of Senalizability in Database Concurrency Control," IEEE Trans. | Softw Eng. SE-5, 3 (May 1979) 203-215.