Lecture Summary and Readings
ECE/CS 598NV Special Topics (Fall 2009)
(Distributed Algorithms for Wired and Wireless Networks)

Unless otherwise specified, chapter/section numbers below refer to the required textbook by Attiya and Welch. Readings listed below in the entry for a lecture may actually correspond to multiple lectures in the vicinity of that lecture. Not all topics listed for reading may be covered in class. Some readings may be assigned ahead of the corresponding lectures.

The recommended readings listed below are suggested readings to help improve understanding of the material covered in the class. However, the recommended readings are not mandatory. Unless specifically identified as recommended, all other readings are required, and material in the required readings is included for the mid-term tests and final examination.

Lecture	Date	Topics	Readings	Other information
1	8/25/09	Course Introduction. Formal models for message passing systems. Basic graph algorithms.	Chapter 1, Chapter 2 Slides Set 1 & Slides Set 2	Course handout
2	8/27/09	Basic graph algorithms: broadcasting on a spanning tree, convergecast (aggregation), finding a spanning tree. Leader election in rings: examples of algorithms, lower bound for asynchronous ring.	Sections 3.1, 3.2, 3.3 Slides Set 3 & Slides Set 4	Information on Project and paper presentation
3	9/1/09	Leader election in synchronous rings: example algorithms, lower bound on message complexity.	Section 3.4 except section 3.4.2.3 , sections 14.1.1, 14.1.2, 14.1.3 Slides Set 5 Recommended reading: Section 3.4.2.3	Information on Project and paper presentation Homework 1 assigned
4	9/3/09	Lower bound proof for leader election. Randomized leader election. Mutual Exclusion in Shared Memory	Sections 4.1, 4.2, 4.3 Slides Set 6
5	9/8/09	Mutual Exclusion in Shared Memory using Read/Write variables	Section 4.4 Slides Set 7 Slides Set 8
6	9/10/09	Mutual Exclusion in Shared Memory. Causality, vector clocks.	Section 4.4, Sections 6.1 and 6.2 (except section 6.2.2) Slides Set 9 Recommended reading: Sections 1 and 2 of A Survey of Rollback-Recovery Protocols in Message-Passing Systems, by Elnozahy, Alvisi, Wang and Johnson.
7	9/15/09	Vector clocks, consistent state.
8	9/17/09	Consensus in synchronous systems with crash failures.	Section 5.1, Slides Set 10	Consensus with Byzantine faults not included for mid-term test I Information regarding mid-term test I
9 (Guest lecturer: Prof. Sayan Mitra)	9/22/09	Self-stabilization	Self-stabilizing systems in spite of distributed control, EW Dijkstra, CACM 1974 A self-stabilizing algorithm for coloring planar graphs, Ghosh, Distributed Computing 1991 Self-Stabilization In Distributed Systems A Short Survey, Jerzy Brzezinski, Michal Szychowiak, Dariusz Wawrzyniak, Foundations of Computing and Decision Sciences, 25(1), 2000.
10 (Mid-term test I)	9/24/09 (Thursday)	Mid-term test I (in class)	See course homepage for more information	Information regarding mid-term test I
11	9/29/09	Consensus with Byzantine failures. Consensus in asynchronous systems. Reliable broadcast in wireless networks.	Section 5.1, Sections 5.2.1, 5.2.2, 5.2.3, Section 5.2.4 (except the proof of correctness), Sections 1, 2, and 3 of the following paper: [FLP1985] Impossibility of distributed consensus with one faulty process, Fischer, Lynch and Paterson, JACM 1985. Sections 1 through 5, and the algorithm presented in Section 6 (excluding the proof of correctness) from the following paper: [BV2005] V. Bhandari and N.H. Vaidya, On Reliable Broadcast in a Radio Network, 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2005 Slides Set 10 Slides Set 11 Recommended reading: Section 5.2.5	Homework 3 assigned Slides from the web for the [FLP1985] paper Slides for the [BV2005] paper Slides for a talk by Vaidya
12	10/1/09	Reliable broadcast in wireless networks
13	10/6/09	No class (make-up class on November 18)
14	10/8/09	System level diagnosis; Symmetric invalidation model with permanent faults (also known as the PMC model)	Pages 1-11 of the following paper: [SOMANI] System Level Diagnosis: A Review (postscript file) Recommended reading: Proofs of theorems stated on page 10 of [SOMANI] are available in the corresponding papers cited on page 10.
15	10/13/09	Clock synchronization	Section 6.3 Slides Set 12
16	10/15/09	Fault-Tolerant Clock synchronization. Randomized consensus.	Sections 13.1 and 13.2 Section 14.3 Slides Set 13
17	10/20/09	Randomized consensus. Link reversal algorithms.	Pages 305-317 of Analysis of Link Reversal Routing Algorithms	Slides 1-61 for link reversal
18	10/22/09	Link reversal algorithm. Distance vector protocol with tags.	Notes on distance vector routing Recommended readings: A tree-based algorithm for distributed mutual exclusion A mutual exclusion algorithm for ad hoc mobile networks
19	10/27/09	Weighted voting. Quorums. Probabilistic quorum systems.	Sections I, II, III.A and III.B of Vote assignments in weighted voting mechanisms by Tong and Kain Definition 3.1 and Lemma 3.15 in Probabilistic quorum systems by Malikhi, Reiter, Wool, Wright. Definition of "Load" in section 1.1, and first two paragraphs of Section 1.3 on New Results in The Load, Capacity, and Availability of Quorum Systems, by Naor and Wool. Method 2 on page 155 of A squareroot(N) algorithm for mutual exclusion in decentralized systems, by Maekawa. You may have to read additional parts of the above papers to understand the notations used in these papers. Recommended reading: Read the first solution presented in A squareroot(N) algorithm for mutual exclusion in decentralized systems, by Maekawa.
20	10/29/09	Distributed Shared Memory	Chapter 9 Slides Set 14
21 (Mid-term test II)	11/3/09 (Tuesday)	Mid-term test II (in class)	See course homepage for more information
22	11/5/09	No class
23	11/10/09	Broadcast	Sections 8.1 and 8.2 Slides Set 15	Link for the poll to schedule make-up class
24	11/12/09	Distributed graph coloring. Geographic location service.	Section 4 (except the inductive proof) of A Scalable Location Service for Geographic Ad Hoc Routing Sections 1, 3 and 4 (excluding the proofs) from the paper On the Complexity of Distributed Graph Coloring (proofs from this paper not included in the required reading).	Presentation by Vijay Raman based on the paper: On the Complexity of Distributed Graph Coloring by Fabian Kuhn and Roger Wattenhofer, PODC 2006.
25	11/17/09	Geographic location service. Randomized algorithms. Practical Byzantine fault tolerance.	Sections 1, 2, and 3 of Proving time bounds for randomized distributed algorithms Sections 1, 2 and 3 of Practical Byzantine Fault Tolerance	Student Presentations Sridhar Duggirala: Reference Proving time bounds for randomized distributed algorithms Abhishek Verma: Reference Practical Byzantine Fault Tolerance
Make-up for 13	11/18/09 Wednesday at 3:40 p.m. in 3403 Siebel Center	Atomic broadcast object. Renaming in asynchronous systems. Address assignmet in wireless networks.	Definition of atomic broadcast object in Section 10.3. Section 16.3 up to and including Section 16.3.1 (Section 16.3.2 not included). Sections 1.2 and 1.3 of notes on address assignment in wireless networks	Slides for renaming and address assignment
26	11/19/09	Asynchronous randmized consenses. Practical Byzantine fault tolerance. Fair leader election.	Section 1 of Tight bounds for asynchronous randomized consensus Sections 1 and 2 of BFT Protocols Under Fire Section 3.3 of Towards Fair Leader Election in Wireless Networks (slides for the paper presentation). You may also want to read earlier parts of the paper that provide the context and definitions of notations used in the paper.	Homework 5 posted Presentation by Guanfeng Liang: Reference Tight bounds for asynchronous randomized consensus & Brian Cho: Reference BFT Protocols Under Fire & Rachit Agrawal: Reference Towards Fair Leader Election in Wireless Networks (slides)
27	12/1/09	Fault-tolerant mutual exclusion. Routing loops. Code assignment in packet-radio networks.	Section 3 of A dual-token-based fault tolerant mutual exclusion algorithm for MANETs Section III of RIP-MTI: A New Way to Cope with Routing Loops Section I of Distributed assignment of codes for multihop packet-radio networks	Presentation by Ghazale Hosseinabadi: References A dual-token-based fault tolerant mutual exclusion algorithm for MANETs & Brent Mochizuki: Reference RIP-MTI: A New Way to Cope with Routing Loops (slides) & Maria Carrasco: Reference Distributed assignment of codes for multihop packet-radionetworks
28	12/3/09	Leader election. Time synchronization. Distributed localization.	Section 1 of Leader election algorithms for mobile ad hoc networks Wireless sensor networks: a new regime for time synchronization Sections 1, 2 and 4 of Anchor-Free Distributed Localization in Sensor Networks	Presentations by Fatemeh Saremi: Reference Leader election algorithms for mobile ad hoc networks & Parya Moinzadeh: Reference Wireless sensor networks: a new regime for time synchronization & Karthikeyan: Reference: Anchor-Free Distributed Localization in Sensor Networks
Course review	12/7/09 (Monday) at 5 p.m. in room 2124 Siebel Center	Course review.
29	12/8/09	Mutual exclusion. Transient/intermittent failures. Clock synchronization.	Sections 1, 2 and 3 of Read/Write Based Fast-Path Transformation for FCFS Mutual Exclusion Section 1 of Tolerating transient and intermittent failures Sections 1 and 2 of Self-stabilizing clock synchronization in the presence of Byzantine faults	Presentation by ZuCheng Huang: Reference: Sections 1, 2 and 3 of Read/Write Based Fast-Path Transformation for FCFS Mutual Exclusion & Taylor Johnson: Reference Tolerating transient and intermittent failures & Virajith Jalaparti: Reference Self-stabilizing clock synchronization in the presence of Byzantine faults
Final Examination	12/17/09 (Thursday)	Final Examination	See course homepage for more information

Return to ECE/CS 598NV home page