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
| Week | Tutorial | Solutions | Notes | Readings |
|---|---|---|---|---|
| 2 | tute01 | sols01 | notes01 | Lamport ClocksLamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System, 21, 558–565. |
| 3 | tute02 | sols02 | notes02 | SnapshotsChandy, 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 | MutexRicart, 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 | ElectionsGarcia-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 GeneralsLamport, 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 ImpossibilityFischer, 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 | PaxosLamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2), 133–169. |
| 9 | tute08 | sols08 | notes08 | CockroachDBRebecca 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 | CalvinAlexander 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 | ARIESAries –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 |
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
questions I would have liked to include in the tutorials but were either
too challenging (given the time constraints) or there were better options.