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 muchas áreas de aplicación variadas 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 mutuay asignación de recursos . [1]
Los algoritmos distribuidos son un subtipo de algoritmo paralelo , que normalmente se ejecutan 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 en el 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. [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 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 cada proceso correcto decide .
- Integridad : todo proceso correcto decide como máximo un valor, y si decide algún valor, luego debe haber sido propuesto por algún proceso.
- Acuerdo : si decide un proceso correcto, entonces cada proceso correcto decide .
- Los algoritmos comunes para resolver el consenso son el algoritmo Paxos y el algoritmo Raft .
- Búsqueda distribuida
- 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 particular y único como líder de la tarea.
- 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
- ↑ a b Lynch, Nancy (1996). Algoritmos distribuidos . San Francisco, CA: Morgan Kaufmann Publishers . ISBN 978-1-55860-348-6.
Otras lecturas
- Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introducción a la programación distribuida confiable y segura (2. ed.), Springer, ISBN 978-3-642-15259-7
- C. Rodríguez, M. Villagra y B. Barán, ‹Ver Tfd› Algoritmos de equipo asíncronos para la satisfacción booleana , Bionetics2007, pp. 66–69, 2007.
enlaces externos
- Medios relacionados con algoritmos distribuidos en Wikimedia Commons
- MIT Open Courseware - Algoritmos distribuidos