CS5414 (Fall 2010) Homework 3
Snapshots in Synchronous Systems
Due: 9:00am, 9/29/2010
Relative weight: 6 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.
Solutions that do not satisfy the formatting guidelines will be
returned, ungraded.
The Chandy-Lamport snapshot algorithm assumes the asynchronous model of computation.
Consider a synchronous system with N processors interconnected by unidirectional channels.
The topology of the interconnections between processors is fixed, but unspecified.
In addition, assume:
-
Each processor p has a single core and has a hardware clock Cp.
These hardware clocks are synchronized within D of each other.
That is, for all processors p and q and all real times t:
0 <= | Cp(t) - Cq(t) | <= D
where | x | denotes the absolute value of x.
The hardware clocks may not be changed or reset by any executing program, because
this will destroy their synchronization.
-
The message-delivery delay for channels
that connect pairs of processors is bounded from below by DDmin and from above by DDmax
(as measured by the hardware clock at any of the processors).
-
Each processor is fast enough and its outgoing channels have sufficient buffer capacity
so that
IF the processor "broadcasts" a message on all of its outgoing channels
THEN
the messages en route will all be delivered between DDmin and DDmax seconds
from the start of the broadcast.
Part I.
Give an algorithm the individual processors can use use to take local
snapshots that, along with channel states they compute,
constitute a consistent cut.
Like the Chandy-Lamport algorithm, yours should work with any fixed network
topology where
-
there is a path (perhaps indirect) from each processor to every other, and
-
each processor only knows it's outgoing and incoming
communications channels.
Unlike the Chandy-Lamport algorithm,
yours should attempt to minimize the
snapshot elapsed time, which is the time that passes between
the snapshot's start time and the snapshot's end time,
defined as follows.
- start time is the first instant that any processor stores
its local state or starts computing a channel state for the snapshot, and
- end time is the next instant that no processor
is still executing part of the snapshot algorithm.
Assume for this elapsed-time calculation that processor execution time and storing
a processor's local state is inconsequential
but message delivery delay is not.
If needed, other reasonable assumptions about timing may also be
imposed---be sure to state these;
fewer assumptions are better.
Part II.
Give the elapsed-time calculation for your algorithm.
Part III.
Argue that the snapshot your algorithm generates is a consistent cut.