distributed algorithms

comp90020 2021 sm1

graduate cs subject on classical algorithms for distributed systems
university of melbourne

these materials were prepared by me for TA purposes and may be 
arbitrarily out of date relative to current curriculum in comp90020

Schedule

Week	Tutorial	Solutions	Notes	Readings
2	tute01	sols01	notes01	Lamport Clocks Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System, 21, 558–565.
3	tute02	sols02	notes02	Snapshots Chandy, K. M., & Lamport, L. (1985). Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems (TOCS). https://doi.org/10.1145/214451.214456
4	tute03	sols03	notes03	Mutex Ricart, G., & Agrawala, A. K. (1981). An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM. https://doi.org/10.1145/358527.358537
5	tute04	sols04	notes04	Elections Garcia-Molina, H. (1982). Elections in a Distributed Computing System. IEEE Transactions on Computers. https://doi.org/10.1109/TC.1982.1675885
6	tute05	sols05	notes05	Byzantine Generals Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS). https://doi.org/10.1145/357172.357176
7	tute06	sols06	notes06	FLP Impossibility Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM). https://doi.org/10.1145/3149.214121
8	tute07	sols07	notes07	Paxos Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2), 133–169.
9	tute08	sols08	notes08	CockroachDB Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD '20). Association for Computing Machinery, New York, NY, USA, 1493–1509. DOI:https://doi.org/10.1145/3318464.3386134
11	tute09	sols09	notes09	Calvin Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. 2012. Calvin: fast distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12). Association for Computing Machinery, New York, NY, USA, 1–12. DOI:https://doi.org/10.1145/2213836.2213838
12	tute10	sols10	notes10	ARIES Aries –C. Mohan, ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM Transactions on Database Systems, Vol. 17, No. 1, March 1992, pp. 94–16

Books

the tutorial questions contain content, ideas and derived questions from the-
following books. 

I claim no ownership for any content.

*denotes exceeding subject scope or extension material

books in bold, I would recommend referring to first.

• Distributed Systems: Concepts and Design, 2011
  • ch 14,15,16,17
• Distributed Systems: An Algorithmic Approach, 2014
  • ch 6,7,8,9,11,13,14,15,16
• Distributed Algorithms, 1996
  • ch 3, 4, 5, 6, 10, 12, 18, 19
• Notes on Theory of Distributed Systems, 2021
  • ch 5, 6, 8, 9, 10, 11, 12, 13
• Transactional Information Systems, 2002*
  • ch 2, 3, 4, 5, 11, 18, 19
• Distributed Algorithms for Message-Passing Systems, 2013*
  • ch 3, 4, 6, 7, 10, 11, 12, 14, 15
• Distributed Algorithms, an Intuitive Approach, 2018
  • ch 2, 3, 5, 9, 10, 11, 12, 13, 14, 16
• Introduction to Distributed Algorithms, 2000
  • ch 2, 7, 9, 10, 12, 14, 15*
• Distributed Computing Fundamentals, Simulations, and Advanced Topics, 2004*
  • ch 2, 3, 4, 5, 6, 8, 12, 13

Extra Questions

questions I would have liked to include in the tutorials but were either
too challenging (given the time constraints) or there were better options.

misc