Algoritmo de Huang

El algoritmo de Huang es un algoritmo para detectar la terminación en un sistema distribuido . El algoritmo fue propuesto por Shing-Tsaan Huang en 1989 en Information Processing Letters . ^[1]

Detección de terminación

La base de la detección de terminación se encuentra en el concepto de estado de un proceso de un sistema distribuido. En cualquier momento, un proceso de un sistema distribuido puede estar en un estado activo o en un estado inactivo. Un proceso activo puede volverse inactivo en cualquier momento, pero un proceso inactivo solo puede volverse activo nuevamente al recibir un mensaje computacional.

La terminación ocurre cuando todos los procesos del sistema distribuido quedan inactivos y no hay mensajes computacionales en tránsito.

Algoritmo

El algoritmo de Huang se puede describir de la siguiente manera:

• Inicialmente todos los procesos están inactivos.
• Una tarea distribuida se inicia cuando un proceso envía un mensaje computacional a otro proceso. Este proceso inicial que envía el mensaje es el "agente controlador".
  • El peso inicial del agente de control es (normalmente 1). ${\displaystyle w}$
• Las siguientes reglas se aplican durante todo el cálculo:
  • Un proceso que envía un mensaje divide su peso actual entre él mismo y el mensaje.
  • Un proceso que recibe un mensaje agrega el peso del mensaje a sí mismo.
  • Al quedar inactivo, un proceso envía un mensaje que contiene todo su peso al agente controlador y queda inactivo.
  • La terminación se produce cuando el agente de control tiene un peso de y está en estado inactivo. ${\displaystyle w}$

Algunas debilidades del algoritmo de Huang son que no puede detectar la terminación si un mensaje se pierde en tránsito o si un proceso falla mientras está en un estado activo.

Véase también

• Algoritmo de Dijkstra-Scholten

Notas

1. Huang, Shing-Tsaan (1989). "Detección de terminación mediante el uso de instantáneas distribuidas". Information Processing Letters . 32 (3): 113–119. doi :10.1016/0020-0190(89)90010-0.