CSE 763 -- Introduction to Distributed Computing

Instructor:  Prof. Anish Arora

Spring 2010

       

MWF 9:30-10:18am, Central Classrooms CC211,  Section 12572

 

Office hours:  WF 3:30-4:30pm 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

  • G  3

Prerequisites

  • CSE 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 Part 3
  • Lecture 3 : State                    Part 0 Part 1
  • Lecture 4:  Fault-Tolerance    Part 0 Part 1

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 (35%), a 50-minute in-class mid-term quiz on Monday May 10th  (30%), and a take-home final quiz during June 2 – June 4 (35%).

 

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 May 5th and possibly May 7th in class. 
  • Monday, May 31st is a holiday.

 

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 3:30-4:30pm in DL 587

 

Grader

 

Mr. Satyajeet Deshpande, DL 286, deshpande.37@buckeyemail.osu.edu, phone:- 6142666027, office hours: M,W - 11am - 12 noon, T 4pm - 5pm

 

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 c763aa

 

HW0

HW1

HW2

HW3

 

 

Reading assignment: Survey on Clock Synchronization in Wireless Sensor Networks

Timesync One and Two

Reading Assignment Distributed Reset

Peer to Peer Survey