EE 382 N Vijay K. Garg Fall 2011

TTh 12:30 - 2:00
ENS 116
Unique No. 17160

Instructor: Prof. Vijay K. Garg ; Office: ACE 5.436; Phone: 471-9424 ; e-mail: garg AT ece.utexas.edu;
Office Hours: T Th 3:00-4: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, Happened-Before, lattices, Clocks (physial, logical, vector, chain)

C1-5, [L78]

2

Mutex Algorithms: Lamport, Ricart-Agrawala, Drinking Philosophers, Quorums

C6-8

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], C11-14, C21

6

Test 1, Causal and Total Message Order, Synchronizers, Self-stabilization

C16, C17, C21, C23

7

Common Knowledge, FLP, Consensus in synchronous systems, Paxos, Byzantine Agreement

C24-26

8

Weighted Byzantine, Accurate Byzantine, Approximate Agreement, Practical Byzantine

[GB11], [GBB11]

9

Basic Linear Codes, Reed-Solomon, Fusion based Fault-Tolerance

[G10], [GB11]

10

Failure Detectors, Publish-Subscription Systems

C28, [PubSub03]

11

Map-Reduce, 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 (in-class), 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 471-6259, 471-4641 TTY."