Group Communication Notes

Comunicação em Grupo

Caracterização

/

• Definição:

  • Processos pares, sem papéis especiais.

  • Comunicação entre iguais.

• Recursos:

  • Necessidade de mecanismos para prevenir condições de corrida.

  • Condições de corrida podem levar a dados inconsistentes se os recursos partilhados forem acedidos de forma não segura.

• Memória:

  • Sem espaço partilhado.

  • Sincronização por mensagens.

• Pressupostos:

  • Tempo de transmissão finito, sem perda de mensagens.

Acesso Centralizado

• Modelo:

  • Adaptação cliente-servidor com serialização de pedidos.

• Guardião:

  • Processo dedicado que gere o acesso ao objeto partilhado.

  • Monitoriza e concede acesso.

Visão Geral do Protocolo

• Processos $p<em>i$ comunicam com guardião $p</em>N$.

  • Solicitar: $p<em>i$ envia pedido a $p</em>N$ e espera resposta.

  • Resposta: $p_N$ concede acesso ou coloca em espera.

  • Conceder: $p_i$ acede ao objeto.

  • Libertar: $p<em>i$ envia mensagem a $p</em>N$; $p_N$ concede acesso ao próximo.

Comentários

• Sobrecarga:

  • Envolve três mensagens por acesso.

• Limitação:

  • Dependência de um guardião.

• Falha:

  • $p<em>N$ é crítico; falha de $p</em>N$ paralisa o sistema.

Anel Lógico

• Topologia:

  • Processos em ciclo fechado.

• Restrições:

  • Cada $p<em>i$ recebe de $p</em>{(i-1) \mod N}$ e envia para $p_{(i+1) \mod N}$.

• Testemunho (Token):

  • Acesso restrito ao processo que detém o testemunho.

Visão Geral do Protocolo

• Solicitar:

  • $p_i$ espera pelo testemunho, acede ao objeto e envia o testemunho.

• Sem Necessidade:

  • $p_i$ encaminha o testemunho.

Comentários

• Sobrecarga:

  • Troca de mensagem constante.

• Eficiência:

  • Bom para grupos pequenos.

• Escalabilidade:

  • Espera longa em grupos grandes.

Ordenação Total de Eventos

• Exclusão Mútua:

  • Uso de relógios lógicos de Lamport.

• Timestamps:

  • Incluem timestamp do evento de envio.

Algoritmo

• Inicialização:

  • $state = outsideCR$, $requestMessageReady = false$

• Entrar:

  • $state = wantIn$, $numberOfRequestsGranted = 0$

  • Envia pedido e espera até $(numberOfRequestsGranted == N-1)$

  • $state = insideCR$

• Sair:

  • $state = outsideCR$, $requestMessageReady = false$

  • Liberta acesso.

• Receber Pedido:

  • Lida com base no estado e prioridade.

Comentários

• Sobrecarga:

  • $2(N-1)$ mensagens por acesso.

• Eficiência:

  • Bom para grupos pequenos.

• Escalabilidade:

  • Intenso em comunicação para grupos grandes.

Minimizar Mensagens

• Modelo:

  • Permissão baseada em subconjuntos de processos.

• Interseção:

  • Grupos devem-se intersetar para garantir exclusão mútua.

• Votação:

  • Acesso concedido por votos do grupo.

Estrutura do Grupo

• Cada $p<em>i$ pertence a $V</em>i$.

• Propriedades:

  • $V<em>i \subseteq {p</em>0, p<em>1, …, p</em>{N-1}}$

  • $p<em>i \in V</em>i$

  • $V<em>i \cap V</em>j \neq \emptyset$

  • #(Vi) \approx #(Vj)

  • Cada $p_i$ pertence a $M$ grupos.

Algoritmo

• Inicialização:

  • $state = outsideCR$, $voted = false$

• Entrar:

  • $state = wantIn$, espera votos de $V_i$

  • $state = insideCR$

• Sair:

  • Liberta acesso para $V_i$

• Receber Pedido/Libertação:

  • Gerir estado e votos.

Comentários

• Complexidade:

  • Aproximadamente $3 \times \mathcal{O}(\sqrt{N})$ mensagens.

• Escalabilidade:

  • Mais eficiente para grupos grandes.

• Problema:

  • Potencial deadlock.

Solução para Deadlock

• Ordenação total dos pedidos.

• Fila de prioridade por timestamp.

• Mecanismo de fallback centralizado.

Eleição

• Objetivo:

  • Selecionar um processo para uma tarefa específica.

• Requisitos:

  • Terminação, não ambiguidade, consenso.

Pressupostos

• Grupo fixo, estados de processo (em execução ou falha), tempo de transmissão limitado, fiabilidade