CIS 763 -- Introduction to Distributed Computing

Instructor:  Prof. Anish Arora

Spring 2008

       

MWF 9:30-10:18am,  Bolz Hall 0428,  04462-5 D (for 763M) and 04461-0 D (for 763)

 

Office hours:  WF 11:25am-12:25pm 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

Reference Texts

  • Paul Sivilotti, Course Notes, Introduction to Distributed Systems, Spring 2005
  • Vijay K. Garg, Elements of Distributed Computing, Wiley, 2002
  • M. Singhal and N. Shivaratri, Advanced Concepts in Operating Systems, McGraw Hill (1994)
  • 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 Wednesday April 30th (30%), and a take-home final quiz during May 31 – June 2 (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 and Stargates and for using the Kansei testbed on April 21st in class and on April 23rd in DL280 from 6:30-7:30pm. 
  • There will be no class on Wednesday May 14th.  Professor Arora will be traveling.
  • Monday, May 29th is a holiday.

 

Our newsgroup is cse.project.siefast.

 

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

 

MF 11:25am-12:25pm

 

Grader

 

Mr. Brian Larkins, DL474, larkins@cse.ohio-state.edu, phone: 668-7552, office hours: T 10:30-11:30, R 2:30-3:30

 

 

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.)

HW1

HW2

HW3

HW4

Reading assignment: Survey on Clock Synchronization in Wireless Sensor Networks

Timesync One and Two

Reading Assignment Distributed Reset

Peer to Peer Survey