Com S 612
Distributed Algorithms
Fall 2018
Instructor
Soma Chaudhuri
230 Atanasoff
Phone 294-8547
e-mail: chaudhur@iastate.edu
Office Hours : W 1-2 pm, F 10-11 am or by appointment
Lecture: TR 3:40 - 5 pm, 213 Atanasoff
Textbook: Distributed Computing: Fundamentals, Simulations and Advanced Topics
by Hagit Attiya and Jennifer Welch, Wiley & Sons (2nd ed.), 2004.
Reference Texts:
Distributed Computing by Nancy Lynch
Synthesis Lectures on Distributed Computing Theory
Jennifer Welch, editor. Morgan & Claypool Publishers.
Pre-requisites: Com S 511 or Com S 531.
Announcements
- August 21, 2018
Welcome to Com S 612!
- August 22, 2018
The course will cover the theoretical aspects of distributed computing. We will be studying algorithms, lower bounds and impossibility results. While proof techniques you have studied in 511 and 531 will be useful, some of the proof concepts are somewhat different. As mentioned in class, distributed systems are more difficult to reason about than sequential systems due to asynchrony and failures. If you feel you are having trouble understanding or coming up with proof arguments, I would be happy to discuss this with you. Please don't hesitate to come to office hours or make an additional appointment.
- August 29, 2018
Assignment 1 has been posted. It is due on Tuesday, Sept 18.
- September 1, 2018
Assignment 1 has been modified. In particular, Problem 1 now requires you to show only one direction of the equivalence argument instead of both directions. To prove that Model B is at least as strong as Model A, show that any execution in Model B is equivalent to some execution in Model A.
- September 2, 2018
Notes on a Model Equivalence Proof, proving that the asynchronous processor / asynchronous communication model is as strong as the synchronous processor / asynchronous communication model, has been posted on the Notes page.
- September 28, 2018
Assignment 2 has been posted. It is due on Tuesday, Oct 16.
- October 3, 2018
A scanned copy of my hand-written notes on the read/write register lower bound for mutual exclusion with no deadlock has been posted on the Notes page.
- October 15, 2018
Assignment 3 has been posted. It is due on Tuesday, Nov 6.
- October 18, 2018
A scanned copy of my hand-written notes Coordinated Attack Problem on the has been posted on the Notes page.
- October 30, 2018
Now that we are about two-thirds into the course, you should start reading papers and deciding on your topic for your paper presentation. General ideas of topics and a recommended list of journals and conferences to choose from are posted on the Projects page.
- November 1, 2018
If you would like to read more about reductions and simulations in distributed computing, or about impossibility results in general, refer to Impossibility Results for Distributed Computing, Synthesis Lectures on Distributed Computing Theory, Morgan Claypool Publishers on the Notes page.
- November 14, 2018
Assignment 4 has been posted. It is due on Tuesday, Dec 4.
- November 16, 2018
David just pointed out to me that the Local Write algorithm I presented (Alg 25 in the book) is wrong. In particular, consider an execution segment where p_i does write (x, 1) write (x,2) read. If the message for write (x,1) is received after the message for write (x,2), the read will return 1. This would be consistent with pi = write (x,2) write (x,1) read (x.1), which violates operation ordering of p_i, therefore violating sequential consistency. Fix: Assume that you are also given FIFO ordering. FIFO ordering can be implemented easily (you do not have to implement it). - November 16, 2018
In Assignment 4, Problem 9.7, show that a local read algorithm and a local write algorithm are both possible for linearizability. These can be modifications to the algorithms proposed in the class (Alg 24 and 25 in the book). In both cases, show that any execution is linearizable by placing linearization points for every operation in the execution, and arguing that they satisfy linearization.