Algoritmo de Carvalho e Campos (1991) - 1

GENIAL [de Aguiar Campos and Carvalho, 1988] fusão das idéias de Maekawa e de Chandy e Misra;
O esquema de comunicação é restrito por um plano projetivo finito ;
Conflitos são resolvidos pela profundidade dos nós num grafo acíclico ;
O número de mensagens trocadas por seção crítica varia entre 0 e um máximo que é $O(\sqrt(n))$ ;
Sítios agem como clientes e como árbitros;
Cada árbitro usa um permission token como autorização única disputada por seus clientes;
Para comer um cliente precisa da permissão de todos os seus árbitros;
Entre um cliente e um árbitro circula um request token, usado por ambos para pedir a permissão;
permissões podem estar sujas ou limpas ;
ao comer, um cliente suja todas as suas permissões ;
um cliente envia de volta a permissão de um árbitro no estado em que ela se encontra, suja ou limpa;
um árbitro só envia permissões limpas;
cada árbitro mantém uma lista de prioridades que ordena totalmente seus clientes;
esta lista só é modificada pelo árbitro na recepção de uma permissão suja, quando o cliente que a devolveu é movido para a última posição .

Next: Carvalho e Campos: Grafo Up: Exclusão Mútua Distribuída Previous: Algoritmo de Maekawa -