ISE 435 -  Distributed Algorithms in Network Communications
Semester 2 5771

Topics     Reading     Assignments   Quizzes  Grading     Lectures     Policies

Time: Monday 13:00 - 15:00 in Room 202
Targil: Thursday 16:00 - 17:00 in Room 202

Instructor:

    Michael J. May
      e-mail: mjmay (AT) kinneret,ac,il
      office hours: Monday. 11:45-12:45 (and by appointment)

Metargel:

       Naomi Unkelos
       email: noom112@
       office hours:

The full detailed syllabus for the course is available here.

Reminder: Assignments 4 solutions on Telem.

Topics:

The topics for the course include some or all of the following:
  • Peer-to-Peer asynchronous network communication
  • Primitives and building primitive distributed algorithms
  • Data distribution algorithms
  • Request-Reply algorithms
  • Search and traversal algorithms
  • Breaking symmetry and election algorithms
  • Topology discovery
  • Routing
  • Building and maintaining trees
  • Synchronization
  • Fault tolerance and recovery
  • Proving correctness of distributed algorithms
  • Complexity of distributed algorithms

Reading

The following book contains useful course material, and much of the lecture content is derived from them (and other sources). Copies of these books are on reserve in the Kinneret Library.

  • Introduction to Distributed Algorithms. (2nd edition) by Gerard Tel.

Assignments

Assignment 1:  Graph Theory.  Due 7 March 2011.
                         Solutions posted on Telem.

Assignment 2:  Logical Clocks. Due 12 April 2011.
                         Solutions posted on Telem.

Assignment 3: Wave and Traversal Algorithms. Due 25 May 2011
                        Solutions posted on Telem.

Assignment 4: Communication and Election. Due 18 June 2011.
                        Solutions posted on Telem.

Submission instructions: You may submit work using Telem, in person, or by sending email to the address ise435 at gmail.  If you send email to the ise435 address, you will receive an auto-answer response acknowledging that a message has been received.

Quizzes


There will be (a maximum of) four in class short quizzes at the beginning of lectures during the course of the semester. The quizzes will take place from 2:00-2:10pm.  Students may skip or drop the grade of one of the quizzes without penalty. Students who miss a quiz due to Miluim duty will be allowed to (additionally) drop the missed quiz.

Tentative Quiz Schedule


#
 Date
 Topic
 Source
1
 7 March
 Graph Theory, Models
 App B, 2
2
 4 April
 Wave Algorithms
 6.1-6.2
3
 16 May
 Wave and Traversal Algorithms
 6.2-6.3
4
 6 June
 Routing Algorithms
 4.1-4.4

Grading Criteria

  •   4%   Quizzes
  • 16%   Programming Projects / Assignments
  • 80%   Final Exam

Lecture Slides and Notes

Schedule
#
 Date
 Topic
 Notes
1
 21 Feb
 Introduction and Graph Theory [pdf][targil]
2
 28 Feb
 Graph Types, Intro to Models
 [pdf][targil]
3
 7 March
 Communication Models
 [pdf][targil]
4
 14 March
 Events, Fairness, Invariants
 [pdf][targil]
5
 28 March
 Causality, Wave algorithms
 [pdf][targil]
6
 4 April
 Wave Algorithms
 [pdf][targil]
7
 11 April
 Traversal and Depth First Search Algorithms
 [pdf][targil]
8
 2 May
 DFS 2, Comm. protocols (Balanced Sliding Window) [pdf][targil1][targil2]
9
 16 May
 Comm. protocols (Balanced and Timer-based protocol)
 [pdf][no targil]
10
 23 May
 Balanced 2, Timer-based Protocol
 [pdf][targil, example]
11
 30 May
 Timer-based Protocol
 [pdf][targil]
12
 6 June
 Routing Algorithms 1
 [pdf][no targil]
13
 13 June
 Routing Algorithms 2, Election algorithms
 [pdf][targil]

6 July
 Final Exam Moed A - TBA 08:30 - 11:30

3 August
 Final Exam Moed B - TBA 08:30 - 11:30

Academic Integrity

Since Kinneret College does not have a unified code of academic integrity, this course will abide by the University of Pennsylvania's Code of Academic Integrity. In particular, for individual projects and group projects, the following guidelines should be followed:
  • For individual projects, you must type in and edit your own code, documentation, and any other materials submitted for grading.
    • Copying someone else's file is not allowed.
    • Allowing someone else to copy a file of yours, either explicitly or implicitly by leaving your code unprotected, is not allowed.
    • Editing each other's files is not allowed
  • Regarding the ethics of what you may or may not discuss with others:
    • "High level" discussions are fine.
      For example, discussions about the problem statement.
    • "Low level" discussions are fine.
      For example, discussions about C syntax or using gdb, understanding compiler error messages, understanding the mechanics of the tools and libraries used for the projects.
    • "Mid level" discussions require discretion. In this CIS course, discussions at this level must be limited.  Unless explicitly stated otherwise, you may not collaborate significantly with classmates (except group project members) at this level.  If you have minor discussions with others at this level or get help from outside resources (tutors, web sites, etc), you must cite at the top of the submitted projects the names of the people or websites who helped you and how they did. For example: 
            /**
             * Chris Brown
             * Project 1
             * 5/6/2008
             * I received tips from Jo Johnson on the i/o and example.com/mem.htm on memory
             */
  • If there is any doubt about the use of external sources or collabortation, please ask for clarification by the course staff.