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.

Put your name and net id on each page of your solution.

Typeset your solution, using 10 point or larger font and use 8.5 x 11 inch paper.

Use at most one page (both sides, if necessary) for each problem.

Start each problem's solution on a separate side.
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 realtime, and there are no bounds on message delivery delays.
Further suppose the communications topology is a ring of unidirectional 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 ringi.e., processor
p_i may send only to processor p_(i+1 mod N+1), for 0 <= i <= N.

Give a snapshot algorithm that is specialized for
this exact ring communications topology.
In any execution of your algorithm,
 p_0 initiates the snapshot.
 each processor sends exactly one message.
Your algorithm should include no additional functionality beyond
what is required for systems having this topology.

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

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.