DD2451, Parallel and Distributed Computing, Pardis, 2011
The list below is advice plus pointers for more information for those that want to find out more.
- Herlihy+Shavit chapter 1 and 2
- E.W. Dijkstra, Cooperating Sequential Processes, manuscript, 1965.
- E. W. Dijkstra. Solutions of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965.
- G. L. Peterson. Myths about the mutual exclusion problem. Inf. Process. Lett., 12:115--116, June 1981.
- G. L. Peterson and M. J. Fischer. Economical solutions for the critical section problem in a distributed system. In Proceedings of the 9th ACM Symposium on Theory of Computing, pages 91-97, 1977
- See also references at end of H+S ch 2.
- L. Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Transaction on Computers Volume 28 Issue 9, September 1979
- M. Herlihy, J. M. Wing Linearizability: a correctness condition for concurrent objects, TOPLAS Volume 12 Issue 3, July 1990
- Leslie Lamport, The mutual exclusion problem: part I - a theory of interprocess communication, Journal of the ACM (JACM) Volume 33 Issue 2, April 1986
- Leslie Lamport, The mutual exclusion problem: partII - statement and solutions, JACM Volume 33 Issue 2, April 1986
- Cachin, Guerraoui, Rodrigues chapter 4.1-4.3
- Lots of material on the Java memory model around the web
- H+S chapter 4
- Wattenhofer section 5.3, available here
- Attiya, Fouren, Gafni: An adaptive collect algorithm with applications, Distributed Computing 15, pp. 87-96. 2002
- Afek Attiya, Dolev, Gafni, Merritt, Shavit: Atomic snapshots of shared memory, JACM vol 40, issue 4
- M. J. Fischer, N. A. Lunch, M. S. Paterson: Impossiblity of distributed consensus with one faulty process, JACM 32, 2, pp 374-382, 1985
- M. Herlihy. Wait-free synchronization. ACM TOPLAS 13, 1, pp. 124-149, 1991
- Read also appendix A of H&S
- H&S chapter 7
- H&S appendix B
- Thomas Anderson. The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, vol. 1, num. 1, January 1990, pages 6 - 16. Here
- John M. Mellor-Crummey, Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems (TOCS) Volume 9 Issue 1, Feb. 1991
- Check out the references at the end of H&S ch 7.
- John D. Valois: Lock-free Linked Lists Using Compare-and-Swap, proc. PODC'95
- H Sundell, P. Tsigas: Lock-free deques and doubly linked lists, Journal of Parallel and Distributed Computing,Volume 68 Issue 7, July, 2008
- See references in slides. Both Attiya and Welch and Lynch: Distributed algorithms cover much of the material. Lynch has some course notes from abobut 1993 available on the net.
- Wattenhofer chapter 16, available here
- Wattenhofer chapter 2, available here
- Attiya and Welch chapter 3
- Use the slides, they should be adequate
- Two phase commit, three phase commit: Covered in most textbooks on databases and transaction processing
- Paxos: Lamports paper "Paxos made simple"
- Other material: Look up the referenced papers.
- Wattenhofer chapter 8, available here
- Paper references in slides