Heart Beat Algorithm

----
<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
----
=[http://yjucofi.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=
----
=[http://yjucofi.co.cc CLICK HERE]=
----
</div>
A '''heartbeat algorithm''' or '''systolic algorithm''' is executed by a
synchronous array of cells (&quot;systolic array&quot;) 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 &quot;heartbeat&quot;
and &quot;systolic&quot; are chosen by analogy with the regular pumping of blood by the 
heart in living organisms, &quot;systolic&quot; is the Greek word for &quot;to contract&quot; and 
heartbeat. The asynchronous version of the heartbeat algorithm is
named [[Phase Algorithm|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 &quot;rhythmic&quot; 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 &quot;horizon&quot; is expanded by one &quot;hop&quot;.
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&lt;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 Algorithm|total algorithms]], heart beat or systolic algorithms 
can be used to spread and collect information in a distributed system.
An example is the &quot;FloodMax&quot; algorithm, an [[Election_algorithm|election algorithm]]
which determines and selects the node with the highest ID in the system. In the 
&quot;FloodMax&quot; 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.

[[Category:Distributed Algorithms]]