The Wh QuestionsMost interesting computer systems today, as well as those of the future, are distributed in nature: the Internet, cellular and PDA communications, biological and bio-tech computations, international trade, multi-national corporate databases, multi-user games, and even your LAN at work. Developing software for such complex systems requires an understanding of basic algorithms that these systems use, and the ability to develop and adjust new algorithms under changing conditions. This is our goal.
The material has been divided to two courses; Syllabus I will be given in the fall semester, and Syllabus II will be given in the spring semester. The courses are independent: you can take any one without taking the other, or decide to take both.
The Wh QuestionsWho: David Talby (Homepage, Email)
When: Friday Mornings, 10:45-13:15
Where: Somewhere in Hadassah College, Jerusalem
Reception Hour: Friday 13:15-14:00
Syllabus I(The numbers in parentheses represent chapter numbers in Lynch's book)
Introduction: Formal Models versus common problems and their practical use
(3) Leader election in a synchronous ring
(4) Algorithms in general synchronous networks: Leader election, Breadth-first search, Minimum spanning tree
(6) Distributed consensus with process failures: Stopping failures, Byzantine failures
Exercise One: Consensus problems in synchronous networks (5,7)
(8,14) The asynchronous network model, summary of widespread industrial implementations
(15) Algorithms in asynchronous networks: Leader election, breadth-first search, spanning tree
(16) Synchronizers
(17) Shared memory versus networks
(18) Logical time
Exercise Two: Stable properties and network resource allocation (19,20)
(21) Asynchronous networks with process failures
(22) Data link protocols
Syllabus IIIntroduction: Formal Models, Common problems and their practical use
(8,9) The asyncronous shared memory, summary of widespread industrial implementations
(10) Mutual Exclusion
(11) Resource allocation and the dining philosophers problem
(13) Atomic objects
(12) Consensus in the shared memory asynchronous model
(8,14) The asynchronous network model, summary of widespread industrial implementations
Exercise One: Algorithms in asynchronous networks (15)
(17) Shared memory versus networks
(18) Logical time
(19) Termination detection, global snapshots and stable properties
(20) Network resource allocation
Exercise Two: Algorithms in synchronous networks (3,4)
(23) Partially synchronous system models, summary of industrial implementations
(24) Mutual exclusion with partial synchrony
(25) Consensus with partial synchrony (basic results)
BibliographyOur book:
Distributed Algorithms, by Nancy Lynch
If you intend to take both courses or just love this area, seriously consider buying this book. It is a large encyclopedia of distributed algorithms, and can be useful as a reference book in your future.
Exercises & GradingThe course will be graded by a final test (70%), as well as two exercises (15% each), which must be submitted and can be done in pairs.
Since this is a last-year elective course, exercises have a more advanced format: They will involve learning and explaining an algorithm from the book on your own. Preferably at most two pairs will work on the same problem. Each exercise must be printed, 4-10 pages long, and include the following sections: The problem description, the algorithm description, an informal correctness argument, an example execution of the algorithm, complexity analysis, special notes (termination, useful variants, etc.), and practical uses of the algorithm.
Dividing algorithms to student pairs will be done in class. Submit exercises by emailing them to David by midnight of the submission date. Hand-written exercises will not be accepted.
Grades for the first semester's course are available here.