Sistemas Distribuídos: Sincronização e Exclusão Mútua

Sincronização de Relógios

• Sincronização interna: Diferença entre tempo de relógios locais: D > 0, |Ci(t) – Cj(t)|, os relógios Ci concordam dentro do limite D.
• Monotonicidade: Se t' > t, então c(t') > c(t), significa que o tempo decorre sempre para frente.
• Correção interna: Ajusta os termos do relógio de software para sincronização: Hi(t) + β, para garantir a monotonicidade.
• Sistemas assíncronos: A maioria dos sistemas distribuídos é assíncrona, então trans = min + x (x >= 0), sendo min o tempo mínimo estimado.

Método de Cristian

• Método de sincronização externa com UTC.
• Assume tempos de ida e volta curtos.
• Utiliza servidor de tempo UTC.
• Desvantagens: Não é válido para redes congestionadas e possui um único servidor (ponto de falha).

Algoritmo de Berkeley

• Sincronização interna em rede local.
• Arquitetura mestre-escravo: O mestre consulta os escravos, calcula a média tolerante a falhas (eliminando relógios defeituosos) e envia ajustes individuais.
• Se o mestre falhar, é possível eleger outro.

Network Time Protocol (NTP)

• Visa a internet como rede para sincronização.
• Características: Alta precisão, filtragem de dados, redundância de servidores, sincronização frequente e servidores autenticados.
• Formas de sincronização: Multicast (baixa precisão), RPC (semelhante ao método de Cristian) e Simétrico (usado por servidores de stratum baixo).

Segurança e Comunicação

• Comunicação secreta: Alice e Bob compartilham uma chave secreta KAB. Alice usa C(KAB, M) para cifrar e Bob usa D(KAB, M) para decifrar.
• Chave pública: Bob envia uma mensagem para Alice encriptada com a chave pública dela; Alice a decifra usando sua chave privada.

Exclusão Mútua

Garante que apenas um processo por vez acesse um recurso compartilhado, essencial para dados, arquivos e operações em ambientes externos (ex: robôs cooperativos).

Algoritmos de Exclusão Mútua

• Algoritmo Centralizado: Um coordenador gerencia as solicitações de entrada na Região Crítica (RC).
• Algoritmo Distribuído: Baseado no algoritmo de Lamport. O processo envia uma mensagem (Id, Rc, Ts) para todos. O acesso é permitido após receber OK de todos os processos.
• Algoritmo Baseado em Token: Um token circula em um anel virtual; apenas o detentor do token pode acessar a RC.

Algoritmos de Eleição

Algoritmo Bully (Garcia-Molina, 1982)

Se o coordenador falha, um processo inicia uma eleição enviando mensagens para processos com identificadores superiores. O processo com o maior identificador vence e anuncia sua vitória.

Algoritmo de Anel

Os processos formam um anel. Ao detectar falha, o processo envia uma mensagem de eleição com seu ID. A mensagem circula, acumulando IDs, até retornar ao iniciador, que define o novo coordenador.

Deadlock

• Exclusão mútua: Recurso não compartilhável.
• Espera circular: Processos aguardando recursos mantidos por outros.
• Detecção: O coordenador verifica ciclos e pode encerrar um dos processos causadores para remover o deadlock.