Aula 16 - Exclusão Mútua Distribuída

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 $O(\sqrt{n})$ , ao custo de uma indireção que penaliza a transferência do recurso crítico em um tempo de transmissão de mensagens.