DISTRIBUTED COMPUTING
COMP 4001
Fall 2017

1. CONTACTS: Evangelos Kranakis Office hrs
   Teaching Assistants:
   TA Office Hours: (Held in HP 4125)
   Ryan Killick (email: RyanKillick@cmail.carleton.ca) [OffHrs Mon 2:30 to 4:30 pm]
2. IMPORTANT: Carleton University Equity Statement
   Explanations for Lectures: NC = Not Covered, (*-*) = page range covered in class
   
   

   Week	Lecture	Announcements	Information/Resources MSDNAA
   Wk 01 Sep 06	E Pluribus Unum Distributed Computing		PoDC: Lecture Notes Useful Probability
   Wk 02 Sep 13	Coloring	Assignment A Posted: Sep 08	WP1
   Wk 03 Sep 20	ID Selection Leader Election1		WP2
   Wk 04 Sep 27	Leader Election2	Assignment A Due: Sep 28	WP3
   Wk 05 Oct 04	Search Evacuation	What-to-Study Exam from 2013 Assignment B Posted: Oct	WP4
   Wk 06 Oct 11	TEST 1 (in class) Connections	Project Posted: Sep Related Publication
   Wk 07 Oct 18	Locality Discussion of Project		WP5
   Wk Oct 23-27	Fall Break
   Wk 08 Nov 01	Geolocality Broadcasting	Assignment B Due: Nov	Bellman Ford Example
   Wk 09 Nov 08	Trees in DC1	Assignment C Posted: Nov
   Wk 10 Nov 15	Trees in DC2		WP6
   Wk 11 Nov 22	TEST 2 (in class) RV RRV	What-to-Study Assignment C Due: Nov	WP7 WP8
   Wk 12 Nov 29	Rendezvous Patrolling		Batcher
   Wk 13 Dec 06	Distributed Sorting Project Demos	Project Due: Dec What/How to Submit

3. NOTE:
   Student or professor materials created for this course (including presentations and posted notes, labs, case studies, assignments and exams) remain the intellectual property of the author(s). They are intended for personal use and may not be reproduced or redistributed without prior written consent of the author(s).
4. CONTENTS OF LECTURES: Some of the course may be based on recent papers published only in journals and/or conference proceedings. You can download lecture notes in pdf format. Links are activated only when the lectures are ready, which is usually before, but close to the time of the lecture.
5. BRIEF COURSE DESCRIPTION:
   Overview of distributed computing. Topics include: computational models, communication complexity, design and analysis of distributed algorithms and protocols, fault-tolerant protocols, synchronous computations. Applications may include: communication in data networks, control in distributed system (e.g., election, distributed mutual exclusion), manipulation of distributed data (e.g., ranking).
6. PREREQUISITES
   COMP 1805, 2401 and 2406
7. WHAT TO STUDY FOR THE TESTS:
   1. Read everything covered in class. Make sure you understand concepts and methodologies in a technical manner.
8. STUDENTS' REQUIREMENTS SCHEDULE
   
   1. Homework assignments.
      Three assignments that will contribute 15% of the final grade (5% each).
      All assignments are compulsory and must be uploaded the course web site in CU Learnn on the due date no later than 12 noon:
      Submit only in pdf format and avoid zip, wordperfect, etc.
      Late assignment policy: 33% off penalty per day.
   2. Active Class Participation.
      This will contribute 5% of the final grade.
      1. Active class participation means: participating during the lecture by making improvements, presenting a short program illustrating an algorithm presented in class, presenting a short proof of something presented in the lecture, elaborating on something new you discovered, or solving the weekly problem and presenting it in class. (Please send me an email prior to the presentation.)
      2. The weekly problem is only for class discussion and is not to hand in.
   3. Project
      This will contribute 20% of the final grade.
      1. Students can work in groups of at most two.
      2. The project should follow (guidelines for project/paper abstract preparation).
      3. Students must make an in-class presentation (during last week of class),
   4. In-class exams.
      1. Two 60 min Tests. Each test will contribute 30% to the final grade and you will be examined on the material covered.
9. USEFUL TEXTBOOKS: (Not Required)
   1. H. Attiya, J. Welch, Distributed Computing, Wiley, 2E, 2004.
   2. F. Bullo, J. Cortes, S. Martinez, Distributed control of robotic networks_ a mathematical approach to motion coordination algorithms, Princeton University Press, 2009.
   3. D. Gordon, Ant Encounters: Interaction Networks and Colony Behavior, Princeton University Press, 2010.
   4. E. Kranakis, D. Krizanc, and E. Markou, The Mobile Agent Rendezvous Problem in the Ring, Morgan-Claypool, 2010.
   5. N. Lynch, Distributed Algorithms, Morgan-Kaufmann, 1996.
   6. D. Peleg, Distributed Computing A Locality Sensitive Approach, SIAM, 2000.
   7. N. Santoro, Design and Analysis of Distributed Algorithms, Wiley, 2007.
   8. R. Wattenhoffer, The Science of the Blockchain, 2017.