Algoritmo distribuido - Distributed algorithm

Un algoritmo distribuido es un algoritmo diseñado para ejecutarse en hardware de computadora construido a partir de procesadores interconectados . Los algoritmos distribuidos se utilizan en diferentes áreas de aplicación de la computación distribuida , como las telecomunicaciones , la computación científica , el procesamiento de información distribuida y el control de procesos en tiempo real . Los problemas estándar resueltos por algoritmos distribuidos incluyen elección de líder , consenso , búsqueda distribuida , generación de árbol de expansión , exclusión mutua y asignación de recursos .

Los algoritmos distribuidos son un subtipo de algoritmo paralelo , que normalmente se ejecuta al mismo tiempo , con partes separadas del algoritmo que se ejecutan simultáneamente en procesadores independientes y que tienen información limitada sobre lo que están haciendo las otras partes del algoritmo. Uno de los principales desafíos en el desarrollo e implementación de algoritmos distribuidos es coordinar con éxito el comportamiento de las partes independientes del algoritmo frente a fallas del procesador y enlaces de comunicaciones no confiables. La elección de un algoritmo distribuido apropiado para resolver un problema dado depende tanto de las características del problema como de las características del sistema en el que se ejecutará el algoritmo, como el tipo y la probabilidad de fallas del procesador o enlace, el tipo de comunicación entre procesos. que se puede realizar, y el nivel de sincronización de tiempo entre procesos separados.

Problemas estándar

Compromiso atómico
Una confirmación atómica es una operación en la que se aplica un conjunto de cambios distintos como una sola operación. Si la confirmación atómica tiene éxito, significa que se han aplicado todos los cambios. Si hay una falla antes de que se pueda completar la confirmación atómica, la "confirmación" se cancela y no se aplicarán cambios.
Los algoritmos para resolver el protocolo de compromiso atómico incluyen el protocolo de compromiso de dos fases y el protocolo de compromiso de tres fases .
Consenso
Los algoritmos de consenso intentan resolver el problema de una serie de procesos que acuerdan una decisión común.
Más precisamente, un protocolo de consenso debe satisfacer las cuatro propiedades formales siguientes.
  • Terminación : todo proceso correcto decide algún valor.
  • Validez : si todos los procesos proponen el mismo valor , entonces todo proceso correcto decide .
  • Integridad : todo proceso correcto decide como máximo un valor, y si decide algún valor , entonces debe haber sido propuesto por algún proceso.
  • Acuerdo : si un proceso correcto decide , entonces todo proceso correcto decide .
Los algoritmos comunes para resolver el consenso son el algoritmo Paxos y el algoritmo Raft .
Búsqueda distribuida
Elección de líder
La elección de líder es el proceso de designar un solo proceso como organizador de alguna tarea distribuida entre varias computadoras (nodos). Antes de que se inicie la tarea, todos los nodos de la red desconocen qué nodo servirá como "líder" o coordinador de la tarea. Sin embargo, después de ejecutar un algoritmo de elección de líder, cada nodo de la red reconoce un nodo único y particular como líder de la tarea.
Exclusión mutua
Estructuras de datos sin bloqueo
Transmisión confiable
La transmisión confiable es una primitiva de la comunicación en los sistemas distribuidos. Una transmisión confiable se define por las siguientes propiedades:
  • Validez : si un proceso correcto envía un mensaje, algún proceso correcto eventualmente entregará ese mensaje.
  • Acuerdo : si un proceso correcto entrega un mensaje, todos los procesos correctos eventualmente entregan ese mensaje.
  • Integridad : cada proceso correcto envía el mismo mensaje como máximo una vez y solo si ese mensaje ha sido enviado por un proceso.
Una transmisión confiable puede tener un orden secuencial, causal o total.
Replicación
Asignación de recursos
Generación de árbol de expansión
Ruptura de simetría, por ejemplo, coloración de vértices

Referencias

Otras lecturas

enlaces externos