UFMG - Pós-graduação em Ciência da Computação - Programação Paralela

A seguir: Algoritmo de Ricart e Acima: Relógios Lógicos e Timestamps Anterior: Algoritmo de Lamport -

Algoritmo de Lamport - Progresso

• 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 que
  • enviou um <T_j:j,request> para i, com prioridade superior a (T_i:i), e que nunca saiu da fila de i,
  • isto nao aconteceu, mas j nunca enviou uma mensagem com prioridade inferior a (T_i:i)
  • No segundo caso, j teria recebido o <T_i:i,request>, e não teria enviado o <ack> correspondente, o que não pode acontecer;
  • No primeiro caso, o único motivo para j ter morrido de fome é a existência de k, mais prioritário que j, que também morreu de fome, 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.