Distributed Algorithms Contents Index

Applications of Diffusing Computation

This module describes diffusing computation algorithms by which an agent learns properties of the network in which the agent is situated.

Diffusing computations are used by an agent to learn properties of the network in which the agent is embedded. We will first look at cases in which the network is static and then study an algorithm in which an agent learns properties of the network while the network is changing.

In this problem, agents are in a static network. If there is an edge from an agent \(x\) to an agent \(y\), in the network, then there is an edge in the reverse direction.

Acquiring Graph Information

Associated with each agent \(x\) is some constant value, \(x.v\), where \(x.v\) is arbitrary. For example \(x.v\) could be: the coordinates of agent \(x\) in 3D space, or agent \(x\)'s lists of assets and liabilities, or the files for which it has exclusive locks.

An agent, called the initiator, starts a computation by which it learns the values of all the agents in the network. When the the computation terminates, the initiator will have a set \(initiator.values\) where the elements of the set are pairs \((x, x.v)\), with one element for each agent in the system.

We first give the program and then prove its correctness. The program is a simple version of a diffusing computation. The simplification comes from the facts that:

  1. Each agent becomes active only when it receives its first message. It doesn't change its active/idle state when it receives subsequent messages. So each agent changes from idle to active exactly once.
  2. After an agent sets its parent to a non-null value, it does not change its parents thereafter. So, the tree grows, and once an edge of the tree is created that edge is never changed.
  3. For each channel \(c\), exactly one message and exactly one ack traverses the channel in the algorithm

By contrast, in a general diffusing computation an agent may become active multiple times because each time an idle agent receives a message it becomes active. In the general case, edges of the tree are created and may be later deleted.

Associated with each agent \(x\) is a local boolean variable \(x.received\_all\_acks\) which is True exactly when agent \(x\) has received acks for all the messages that it has sent.

Each ack has a field called values which is a set. The elements of this set are pairs \((x, x.v)\) where \(x\) is an agent.

Simpler Version

Initially, \(x.parent = null\) for all agents \(x\) other than the initiator.

The initiator starts the computation by executing the following program: 

initiator.values = {(initiator, initiator.v)}
send a message to each neighbor of the initiator
Next we give the program for an agent \(x\) other than the initiator. 

1: if (x.parent == null) and (x receives a message from y):
       x.parent = y
       // x.parent does not change from now onwards.
       x.values = {(x, x.v)}
       send a message to each neighbor of x other than x.parent

2: if (x.parent != null) and (x receives a message from y):
          send ack(values = {}) to y

3: if x receives an ack
          // set x.values to the union of x.values and ack.values.
          x.values = union(x.values, ack.values)
          if x.received_all_acks:
               send ack(values=x.values) to x.parent

Proof outline

The steps of the proof are as follows:
  1. An agent \(x\) changes \(x.parent\) exactly once from \(null\) to a non-\(null\) value. The initiator is the ancestor of all agents \(x\) for which \(x.parent\) is not null. The tree propagates to span all agents reachable from the initiator.
  2. For each agent \(x\), its value \((x, x.v)\) is propagated exactly once to its parent. This value is then propagated along edges of the tree through ancestors of \(x\) to the initiator.

Examples

The algorithm can be optimized for problems in which the initiator has to discover different kinds of information about graphs. For example, if agents have colors and the initiator has to discover the numbers of agents of each color, then values can be counts of agents of each color, and counts can be summed instead of taking unions of sets.

Example

Next, we look at an example of an algorithm in which an agent acquires a specific kind of graph information. An agent has a color, either red or blue, and the color does not change. The initiator has to discover whether there exists at least one red agent in the network. An optimization is that if the diffusing computation reaches a red agent then the red agent does not diffuse the computation even further. We give the optimized algorithm, program 2, below. It's proof of correctness is similar to the proof of program given above.

Program 2: Detecting a red agent

1: if (x.parent == null) and  (x receives a message from y):
        x.parent = y
        if x.color == red:
             send ack(color=red) to y
        else:
             send a message to all neighbors of x other than y

2: if (x.parent != null) and x receives a message from y:
          send ack(color=x.color) to y

3: if (x receives an ack A) and (x has not sent an ack to x.parent):
        if A.color == red:
              send ack(color=red) to x.parent
        elif x.received_all_acks:
              send ack(color=blue) to x.parent

If the initiator receives at least one red ack then the network has a red agent. If the initiator receives only blue acks then the network has no red agent.

Termination Detection Revisited

We described the problem of detecting that a computation has terminated in the module on global snapshot applications. We also described an algorithm to solve that problem in the module. Now we give another algorithm to solve the same problem. This algorithm combines diffusing computation and the snapshot algorithm, and is a small modification of program 2.
Problem Specification

For convenience, the problem definition from the earlier module is repeated here.

An agent is either idle or active. An idle agent remains idle until it receives a message. An idle agent does not send messages. An active agent may send messages. An active agent may become idle at any point. An idle agent becomes active when it receives a message. Initially all agents are active and all channels are empty.

A terminated state of the system is one in which all agents are idle and all channels are empty. terminated is stable: a system in a terminated state remains terminated thereafter. A system may or may not enter a terminated state. Our task is to develop an algorithm that detects that a system has entered a terminated state.

Algorithm
In analogy with program 2, let's give colors to agents. Let's specify that an agent that is idle throughout the snapshot algorithm is colored blue. An agent that is active at any point during the snapshot algorithm is colored red. The initiator has to discover whether any agent is red.

The differences between termination detection and the problem of detecting a red agent are that (1) agent colors may change during termination detection, and (2) termination detection has to detect properties of channels --- namely whether channels are empty --- in addition to detecting properties of agents. A surprising result is that program 2, with the addition of a statement to deal with channels, can be used for termination detection.

In the modified algorithm, the initiator takes its local snapshot when it initiates the algorithm. All other agents take their local snapshot when they set their parents to non-null values.

The statement that we add is: 

4: if (x.parent != null) and x receives a message:
          if x has not sent an ack to x.parent:
              send ack(color=red) to x.parent

Proof outline

Consider the following modification to the snapshot algorithm: replace the ack and message of program 2 by markers of the snapshot algorithm. The resulting program is identical to the snapshot algorithm with two differences:
  1. An ack in program 2 may be sent later than a marker is sent in a snapshot algorithm. In the snapshot algorithm, when an agent receives a marker for the first time it sends markers immediately. In the modified algorithm, however, an agent may not immediately send an ack when it receives a command. This is because of the elif clause in statement 3: an agent sends an ack only after receiving acks for all the messages that it sent.
  2. The snapshot algorithm takes snapshots of channels as well as agents. The modified algorithm doesn't mention channels.

Next, we address these two differences.

Late arrivals of markers don't matter for the purposes of detecting termination. If computation has terminated then agents will be idle when markers arrive, regardless of when they arrive. Likewise, the algorithm records channel states as empty, regardless of when markers arrive.

If \(x\) receives no messages after it takes its local snapshot and before receiving markers on all its incoming channels then all its incoming channels are empty. Statement 4 identifies the computation as not terminated when \(x\) receives a message.

Communication Deadlock Detection

Communication deadlock is identical to termination detection with one difference. An idle agent in termination detection becomes active if it receives a message from any agent. By contrast, in the communication deadlock problem, an idle agent becomes active only if receives a message from a set of agents for which it is waiting. An earlier module on deadlock detection developed algorithms to detect deadlock when an idle agent became active only if it received messages or resources from all the agents for which it is waiting. In the communication-deadlock case, an idle agent became active if it receives messages from any of the agents for which it is waiting.
Problem Specification
An agent is either active or waiting. Associated with each waiting agent \(x\) is a non-empty set \(x.waits\) of agents; \(x\) becomes active if it receives a message from any agent in \(x.waits\), and \(x\) remains waiting if it receives a message from an agent that is not in \(x.waits\). A waiting agent does not send messages. Active agents may send messages.
The Algorithm
The algorithm for communication deadlock detection is the same as that for termination detection except that the network is restricted to agents that are waiting. The network has a channel between a pair of agents if either agent in the pair is waiting for the other.

Review

  1. Modify the algorithm to count the number of red agents to count agents of all colors. Assume that colors of agents don't change.
  2. Now consider the case where each agent is either red or blue. A blue agent can become red. A red agent does not change its color. Develop an algorithm to obtain a lower bound on the number of red agents and an upper bound on the number of blue agents. The algorithm should get good bounds. (Obviously 0 is a lower bound and N, the number of agents is an upper bound.)

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