CS5414 (Fall 2012) Homework 2
Snapshot Algorithms for Rings

Due: 11pm, Sept 14
Relative weight: 5 units

General Instructions. You are expected to work alone on this assignment.

Submit your solution using CMS. No late assignments will be accepted.

To facilitate grading, format your solutions as follows.

Solutions that do not satisfy the formatting guidelines will be returned, ungraded.


Consider an asynchronous distributed system comprising processors p_0, p_1, ..., p_N. So, by definition, local processor clocks are not synchronized with each other or with real-time, and there are no bounds on message delivery delays.

Further suppose the communications topology is a ring of uni-directional FIFO reliable channels. Thus, the only direct communications allowed in this system is for a processor p_i to send messages to its unique successor in the ring---i.e., processor p_i may send only to processor p_(i+1 mod N+1), for 0 <= i <= N.

  1. Give a snapshot algorithm that is specialized for this exact ring communications topology. In any execution of your algorithm, Your algorithm should include no additional functionality beyond what is required for systems having this topology.

  2. Argue that a snapshot produced by executing your algorithm is always a consistent cut.

  3. Is it possible to add additional reliable FIFO links to the communications topology and still have the snapshot algorithm described for part 1 be correct? Characterize the properties of links that can be added without destroying correctness.