Algoritmo de Carvalho e Campos (1991)

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

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: Aula 16 - Exclusão Previous: Algoritmo de Maekawa -