Examples: Combining Algorithms

These examples show how to compose or combine algorithms.

Snapshot Termination Detection

This algorithm combines the global snapshot algorithm and diffusing computations to get an algorithm that is initiated by a single agent which detects when the snapshot algorithm has terminated.

Single initiator of snapshot

An earlier module gave the rules for the global snapshot algorithm. These rules allow multiple agents to start recording their states either independently or when they receive markers from other agents who have recorded their own states. Now, let's design an algorithm in which a single agent, called the initiator is the only agent that records its state independently, and all other agents record their states only when they receive markers.

Initiator detects termination of snapshot

A global snapshot is complete when all agents have recorded their own states and the states of all incoming channels. The rules for the snapshot algorithm don't specify how an agent detects that the global snapshot is complete. Now let's look at an algorithm by which the initiator detects that the snapshot algorithm is over. In this algorithm the initiator does not get the local snapshots of all the agents; the initiator merely detects that the states of all agents and channels have been recorded.

Problem Specification

A system is as specified in diffusing computations. There is a channel from agent \(x\) to agent \(y\) if and only there is a channel from \(y\) to \(x\). All agents are reachable, by a sequence of channels from an agent called the initiator.

Modify the global snapshot algorithm so that it is started by a single agent which detects that the algorithm has terminated.

Solution: Combine Algorithms

The solution is a diffusing computation algorithm which takes global snapshots.

A message in the diffusing computation is a marker in the snapshot algorithm. When a message (i.e. marker) is received by an idle agent the agent becomes active, sends messages (i.e., markers) specified by the snapshot algorithm, and becomes idle.

The diffusing computation terminates when all agents are idle and all channels are empty. So the computation terminates when each agent has completed its step of the snapshot algorithm, and when all markers have been received. This implies that at termination the states of all agents and channels have finished being recorded.

Initiator Acquires the Global Snapshot

In the algorithm given above the initiator detects that the global snapshot is complete --- i.e., each agent has finished recording its state and the states of its incoming channels. The algorithm does not show how the local information of each agent is sent to the initiator. An algorithm to send agent information to the initiator operates in two phases.

Execute a diffusing computation in which the initiator detects that a global snapshot is complete.
Initiate the algorithm to acquire graph information. The information that is acquired from each agent is its recorded state and the recorded states of its incoming channels.

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology