-
-
-
-
CENAPAD-MGCO
A seguir: Princípios Básicos
Acima: Exclusão Mútua Distribuída
Anterior: Carvalho e Roucairol: Complexidade
- Para n nós,
-
o algoritmo de Lamport usa 3.(n-1) mensagens por
seção crítica,
-
Ricart e Agrawala usa 2.(n-1), e
-
Carvalho e Roucairol usa entre e 2.(n-1) mensagens por
seção crítica.
- Nesta aula vamos explorar o uso de esquemas de comunicação
para diminuir a ordem de complexidade na troca de mensagens.
- Os dois algoritmos - Maekawa (1985) e Carvalho e Campos (1987)
utilizam um esquema de comunicação definido por um grafo especial,
chamado de plano projetivo finito
- Usando planos projetivos finitos, a complexidade é reduzida para
, ao custo de uma indireção que penaliza a
transferência do recurso crítico em um tempo de
transmissão de mensagens.
Osvaldo Carvalho
-
Postscript -
Comentários?