O problema consiste em determinar a topologia de uma rede, a partir de uma situação inicial em que cada nodo conhece apenas os seus vizinhos e o número de nodos da rede. A partir daí, executa-se uma seqüência finita de passos, em que os nodos trocam informações, até que a topologia da rede seja conhecida por todos.
A solução do problema com o algoritmo heartbeat consiste na execução de uma seqüência de passos. No primeiro passo, o nodo informa aos seus vizinhos a própria topologia e conhece a topologia dos seus vizinhos. No segundo passo, o nodo conhece os vizinhos dos vizinhos e assim sucessivamente, até que todos os nodos conheçam a topologia completa da rede.
A linguagem escolhida para a implementação foi "C", utilizando sockets para comunicação entre nodos. O programa foi compilado com GCC no sistema operacional Linux (RedHat-5.1). Código fonte disponível.
O programa é ativado através de chamada via linha de comando, recebendo como parâmetros o número de nodos e o endereço IP dos vizinhos do nodo. Nessa implementação, existe a limitação de no máximo três vizinhos por nodo.
O programa executa um fork, ficando o processo pai responsável pelo recebimento das topologias dos vizinhos e o processo filho pelo controle da topologia. O processo pai, ao receber uma mensagem, escreve essa mensagem em um pipe compartilhado com o processo filho, avisando-o através do envio do sinal SIGUSR2. O processo filho enviará a sua topologia a todos os seus vizinhos e ficará aguardando a sinalização do processo pai do recebimento de uma nova mensagem. Essa seqüência de operações será realizada até que o nodo conheça toda a topologia da rede.
Como procedimento final, o processo filho enviará a sua topologia para os vizinhos que ainda estão ativos. Como os vizinhos podem estar fazendo o mesmo, efetua um recebimento dos vizinhos ativos para limpar os canais de comunicação.
Para resolver o problema de nodos mais rápidos, foi necessário implementar o controle por nome de nodo e por passo. Dessa forma, cada mensagem carrega consigo o nome do nodo que a enviou e o passo em que essa mensagem foi gerada.
Pela forma de controle, o processo filho "sabe" de qual vizinho a mensagem deve ser lida e qual o passo em que a mensagem foi gerada. Assim, se a mensagem não preencher esses requisitos, ela será armazenada em estrutura criada para esse fim, devendo ser lida posteriormente, sendo esse processo novamente efetuado até que a mensagem correta seja recebida.
O programa foi testado com sucesso em um ambiente com até oito máquinas, sem problemas na determinação da topologia. A fim de possibilitar a execução do programa em todos os nodos da rede, o processo pai inicia sua execução imediatamente (receive), ficando o filho em processo de espera (sleep) por vinte segundos (send).
A implementação do recepção condicionada a identificação do vizinho (IP), exige que a identificação informada via linha de comando quando do disparo do programa seja igual a informação contida na estrutura de mensagem do nodo vizinho. No caso de máquinas com mais de um endereço IP, pode acontecer um dead-lock, em virtude do não recebimento da mensagem corretamente identificada.
ANDREWS, G. R. Concurrent Programming - Principles and Practice. The Benjamin/Cunnings, Redwood City, 1991.
GEYER, Claudio. Programação Distribuída e Paralela. UFRGS, Porto Alegre, 1998. (Notas de Aula)