Due in class, Thursday October 31, 2002

• CS 4230 students: You need only complete the questions in Part I. Part II may be completed for extra credit.
• CS 6236 students: You must complete all of the questions in both Part I and Part II.

Part I

1. A Time Warp simulation contains four LPs (LP0, LP1, LP2, and LP3). Each LP executes on a separate processor, and initially contains one unprocessed event in its input queue. LP0’s event has time stamp 1, LP1’s event has time stamp 10, LP2’s event has time stamp 11, and LP3’s event has time stamp 12. When an event with time stamp T is processed in LPi, at the end of processing that event, a new event is scheduled for LPi+1 (using modulo 4 arithmetic) with time stamp T+2. Processing an event requires 1.0 seconds of wallclock time. Assume state saving, message transmission, rollback, event cancellation, and other overheads take a zero time. Assume that rollback and event cancellation computations always take precedence over normal event processing. Show the first five seconds (wallclock time) of execution of this Time Warp simulation. In each second indicate for each LP:

1. what event is processed by that LP that second,

2. the contents of the input queue at the end of the second,

3. the contents of the output queue at the end of the second,

4. what events, if any are rolled back, and

5. what events, if any are cancelled.

2. Samadi’s algorithm (as does Time Warp) for computing GVT assumes no messages are lost. Explain what would happen in Samadi’s algorithm if an acknowledgement message were lost. Specifically, explain what would happen in an execution where a single “marked” acknowledgement message was lost. Explained what would happen in another execution where a single unmarked acknowledgement message was lost.

3. Develop a variation on Time Warp that uses rollback, but eliminates the need for anti-messages, thereby eliminating the possibility of secondary rollbacks. Describe how Time Warp’s local and global control mechanisms must be modified to create a new synchronization mechanism with this characteristic.

4. Consider Mattern’s algorithm for computing GVT. Consider the execution below, where arrows denote message communication and the solid lines denote cuts C1 and C2. Show the contents of the vector counters for green messages (messages sent prior to C1) for each LP at cut C1 and again at cut C2.

Part II

1. Mattern’s algorithm was described using a ring to construct cuts in the distributed system. Design a version of Mattern’s algorithm that uses a Butterfly rather than a ring to compute GVT values. Describe the algorithm at the same level of detail as the description in the lecture notes (or textbook).