TTh 12:30  2:00
ENS 116
Unique No. 17160
Instructor: Prof. Vijay K. Garg ; Office: ACE 5.436; Phone: 4719424 ;
email: garg AT ece.utexas.edu;
Office Hours: T Th 3:004:30 (or by appointment);
URL:
http://www.ece.utexas.edu/~garg
Prerequisites: Programming experience, Graduate standing
Textbook :
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
two exams during the course.
The following topics will be covered in the course:
Week  Topics  Course Material 
1  Introduction, posets, HappenedBefore, lattices, Clocks (physial, logical, vector, chain)  C15, [L78] 
2  Mutex Algorithms: Lamport, RicartAgrawala, Drinking Philosophers, Quorums  C68 
3  Snapshot algorithms, Leader election, Spanning tree,  C9, C10, C18, [CL], [GG], [GHS] 
4  Randomization, Chernoff's bound, Distributed Trigger Counting, Maximal Independent Set  [CCGS11], [Luby86] 
5  Global Predicates (linear, relational), Birkhoff's Theorem, Slicer, termination detection  [IG06], [MG02], C1114, C21 
6  Test 1, Causal and Total Message Order, Synchronizers, Selfstabilization  C16, C17, C21, C23 
7  Common Knowledge, FLP, Consensus in synchronous systems, Paxos, Byzantine Agreement  C2426 
8  Weighted Byzantine, Accurate Byzantine, Approximate Agreement, Practical Byzantine  [GB11], [GBB11] 
9  Basic Linear Codes, ReedSolomon, Fusion based FaultTolerance  [G10], [GB11] 
10  Failure Detectors, PublishSubscription Systems  C28, [PubSub03] 
11  MapReduce, Google File System, P2P Systems  [DG04], [GGL03], [Chord03] 
12  Social Networking, Applications of Game theory to Distributed Computing 

13  Trace Analysis, Controlling Distributed Computations  C15, [SG04], [OG07] 
14  Term Project Presentations 

15  Term Project Presentations, Survey 

Grading: 25 % Assignments, 25 % Exam 1 (inclass),
15% Term paper, 5% Class presentation,
30 % Exam 2.
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 Office of the Dean of Students at
4716259, 4714641 TTY."