O Algoritmo de Naimi-Trehel

Nesta seção vamos apresentar o algoritmo de Naimi-Trehel[Naimi and Trehel, 1987], redescoberto de forma independente por Guilherme Pádua em 1994, então aluno de iniciação científica.
É a versão do Guilherme, com contribuições do Marco Aurélio, do Kemio e minhas que é apresentada aqui
utiliza um token com informação suficiente para manter uma fila de requisições,
reduz a complexidade média para ${\cal O}(\log{n})$ mensagens, cujo tamanho entretanto é da ordem de n
um sítio i com fome envia um único request para o sítio next_i, que ele julga deter o token;
um sítio j que recebe um request do sítio i,
- se estiver com fome ou comendo armazena a requisição em uma fila local;
- ao terminar de comer, j envia o token para o sítio mais prioritário em sua fila local; a fila é enviada junto com o token, e esvaziada em seguida. next_j passa a apontar para o sítio menos prioritário nesta fila.
- se estiver pensando e não estiver de posse do token, o request é retransmitido para o sítio next_j; next_j passa a apontar para o sítio que originou o request recebido (que pode ser diferente do sítio que enviou o request)

Next: State Variables and Initial Up: Exclusão Mútua Distribuída Previous: Carvalho e Campos: Exemplo