DD2451, Parallel and Distributed Computing, Pardis, 2011

Reading

The list below is advice plus pointers for more information for those that want to find out more.

Lecture 1

• Herlihy+Shavit chapter 1 and 2

Extra reading:

• 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.

Lecture 2

• H+S chapter 3

Extra reading:

• 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

Lecture 3

• H+S chapter 4
• Wattenhofer section 5.3, available here

Extra reading:

• 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

Lecture 4

• H+S chapter 5

Extra reading:

• 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

Lecture 5

• H&S chapter 7
• H&S appendix B

Extra reading:

• 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.

Lecture 6

• H&S chapter 9

Extra reading:

• 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

Lecture 7

• 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

Lecture 8

• Wattenhofer chapter 2, available here

Extra reading:

• Attiya and Welch chapter 3

Lecture 9

• 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.

Lecture 10

• Wattenhofer chapter 8, available here
• Paper references in slides