CS5414 (Fall 2012) Homework 2
Snapshot Algorithms for Rings
Due: 11pm, Sept 14
Relative weight: 5 units
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
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.
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
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.
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.
- p_0 initiates the snapshot.
- each processor sends exactly one message.
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.