TTh 12:30 - 2:00
Unique No. 17255
Instructor: Prof. Vijay K. Garg ; Office: ACE 5.436; Phone: (512) 471-9424 ;
e-mail: garg AT ece.utexas.edu;
Office Hours: T Th 3:00-4:30 (or by appointment);
Prerequisites: Programming experience, Graduate standing
Elements of Distributed Computing by Vijay K. Garg, Wiley & Sons, 2002. The textbook will be supplemented with a set of papers .
Course Contents: This will be an introductory graduate level course in distributed systems. It will expose students to theoretical as well as practical aspects of designing such systems. The course assumes that the student has some familiarity with programming. There is no final exam but there will be three tests during the course. The following topics will be covered in the course:
Introduction, posets, Happened-Before, lattices, Clocks (physical, logical, vector, chain)
Mutex Algorithms: Lamport, Ricart-Agrawala, Drinking Philosophers, Quorums
Snapshot algorithms, Leader election, Spanning tree,
C9, C10, C18, [CL], [GG], [GHS]
Randomization, Chernoff's bound, Distributed Trigger Counting, Maximal Independent Set
Test 1, Global Predicates (linear, relational), Birkhoff's Theorem, Slicer, termination detection
[IG06], [MG02], C11-14, C21
Causal and Total Message Order, Synchronizers, Self-stabilization
C16, C17, C21, C23
Common Knowledge, FLP, Consensus in synchronous systems, Paxos,
Byzantine Agreement, Weighted Byzantine, Accurate Byzantine, Approximate Agreement, Practical Byzantine, Test 2,
Basic Linear Codes, Reed-Solomon, Fusion based Fault-Tolerance
Failure Detectors, Publish-Subscription Systems
Map-Reduce, Google File System
P2P Systems, Chord, Dynamo, Cloud Computing,
Trace Analysis, Controlling Distributed Computations
C15, [SG04], [OG07]
Term Project Presentations
Term Project Presentations, Survey, Test 3
Grading: 25 % Assignments, 15 % Test 1,
15 % Test 2, 20 % Test 3, 20% Term paper, 5% Class presentation.
Scribe Notes from Spring 2011
Course Evaluation: Standard ; Add/Drop Policy: Standard.
Disabilities statement: "The University of Texas at Austin provides upon request, appropriate academic accommodations for qualified students with disabilities. For more information, contact the Division of Diversity and Community Engagement, Services for Students with Disabilities, at (512) 471-6259, 471-4641 TTY,http://www.utexas.edu/diversity/ddce/ssd."