previous up next
Go backward to B.1 Problem
Go up to B Distributed Snapshots
Go forward to B.3 Program
RISC-Linz logo

B.2 Algorithm

We implement the solution of the problem by an application of the Chandy-Lamport Algorithm for determining consistent global snapshots of a network5. In our case, this algorithm is applied as follows:

The following figure illustrates the basic idea of the algorithm: the stream of messages passing through a channel is split by the snap message into two parts; a node's snapValue eventually represents the value of the node after having processed all messages within the partition bounded by the snap messages of the incoming and outgoing channels. Since every message is contained in exactly one such partition, the sum of all snapValues represents the total network value.

Distributed Snapshots: Basic Idea
 

In order to broadcast a node's snapValue to every other node of the network, the following (simple-minded) strategy is applied:

The program thus ultimately terminates in a state where every node holds the same totalValue which represents the value of the network.


Maintainer: Wolfgang Schreiner
Last Modification: November 14, 1997

previous up next