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 telecomunicaciones , computación científica , procesamiento distribuido de información y 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 árboles de expansión , exclusión mutua y asignación de recursos . [1]
Los algoritmos distribuidos son un subtipo de algoritmo paralelo , que normalmente se ejecutan de forma concurrente , con partes separadas del algoritmo que se ejecutan simultáneamente en procesadores independientes y tienen información limitada sobre lo que hacen 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 ante fallas del procesador y enlaces de comunicación poco 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 del enlace, el tipo de comunicación entre procesos que se puede realizar y el nivel de sincronización temporal entre procesos separados. [1]
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 se produce un error antes de que se pueda completar la confirmación atómica, la "confirmación" se cancela y no se aplicarán los cambios.
- Los algoritmos para resolver el problema de confirmación atómica incluyen el protocolo de confirmación de dos fases y el protocolo de confirmación de tres fases .
- Consenso
- Los algoritmos de consenso intentan resolver el problema de que varios procesos acuerden 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 cada 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 único proceso como organizador de alguna tarea distribuida entre varias computadoras (nodos). Antes de que comience la tarea, todos los nodos de la red desconocen qué nodo actuará como "líder" o coordinador de la tarea. Sin embargo, después de que se haya ejecutado un algoritmo de elección de líder, cada nodo de la red reconoce un nodo particular y único como el líder de la tarea.
- Exclusión mutua
- Estructuras de datos no bloqueantes
- Transmisión confiable
- La transmisión confiable es una primitiva de comunicación en sistemas distribuidos. Una transmisión confiable se define por las siguientes propiedades:
- Validez : si un proceso correcto envía un mensaje, entonces algún proceso correcto eventualmente entregará ese mensaje.
- Acuerdo : si un proceso correcto entrega un mensaje, entonces todos los procesos correctos eventualmente entregan ese mensaje.
- Integridad : cada proceso correcto entrega el mismo mensaje como máximo una vez y sólo si ese mensaje ha sido enviado por un proceso.
- Una transmisión confiable puede tener ordenamiento secuencial, causal o total.
- Replicación
- Asignación de recursos
- Generación de árbol de expansión
- Ruptura de simetría, p. ej. coloración de vértices
Referencias
Lectura adicional
- Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introducción a la programación distribuida segura y confiable (2. ed.), Springer, Bibcode :2011itra.book.....C, ISBN 978-3-642-15259-7
- C. Rodríguez, M. Villagra y B. Barán, Algoritmos de equipo asincrónicos para satisfacibilidad booleana, Bionetics2007, pp. 66–69, 2007.
Enlaces externos
- Medios relacionados con Algoritmos distribuidos en Wikimedia Commons
- MIT Open Courseware: Algoritmos distribuidos
Medios relacionados con Algoritmos distribuidos en Wikimedia Commons