Spring 2018: CS 553 (Call no 31243) Distributed Computing Systems
Instructor:
Ajay Kshemkalyani
Email:
ajay@uic.edu
Class meeting times: MWF 11:00-11:50am
Room: BH B10
Office Hours in 915 SEO:
MW 1:00 - 1:50pm, and by appointment
- Models: synchronous/asynchronous; shared memory/message-passing
- Global states and snapshots; time models and clock synchronization
- Distributed graph algorithms
- Group communication (including multicast), managing group views
- State predicate detection
- Reasoning with knowledge
- Distributed mutual exclusion, distributed deadlock detection, leader election, termination detection
- Distributed shared memory - coherence, models, register constructions, atomic snapshots (applications to multicore architectures)
- Checkpointing, rollback recovery; distributed debugging
- Agreement and consensus (with malicious and non-malicious process behavior)
- Failure detectors
- Self-stabilizing systems
- Peer-to-peer systems, e.g., Chord, Tapestry, Content-Addressible Network, BitTorrent
- other current topics, e.g., sensor networks
See detailed table of contents of the textbook below by going to the link at Cambridge University Press or Amazon.
This course focuses on distributed algorithms and theoretical principles.
By the end of the course,
you will be able to appreciate that these algorithms have wide applications
in practical distributed systems.
- Textbook:
Distributed Computing: Principles, Algorithms, and Systems, by
Kshemkalyani and Singhal, Cambridge University Press, March 2011 edition
South Asian reprint edition, Dec 2010
ISBN-10: 1107648904, ISBN-13: 978-1107648906
- Course notes are here
- An Overview Chart
- Winners of the Dijkstra Award for Most Influential Paper in Distributed Computing, 2000-.
-
Selected papers and other material from the literature will be posted on the
web or distributed in class.
- Suggested Topics and Papers for class presentation (tentative list; to be updated)
- Self-Stabilization:
E.W. Dijkstra,
Self-stabilizing systems in spite of distributed control,
Communications of the ACM, vol. 17, no. 11, pp. 643-644, Nov. 1974.
plus Chapter 17 (Self-stabilization)
- Paxos:
L. Lamport,
Paxos Made Simple,
ACM SIGACT News (Distributed Computing Column) 32, 4 (121, December 2001)
51-58.
W. Bolosky et al, Paxos replicated state machines as the basis of a high-performance data store, NSDI 2011
- Hadoop and Mapreduce:
J. Dean and S. Ghemawat,
MapReduce: Simplified Data Processing on Large Clusters,
OSDI'04: Sixth Symposium on Operating System Design and Implementation,
San Francisco, CA, December, 2004.
plus Hadoop
- Concurrent Data Structures
- Blockchain and bitcoin
-
W Cai, F He, X Lv, Y Cheng,
A transparent selective undo algorithm for collaborative editing,
IEEE 21st International Conference on
Computer Supported Cooperative Work in Design (CSCWD), 2017.
-
N Agmon, D Peleg,
Fault-tolerant gathering algorithms for autonomous mobile robots,
SIAM Journal on Computing, 36(1): 56-82, 2006.
-
S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita,
Autonomous mobile robots with lights,
Theoretical Computer Science,
Volume 609, Part 1, 4 January 2016, Pages 171-184.
-
Takashi Okumura, Koichi Wada, and Yoshiaki Katayama.
Optimal asynchronous rendezvous for mobile robots with lights.
Technical report, 2017.
Adam Heriban, Xavier Défago, Sébastien Tixeuil,
Optimally Gathering Two Robots,
19th International Conference on Distributed Computing and Networking (ICDCN '18), January 4–7, 2018, Varanasi, India. ACM, New York, NY, USA, 10 pages
-
John Augustine and William K. Moses Jr.,
Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs.
In ICDCN ’18: 19th International Conference on Distributed Computing and Networking, January 4–7, 2018, Varanasi, India. ACM, New York, NY, USA, 10 pages.
The course format will be in two parts.
-
For the first part, the instructor will teach.
Attendance when the instructor is
teaching is not compulsory, but you must attend all the tests/exams.
However, if you miss class, it is your responsibility
to find out what was announced and what was covered, from other students.
-
The second part involves active student participation and is planned as follows.
Each presentation will be made by a team of 2 or 3 students,
depending on the final enrollment which will be known only in the third
week of class.
The class presentations will be on an assortment of topics of current interest.
Each group chooses a paper/topic from a list of topics provided around the
5th week of class.
This is only a starting point. Once you select a topic
from the list (to be provided), you may have to identify more basic or
fundamental papers on that specific topic for presentation.
Pick the most basic/ fundamantal papers that are
rich in new ideas.
They must also have algorithmic content.
Attendance when the student presentations are going on is compulsory.
Algorithm analysis and design (cs401); networks (cs450); or permission of the instructor.
The following is only a tentative breakup of the evaluation scheme
and will be finalized after the second week of class, depending on the final enrollment
in the course.
The final grade is on the curve, i.e., this is relative grading - how you
perform with respect to the others in the class.
Tentative course progress chart (will be updated as we progress)
- Week 1: Introduction (Chapter 1)
- Week 2: Chapter 1, Elementary distributed algorithms (Chapter 5)
- Week 3: Chapter 5
- Week 4: Chapter 5, Chapter 2 (Models), Chapter 3 (Time)
- Week 5: Chapter 4 (Global state), Chapter 6 (Message Ordering and Group Comm.)
- Week 6: Chapter 6, Chapter 8 (Reasoning with Knowledge)
- Week 7: Chapter 8, Chapter 14 (Consensus and Agreement)
- Week 8: Chapter 14 (Consensus and Agreement)
- Week 9: Chapter 18 (Peer-to-peer computing)
- Week 10:
Midterm on March 23: Syllabus: Chapters 1, 5, 2, 3.1-3.4, 3.5.1, 3.7, 3.9, 4-4.3, 6.1-6.2, 6.4-6.5.1, 6.6-6.7, 6.9-6.11.2, 8.1-8.4, 14.1-14.5.4, 14.6-14.6.4, 14.6.6
Chapter 18
- Week 11: Chapter 12 (Distributed Shared Memory)
- Week 12:
- Apr 9: Chapter 12
- Apr 11: Vipul Haralkar : Self-Stabilization
- Apr 13: Bhargav and Amey : Paxos
- Week 13:
- Apr 16: Charu and Nipun : Hadoop and Mapreduce
- Apr 18: Rahul and Charvi : Concurrent data structures
- Apr 20: Nancy and Piyush : Blockchain and bitcoin
- Week 14:
- Apr 23: Louis and Anh
W Cai, F He, X Lv, Y Cheng,
A transparent selective undo algorithm for collaborative editing,
IEEE 21st International Conference on
Computer Supported Cooperative Work in Design (CSCWD), 2017.
- Apr 25: Kislaya and Manika
N Agmon, D Peleg,
Fault-tolerant gathering algorithms for autonomous mobile robots,
SIAM Journal on Computing, 36(1): 56-82, 2006.
- Apr 27: Rachita and Harsh
S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita,
Autonomous mobile robots with lights,
Theoretical Computer Science,
Volume 609, Part 1, 4 January 2016, Pages 171-184.
- Week 15:
- Apr 30: Sreetama and Adarsh
Takashi Okumura, Koichi Wada, and Yoshiaki Katayama.
Optimal asynchronous rendezvous for mobile robots with lights.
Technical report, 2017.
Adam Heriban, Xavier Défago, Sébastien Tixeuil,
Optimally Gathering Two Robots,
19th International Conference on Distributed Computing and Networking (ICDCN '18), January 4–7, 2018, Varanasi, India. ACM, New York, NY, USA, 10 pages
- May 2: Faizan and Vishal
John Augustine and William K. Moses Jr.,
Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs.
In ICDCN ’18: 19th International Conference on Distributed Computing and Networking, January 4–7, 2018, Varanasi, India. ACM, New York, NY, USA, 10 pages.
- May 4: Project Discussion
- Closed book Final exam: as per university timetable,
Thursday 10:30am - 12:30pm.
Syllabus: Midterm syllabus + Chapters 12.1-12.4, 18.1-18.6