Algoritmo de exclusión mutua distribuida de Lamport

El algoritmo de exclusión mutua distribuida de Lamport es un algoritmo basado en contención para la exclusión mutua en un sistema distribuido .

Algoritmo

Cada proceso mantiene una cola de solicitudes pendientes para ingresar a la sección crítica en orden. Las colas están ordenadas por marcas de tiempo virtuales derivadas de las marcas de tiempo de Lamport . ^{[ 1 ]}

Proceso de solicitud

Enrutando su solicitud en su propia cola (ordenada por marcas de tiempo).
Enviando una solicitud a cada nodo.
Esperando respuestas de todos los demás nodos.
Si su propia solicitud está al principio de la cola y se han recibido todas las respuestas, entre en la sección crítica.
Al salir de la sección crítica, elimine su solicitud de la cola y envíe un mensaje de liberación a cada proceso.

Otros procesos

Tras recibir una solicitud, esta se coloca en su propia cola de solicitudes (ordenadas por marcas de tiempo) y se responde con una marca de tiempo.
Tras recibir el mensaje de liberación, elimine la solicitud correspondiente de su propia cola de solicitudes.

Este algoritmo crea 3( N − 1) mensajes por solicitud, o ( N − 1) mensajes y 2 difusiones. 3( N − 1) mensajes por solicitud incluyen:

Este algoritmo tiene varias desventajas. Son las siguientes:

Es muy poco fiable, ya que el fallo de cualquiera de los procesos detendrá el progreso.
Tiene una alta complejidad de mensajes de 3( N − 1) mensajes por entrada/salida a la sección crítica.

↑ Kshemkalyani, A., y Singhal, M. Capítulo 9: Algoritmos de exclusión mutua distribuidos. Computación distribuida: principios, algoritmos y sistemas (página 10 de 93). Cambridge University Press.