Given a system of four concurrent threads t 1 , t 2 , t 3 , and t 4 , we take a

Question

Given a system of four concurrent threads t1 , t2 , t3 , and t4 , we take a snapshot of the consistent state of the system after 3, 2, 4, and 3 events in each thread, respectively; all but the second event in each thread are local events. The only communication event in thread t1 is to send a message to t4 and the only communication event in thread t3 is to send a message to t2. Draw a space-time diagram showing the consistent cut; mark individual events on the thread ti as eij .

How many messages are exchanged to obtain the snapshot in this case? The snapshot protocol allows application developers to create a checkpoint. An examination of the checkpoint data shows that an error has occurred, and it is decided to trace the execution. How many potential execution paths must be examined to debug the system?

Explanation / Answer

A protocol to construct consistent global states. The protocol has three steps: Process p0 sends to itself a take snapshot message. Let pf be the process from which pi receives the take snapshot message for the first time. Upon receiving the message, the process pi records its local state and relays the take snapshot along all its outgoing channels without executing any events on behalf of its underlying computation; channel state is set to empty and process pi starts recording messages received over each of its incoming channels. Let ps be the process from which pi receives the take snapshot message beyond the first time; process pi stops recording messages along the incoming channel from ps and declares channel state between processes pi and ps as those messages that have been recorded.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.