Maekawa (1985)

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.