CSE 6333 -- Introduction to Distributed Computing

Instructor: Prof. Anish Arora

Spring 2013

WF 11:10am-12:30pm, Dreese Labs DL480, Section 12572

Office hours: WF 2:45-3:45pm in DL 587

Description

This course will introduce concepts and mechanisms in the design and analysis of distributed programs, including:

global time and global state
programming logics for distributed programs
problems in fault-tolerant distribution
wireless sensor networks
distributed data structures
systems design
representative distributed computing environments

Level and Credits

Prerequisites

CSE 6431 (formerly 760) or permission of instructor

General Information, Exclusions, etc.

None

Objectives

On completion of the course, you will have gained mastery of various issues in the design and analysis of distributed programs, and familiarity with ways to address these issues. In particular, you will:

Be familiar with writing and designing distributed programs.
Be familiar with the analysis and verification of distributed programs.
Understand the principles behind several specific classes of distributed algorithms for solving particular problems.
Have mastered reading and understanding distributed algorithms

Reading material

Notes and papers from the literature will be periodically distributed in class. Papers from the literature will be assigned.
Lecture 0 : Introduction
Lecture 1 : Time Part 0 Part 1 Part 2
Lecture 2 : Reasoning Part 0 Part 1 Part 2
Lecture 3 : State Part 0 Part 1
Lecture 4: Fault-Tolerance Part 0 Part 1 Notes
Lecture 5: Paxos
Lecture 6: CAP
Lecture 7: Atomic Registers
Lecture 8: Transactional Memory

Reference Texts

Paul Sivilotti, Course Notes, Introduction to Distributed Systems, Spring 2005
Vijay K. Garg, Elements of Distributed Computing, Wiley, 2002
A. Kshemkalyani and N. Shivaratri, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008
K. M. Chandy and J. Misra, Parallel Program Design: A Foundation, Addison-Wesley, 1988

Topics

Number of Weeks	Topics
1/3	Introduction
2	Programming Notation and Logic: syntax and semantics for distributed programs, safety and progress properties, a UNITY-style temporal logic, proofs of program properties, examples
1.5	Global Time: logical clocks, vector clocks, clock synchronization, order and broadcast
1.5	Global State: consistent states, distributed snapshots, stability detection: termination detection
2	Fault-Tolerance in Distribution: consensus, impossibility of robust consensus, leader election, self-stabilization, distributed reset
1	Wireless Sensor Networks: broadcast and convergecast routing, resource constrained time synchronization
1.5	Systems Design: message passing primitives, shared memory primitives, atomic registers, transactional memory, overlays

Miscellaneous

Grades will be based on five homework/lab assignments (25%), in-class quizzes (10%) a 75-minute in-class mid-term quiz on February 27th^th (25%), an in-class presentation (15%), and a take-home final quiz during April 19-April 21 (5%).

Homeworks will be designed to stimulate independent thinking among the students. They will be due a week after they are given. Late submission of homeworks is strongly discouraged. An exception to this rule is that you give well in advance a strong and convincing reason. Questions regarding the grading of homeworks should be addressed by first contacting the grader.

Mid-term quiz will be closed notes and of fixed duration. Final quiz will be open book and students will follow the honor code, discussing questions on the quiz only with Dr. Arora. A missed quiz will receive a score of zero in the absence of a verifiable medical excuse.

Letter grades will be assigned based on performance relative to other students. In other words, do not expect that an A grade corresponds to 90 or more per cent marks.

Schedule notes:

There will be a training session for programming motes on March 1 in class.
No class on March 13 and 15, courtesy of Spring Break.
Prof. Arora's travel schedule is TBA.

From time to time, I will email the class using your buckeyemail addresses, make sure that you are able to receive these messages if this is not your default address (use forwarding for instance). We’ve had considerable confusion in the past when some students only use these addresses, or cse email addresses, or some third party providers, and miss messages broadcast within the group..

Expectations

I expect you to read carefully the course notes and all material handed out in class. You are encouraged to refer periodically to the books mentioned above and other related literature. You are also encouraged to discuss the material presented in class with other students, but do not collaborate with anyone in solving the problems on the homework or final quiz. Feel free to discuss our expectations and grading criteria with the grader or with me during the quarter

Office Hours

WF 2:45-3:45pm in DL 587

Grader

Mr. Dustin Hoffman DL674, DL 674, hofman.373@buckeyemail.osu.edu, office hours: 3pm-4pm TR, or by appointment

Homework and Lab Assignments

These are to be submitted by the beginning of class on the due date. (Lab exercises should all be electronically submitted before class on the due date.)

Submission will typically be electronic using the submit command, with the directory submit <hw or c6333aa

Reading assignment: Survey on Clock Synchronization in Wireless Sensor Networks

Timesync One and Two

Reading Assignment Distributed Reset

Reading Assignment Robust Commit

Reading Assignment Paxos

Peer to Peer Survey