Distributed computing

Download 0,86 Mb.

1 ... 10 11 12 13 14 15 16 17 ... 38

Bog'liq
distcomp

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.)

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.)

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.

Download 0,86 Mb.

Do'stlaringiz bilan baham:

1 ... 10 11 12 13 14 15 16 17 ... 38