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