Algoritmo de Lamport

Suponhamos a existência de uma computação infinita em que o sítio i requisitou a seção crítica num instante T_i, e nunca conseguiu.
Se i não conseguiu, é porque existe um sítio j que nesta computação:
- enviou um <T_j:j,request> para i, com prioridade superior a <T_i:i,request>, e que nunca saiu da fila de i,
- isto nao aconteceu, mas j nunca enviou uma mensagem para i com prioridade inferior a <T_i:i,request>
No segundo caso, j teria recebido o <T_i:i,request>, e não teria enviado para i o <T_j:j,ack> correspondente, o que não pode acontecer;
No primeiro caso, j não enviou <T'_j:j, release>, e como todo sítio entrega o recurso crítico após um tempo finito, o único motivo para j ter morrido de fome é a existência de j', mais prioritário que j, que também morreu de fome, por culpa de j'', mais prioritário que j', e assim por diante.

Como não existe uma sequência infinita como esta, a computação com inanição não pode existir, c.q.d.

Next: Exemplo Up: O Algoritmo de Lamport: Previous: Algoritmo de Lamport -