SYLLABUS: CS 6570 DISTRIBUTED COMPUTATION (Fall 2008) Instructor: Ted Billard Email : ted.billard@csueastbay.edu Phone : 885-3437 Home Page : http://www.mcs.csueastbay.edu/~billard Class Time: Tu/Th 8-9:50am Office Hrs: Tu/Th 12-1pm (Sc N216) Summary: The course emphasizes classical problems which abstract real-world network problems. There are 16 algorithms which include leader election, global snapshots, Byzantine generals, common knowledge, resource allocation, spanning trees and logical clocks. Lectures consist of pseudocode and diagram presentations of the algorithms. A longer algorithm, the distributed minimum-weight spanning tree, is the term project. This course presents more details on specific distributed algorithms than typically found in CS 6580 Distributed Systems and is good before or after a network course. Prerequisites: CS 4560 Operating Systems The student must be familiar with concurrency problems like Dining Philosophers. A network course is not required but the student should understand the concept of sending and receiving messages on a graph of nodes. It is helpful if the student knows Java but the stubs for the classes are provided, hence, the programming is mostly algorithmic. Also, two intro labs will help the student get started. Lecture Notes: ONLINE Grades: Mid-Term (Th 10/30): 25%, Project: 40%, Final (Tu 12/9): 35% Schedule: Date Topic Pages 1 9/25 Leader Election on a Ring 5-7 2 9/30 Leader Election on a Graph 8 3 10/02 Lab 4 10/07 BFS Spanning Tree 26 5 10/09 Lab DUE: LEADER 12, 13, 13A 6 10/14 Centralized MST/SP Weiss 7 10/16 Distributed Sync/Async SP 27-28 8 10/21 Distributed MST 19-25 9 10/23 Distributed Philosophers 2-4 10 10/28 Practice Workshop 11 10/30 MID-TERM 12 11/04 Common Knowledge,Byzantine Gen 9, 16-18 13 11/06 Global Snapshots 10-15 14 11/13 Global Snapshots 15 11/18 Termination Detection 33-35 16 11/20 Phased Algorithms 36 17 11/25 Logical Clocks 29-32 18 12/02 Logical Clocks 19 12/04 Lab 12/09 FINAL EXAM DUE: Program Notebook Collaboration/Copying: Unless otherwise stated, do your own work in this class. Violations will be prosecuted to the full extent of the University rules. Algorithm Assignments: # Algorithm Source Code --------------------------------------------------- 9A. Distributed Philosphers InitDphilBAD.java 12. LeLann Leader InitLelannBAD.java 13. Peterson Leader InitLeaderBAD.java 13A.Flood Leader InitFloodBAD.java 20. Gallager MST InitMSTBAD.java 21. BFS Spanning Tree InitBFSBAD.java 21A.Bellman Shortest Path InitSPBAD.java 21B.Async SP InitASPBAD.java 21B.Async SP with Term 23. Logical Clock ME InitTclockBAD.java 24. BFS and Leader Election InitBFS1BAD.java Installation: www.mcs.csueastbay.edu/~billard/cs6570.html