Distributed computing

DISTRIBUTED SNAPSHOTS

• Intuitively, a snapshot is a freezing of a distributed computation at the “same time.”
• Given a snapshot, it is easy to detect stable conditions such as deadlock.
• (A deadlock condition doesn’t go away. If a deadlock held in the past and nothing has been done about it, then it still holds. That makes it stable.)

FORMAL NOTION OF SNAPSHOT

• Assume that each processor has a local clock, which is incremented after the receipt of and processing of each incoming message, e.g., a Lamport clock. (Processing may include transmitting other messages.)
• A collection of local times {tk|kεN}, where N denotes the set of nodes, constitutes a snapshot, if each message received by node j from node i prior to tj has been sent by i prior to ti.
• A message sent by i before ti but not received by j before tj is said to be in transit.
• The correctness criterion is that no message be received before the snapshot, which was sent after the snapshot. (Such a thing could never happen if the snapshot time at every site were a single global time.)

DISTRIBUTED SNAPSHOTS

• i

• j

• i

• j

• i

• j

• i

• j

• SITUATION I

• SITUATION II

• SITUATION III

• Time

• Time

• Time

• ti

• tj

• ti

• ti

• tj

• tj

• A MESSAGE FROM i TO J

• OK

• BAD

• IN TRANSIT -- OK

• ti is SNAPSHOT TIME FOR PROCESS i
• tj is SNAPSHOT TIME FOR PROCESS j

ALGORITHM

• Node i enters its snapshot time either spontaneously or upon receipt of a “flagged” message, whichever comes first. In either case, it sends out a “flagged” token to all neighbors and advances the clock to what becomes its snapshot time ti.
• Messages sent later are after the snapshot.
• This algorithm allows each node to determine when all messages in transit have been received.
• That is, when a node receives a flagged token from all its neighbors, then it has received all messages in transit.

• spontaneous

• received flagged token

• send flagged token; set snapshot