Large-scale Data Processing

Date	Topic	Materials	Presenter
1/13	Syllabus and overview	Null	Yang Wang syllabus overview
1/15	Consistency	Null	Yang Wang
1/20	Consistency	Null	Yang Wang consistency
1/22	Global state	Null	Yang Wang slides
1/27	Global state	Null	Discussion
1/29	Order and clocks	O. Babaoglu and K. Marzullo. Consistent Global States of Distributed Systems.	Yang Wang slides
2/3	Two-phase Commit (2PC)	Bernstein, Goodman and Hadzilacos. Distributed Recovery	Sixiang Ma
2/5	Replication	T. Bressoud and F.B. Schneider. Hypervisor-based Fault-Tolerance. SOSP Best Paper Award	Fang Zhou
2/10	Replication	F.B. Schneider. Implementing fault-tolerant services using the state machine approach: a tutorial. SIGOPS Hall of Fame	Xiaochi Li
2/12	Replication - Consensus	Null	Yang Wang slides
2/17	Replication - Paxos	Null	Discussion slides
2/19	Replication - Paxos	Required: L. Lamport: Paxos Made Simple. Suggested: L. Lamport: The Part-Time Parliament. SIGOPS Hall of Fame R. van Renesse: Paxos made moderately complex M.J. Fischer, N.A. Lynch, and M.S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. E.W. Dijkstra Prize, 2001.	Yang Wang slides Project 2 description Project 2 template
2/24	Can we strengthen Paxos to tolerate arbitrary errors?	Null	Discussion
2/26	Replication - BFT	Required: M. Castro and B. Liskov. Practical Byzantine Fault-Tolerance. Suggested: L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. E.W. Dijkstra Prize, 2005. J. Yin, J.P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. Separating Agreement from Execution for Byzantine Fault-Tolerant Services	Rong Shi
3/2	Weaker Consistency	D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer and C. H. Hauser. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System	Yang Wang
3/9	Industry	Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. SIGOPS Hall of Fame.	Giorgio Xu
3/11	Industry	Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. SIGOPS Hall of Fame.	Lakshmi anusha Pasagadugula
3/23	Industry	Chang et. al. Bigtable: A Distributed Storage System for Structured Data.	Ganga Reddy Tankasala
3/25	Industry	Mike Burrows. The Chubby Lock Service for Loosely-Coupled Distributed Systems.	Yifan Gan
4/1	Industry	DeCandia et. al. Dynamo: Amazon’s Highly Available Key-value Store.	Vishakha Rai
4/6	Industry	D. Beaver, S. Kumar, H. Li, J. Sobel, and P. Vajgel. Finding a needle in Haystack: Facebook’s photo storage.	Atri Shivam
4/8	Computation	Zaharia et. al. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (Also known as Spark)	Lingyan Yin
4/13	Computation	M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks.	Gaganjit Singh Jhally
4/15	Computation	D. Murray, F. McSherry, R. Isaacs, M. Isard, P. Barham, and M. Abadi. Naiad: A Timely Dataflow System.	Das Shayoni
4/20	Industry	Corbett et. al. Spanner: Google's Globally-Distributed Database. OSDI Best Paper Award 2012.	Runzhou Cao
4/22	Weaker Consistency	W Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS.	Bhavya Arora
Final week	Project presentation and demonstration