Heart Beat Algorithm

A heartbeat algorithm or systolic algorithm is executed by a synchronous array of cells ("systolic array") that perform only local computations and communications. They are a special form of synchronous algorithms. Every node, process or processor exchanges data only with its direct neighbors, and data is flowing synchronously across the array. The names "heartbeat" and "systolic" are chosen by analogy with the regular pumping of blood by the heart in living organisms, "systolic" is the Greek word for "to contract" and heartbeat. The asynchronous version of the heartbeat algorithm is named phase algorithm.

Definition

A heartbeat message is a periodical or regular message to a group of neighbors indicating that a process is still active and alive. A heartbeat algorithm works with heartbeat messages for each node, and is characterized by "rhythmic" expansion and contraction of information. Each node behaves like a beating heart.

The informal description goes like this: each node gives the information it has to his neighbors and asks them for their information. In the first round, every node knows his neighbors. In the second round, every node knows his neighbors and their neighbors. In each round the "horizon" is expanded by one "hop". After D rounds, where D equals the diameter of the network, each node has informations about the whole system.

Usually each processor at each step takes in data from all it's neighbors, processes it and, in the next step, all neighbors are informed about the results. The data flow can also be directed, for example each processor at each step can take in data only from some neighbours (e.g. North and West), and in the next round the outputs are sent in the opposite direction (South and East).

The pseudo code for a heartbeat algorithm is

. // define local parameters, e.g. lists
. // or arrays 
. declaration local Variables; 
. initialization local Variables; 
. wile (r<D) do
. {
.  // Synchronization
.  wait for central pulse generator or timer
.
.  // spread information (expansion)
.  send message to all neighbors;
.   
.  // collect information (contraction)
.  receive message from all neighbors;
.
.  // add new information to existing ones 
.  update local variables; 
.
.  // new round
.  r := r+1
. }

Application

As total algorithms, heart beat or systolic algorithms can be used to spread and collect information in a distributed system. An example is the "FloodMax" algorithm, an election algorithm which determines and selects the node with the highest ID in the system. In the "FloodMax" algorithm, each node informs his neighbors in each round about the node with the highest ID, receives in turn information from them, and updates its information accordingly.