Un algoritmo distribuido es un algoritmo diseñado para ejecutarse en hardware informático 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 de información distribuida 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 árbol de expansión , exclusión mutua y asignación de recursos . [1]
Los algoritmos distribuidos son un subtipo de algoritmo paralelo , normalmente ejecutados al mismo tiempo , en los que partes separadas del algoritmo se ejecutan simultáneamente en procesadores independientes y 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 ante fallas del procesador y enlaces de comunicaciones poco confiables. La elección de un algoritmo distribuido apropiado para resolver un problema determinado 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 de tiempo 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 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 solo 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 ejecutar un algoritmo de elección de líder, cada nodo de la red reconoce a un nodo particular y único 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 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 entregarán 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 un ordenamiento 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
- 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 la satisfacibilidad booleana, Bionetics2007, págs. 66–69, 2007.
enlaces externos
- Medios relacionados con algoritmos distribuidos en Wikimedia Commons
- Material didáctico abierto del MIT: algoritmos distribuidos
Medios relacionados con algoritmos distribuidos en Wikimedia Commons