Lista 2 Sistemas Distribuidos

Prévia do material em texto

Lista 2
Sistemas Distribuídos
3 de dezembro de 2019
1. Qual a necessidade de eleições em sistemas distribuídos?
Um algoritmo de eleição é necessário para escolher qual dos processos
desempenhará a função de coordenador do sistema. A eleição é necessá-
ria quando um sistema distribuído é iniciado pela primeira vez, ou então
quando o coordenador não consegue se comunicar com os demais pro-
cessos e também se o processo coordenador quiser se retirar da função.
2. Descreva os algoritmos de eleições abaixo:
• Algoritmo do anel: O algoritmo em anel, serve para eleger um líder
se os processos estiverem organizados em topologia anel, o processo
que possuir o maior identificador é eleito coordenador. Todos os
processos iniciam como não participantes e qualquer um pode iniciar
uma eleição. Os processos marcam a si mesmo como participante
e enviam uma mensagem com seu identificador no sentido horário.
Quando o processo recebe um identificador maior do que o seu, ele
o encaminha para o processo vizinho. Se o id que ele recebe é menor
do que o seu, ele encaminha o seu identificador para o vizinho. Se
nó recebe o identificador igual ao seu, então esse id deve ser o maior
e se tornará o coordenador e envia uma mensagem “eleito” para seu
vizinho finalizando a eleição.
• Algoritmo do valentão (Bully):O algoritmo de bully serve para ele-
ger um líder entre processos identificados por um identificador nu-
mérico, único, fixo e atribuído antes do início da eleição. Entretanto
neste caso a topologia não é limitada a um anel e cada um dos
processos pode se comunicar com qualquer outro no sistema. No-
vamente a execução do algoritmo busca eleger o processo de maior
identificador e fazer com que todos reconheçam o novo líder. Se um
dos processos identifica a perda de contato com o líder, inicia uma
1
nova eleição enviando a todos os outros uma mensagem contendo
seu identificador; todos os nós respondem ao processo que iniciou a
eleição com os seus próprios identificadores; se o processo que ini-
ciou a eleição verifica possuir o maior identificador entre todos os
outros, proclama-se líder e avisa todos os outros; senão aguarda que
o processo de maior identificador inicie uma eleição e se torne líder.
3. Suponha que dois processos detectam simultaneamente a perda
de um coordenador e ambos decidem forçar uma eleição usando
o algoritmo de Bully. O que acontece nesse caso? E o algo-
ritmo usado fosse o do Anel?
Acontece nesse caso que os dois processos enviarão as mensagens de
eleição com seus identificadores, se receberem respostas contendo iden-
tificador maior que o seus, o processo que respondeu e obtém o maior
id se tornará o novo coordenador. O algoritmo que não receber uma
resposta dos outros esse se torná o coordenador. O maior vence.
No algoritmo em anel, quando identificarem que o token do coordenador
foi perdido, pode acontecer de dois processos iniciarem a eleição mas
quando receberem o identificador de outro processo com identificador
maior ele saberá que perdeu. E outra vez é eleito o que tem identificador
maior.
4. Muitos algoritmos distribuídos requerem o uso de um processo
de coordenação. Até que ponto esses algoritmos podem ser
considerados distribuídos? Discuta.
Mesmo que algumas funções dos algoritmos distribuídos sejam em partes
centralizadas, não o desclassifica de ser distribuído. Esses algoritmos
usam de partes centralizadas, como coordenadores, e se beneficiam por
exemplo com menos envio/troca de mensagens. Portanto se não houver
outras partes, ou se não houver comunicação entre as partes então o
conceito de distribuído pode vir a ser perdido.
5. Defina exclusão mútua e exclusão mútua distribuída? Qual a
diferença fundamental entre elas?
A exclusão mútua é a solução para evitar problemas envolvendo recur-
sos compartilhados. Busca evitar que mais de um processo tenha acesso
ao mesmo tempo de um recurso compartilhado, garantindo que se um
processo está usando um arquivo compartilhado, outros processos serão
impedidos de utilizar o mesmo. Na exclusão mútua distribuída no má-
ximo um processo pode estar executando na seção crítica. Um processo
2
que requisita acesso à seção crítica, obtém este acesso em algum mo-
mento. Ou seja, não há deadlock ou starvation. Se uma requisição para
entrar na seção crítica aconteceu antes de outra, a entrada de seção crí-
tica é garantida na ordem. A principal diferença entre a exclusão mútua
e a exclusão mútua distribuída é que na distribuída não há o comparti-
lhamento de memória. Toda sincronização/coordenação precisa ser feita
através do envio de mensagens.
6. Por que é necessário realizar controle de concorrência em tran-
sações?
Para garantir a propriedade de isolamento em transações concorrentes,
não permitindo que a execução de uma transação interfira na execução
de outra, preservar a consistência do banco pela preservação da consis-
tência na execução das transações, resolver conflitos leitura-gravação e
gravação-gravação
7. Defina e ilustre o funcionamento do protocolo de confirmação
de duas fases.
O protocolo de confirmação de duas fases é projetado de forma a per-
mitir que qualquer participante cancele sua parte de uma transação.
Devido ao requisito da atomicidade, se uma parte de uma transação for
cancelada, a transação inteira também deverá ser cancelada. Na pri-
meira fase do protocolo, cada participante vota na confirmação ou no
cancelamento de uma transação. Quando um participante tiver votado
na confirmação de uma transação, ele não poderá cancelá-la. Portanto,
antes que um participante vote na confirmação de uma transação, ele
deve garantir que poderá executar sua parte do protocolo de confirma-
ção, mesmo que falhe e seja substituído nesse meio tempo. Diz-se que
um participante de uma transação está em um estado preparado para
uma transação se puder confirmá-la. Para garantir isso, cada partici-
pante salva, no meio de armazenamento permanente, todos os objetos
que tiver alterado na transação, junto com seu status – preparado. Na
segunda fase do protocolo, todos os participantes da transação tomam
uma decisão conjunta. Se um participante votar pelo cancelamento, a
decisão deverá ser o cancelamento da transação. Se todos os participan-
tes votarem na confirmação, a decisão será de confirmar a transação.
3
Figura 1: Protocolo Confirmação em Duas Fases
8. A operação create insere uma nova conta bancária em uma
agência. As transações T e U são definidas como segue:
T: aBranch.create(“Z”); U: z.deposit(10); z.deposit(20). De-
clare o saldo de Z após sua execução, nessa ordem. Essas
execuções são consistentes com as execuções serialmente equi-
valentes de T e U?
Saldo de Z será 20, pois no primeiro deposito de 10 a conta ainda não
tinha sido criada. Não são consistentes com as execuções serialmente
equivalentes de T e U, pois a operação create está sendo executada após
a primeira que é de depósito, fazendo com que o saldo final seja 20.
Executando de forma serial o saldo da conta Z seria 30, sendo contado
o primeiro deposito feito na conta.
9. Um servidor gerencia os objetos a1, a2,... an. O servidor
fornece duas operações para seus clientes: read (i) retorna o
valor de ai; write(i, Value) atribui Value a ai.
As transações T e U são definidas como segue:
T: x = read(j); y = read (i); write(j, 44); write(i, 33);
U: x = read(k); write(i, 55); y = read(j); write(k, 66).
(a) Apresente os resultados da execução sequencial de T e U.
j=44; i=55; k=66.
(b) Apresente uma interposição serialmente equivalentes das transações
T e U.
T: x = read(j); write(i, 33); write(j, 44); write(i, 55);
U: x = read(k); y = read (i) ; y = read(j); write(k, 66);
10. Explique por que a equivalência serial exige que, uma vez que
a transação tenha liberado uma trava sobre um objeto, ela
não pode obter mais nenhuma trava.
4
A forma correta é que a transação obtenha todas as travas que necessita,execute e após terminado o processo libere todas as travas. Isso é feito
para garantir a execução de todos os pares de operações conflitantes de
duas transações sejam executadas na mesma ordem.
11. Como é possível garantir o princípio do “tudo ou nada” para
as transações distribuídas mesmo na presença de falhas?
O princípio da atomicidade das transações afirma que para uma tran-
sação ocorrer ela deve seguir seu ciclo até o fim, caso contrário ela será
desconsiderada. Se uma transação atômica falha ela não será computada
e o sistema deve retornar ao estado em que estava antes da requisição
da mesma.
12. Como evitar impasses (deadlocks) distribuídos? Evitar é a
solução mais utilização? Justifique.
Garantindo que os empasses nunca ocorram. Gerenciador de transa-
ções verifica quando ela é iniciada e não permite que ela prossiga se
houver possibilidade de impasse. Geralmente os deadlocks não são evi-
tados, mas quando os mesmos ocorrem eles são tratados ou é realizada
a tentativa de resolvê-los.
13. Por que os UFIDs (Unique File IDentifiers) devem ser exclu-
sivos entre todos os sistemas de arquivos possíveis? Como a
exclusividade dos UFIDs é garantida?
Os UFIDs devem ser exclusivos pois são eles que irão identificar os
arquivos de forma única e exclusiva dentro do sistema. Para garantir
essa exclusividade, o UFID pode utilizar parte do endereço IP + relógio.
14. Quais são as principais características que um Sistemas de
Arquivos distribuídos deve apresentar? Descreva cada uma
delas.
Confiabilidade: São eficazes no fornecimento de armazenamento per-
sistente compartilhado para uso em intranets.
Redundância: Um arquivo pode ser representado por várias cópias em
diferentes localizações, melhorando a escalabilidade do serviço.
Escalabilidade: O serviço pode ser expandido de forma paulatina,
para lidar com uma ampla variedade de cargas e tamanhos de rede.
Tolerância a falhas: Por ser parte essencial nos sistemas distribuídos,
é essencial que o serviço de arquivo distribuído continue a funcionar di-
ante de falhas de clientes e servidores.
5
Consistência: Manutenção da consistência entre várias cópias dos da-
dos quando ocorrem atualizações.
Segurança: Autenticar as requisições dos clientes para que o controle
de acesso no servidor seja baseado nas identidades corretas de usuário
e para proteger o conteúdo das mensagens de requisição-resposta com
assinaturas digitais e criptografia de dados secretos.
15. Em linhas gerais quais são os principais benefícios que podem
ser obtidos com a replicação de dados? Dê exemplos.
Podemos citar como benefícios da replicação:
• Aumento da confiabilidade;
• Tolerância a falhas;
• Distribuição de carga.
16. Explique detalhadamente as estratégias de replicação ativa e
passiva.
Replicação passiva: Um único gerenciador de réplica (GR) trabalha
como primário e os demais como secundários - backups ou escravos.
Os front-ends (FE) se comunicam somente com o GR primário. GR
primário executa as operações e envia cópias dos dados atualizados para
os backups. Se o primário falhar, um dos backups será promovido para
atuar como primário. A sequência de eventos quando um cliente solicita
uma operação é:
• Requisição: é encaminhada pelo FE para o GR primário e possui
um único identificador de requisição.
• Coordenação: o GR primário trata todas as requisições atomi-
camente, em ordem, checa o id (reenvia resposta se não é novo
identificador).
• Execução: GR primário executa as requisições e armazena as res-
postas.
• Acordo/Consenso: se é atualização, GR primário envia estado
atualizado/resultado do objeto, identificador de requisição e res-
posta para todos os GR de backups. Os GR’s de backup enviam
uma confirmação.
• Resposta: GR primário envia resposta ao FE, que envia resposta
de volta para o cliente.
6
Replicação ativa: Os GR’s são máquinas de estado que desempenham
papéis equivalentes e são organizados como um grupo. Os FE’s enviam
suas requisições pormulticast para o grupo de GR’s, e todos processam a
requisição independentemente, mas de forma idêntica, e respondem. Se
qualquer GR falhar, isso não tem nenhum impacto sobre o desempenho
do serviço, pois o GR’s restantes continuam a responder normalmente.
A sequência de eventos após uma solicitação é a seguinte:
• Requisição: contém um identificador único e é enviada pelo FE
por multicast confiável ordenado a todos os GR
• Coordenação: comunicação de grupo garante que as requisições
são entregues a cada GR na mesma ordem.
• Execução: cada réplica executa a requisição. A resposta contém
o identificador de requisição exclusiva do cliente.
• Acordo/Consenso: não é necessário acordo, devido às primitivas
semânticas do multicast.
• Resposta: cada GR envia a resposta diretamente para o FE.
17. Explique a diferença entre capacidade de linearização e con-
sistência sequencial, e por que, em geral, é mais prático im-
plementar esta última.
Um serviço de compartilhamento de objetos replicado é dito linearizável
se obedecem à especificação de uma única cópia correta do objeto e é
consistente com os tempos reais com que cada operação ocorreu durante
a execução. Por outro lado, um serviço de compartilhamento de obje-
tos replicado é sequencialmente consistente se, para qualquer execução
(real) existe alguma intercalação de operações do cliente (virtual) que a
sequência interposta de operações satisfaz a especificação de uma única
cópia correta dos objetos e a ordem das operações de interposição é
consistente com a ordem do programa no qual cada cliente individual
as executou.
A consistência sequencial é mais prática de ser implementada pois não
exige ordenação total ou o tempo real . A única noção de ordem rele-
vante é a ordem dos eventos em cada cliente separado, ordem do pro-
grama em cada cliente.
18. Explique o funcionamento do sistema Gossip (fofoca).
A arquitetura Gossip foi desenvolvida para implementar serviços de alta
disponibilidade por meio da replicação de dados próximos aos pontos
7
onde os grupos de clientes precisam deles. Os gerenciadores de répli-
cas trocam mensagens periodicamente para transmitir as atualizações
que cada um recebeu dos clientes. Oferece dois tipos básicos de ope-
ração: Somente de leitura e atualizações que modificam mais não leem
o estado. Os FE’s enviam consultas e atualizações para o gerenciador
de réplica que escolherem (disponível e com tempo de resposta razoá-
vel). Os clientes (via frontend) podem interagir com qualquer réplica,
qualquer que esteja disponível e oferece bom tempo de resposta, desde
que haja uma réplica, há serviço. As réplicas sincronizam-se através de
fofoca, os updates são espalhados por epidemia.
19. O Bayou tem em comum com o Gossip o uso de um protocolo
epidêmico para disseminar as atualizações. Aponte e explique
as principais diferenças apresentadas nesses dois exemplos de
sistemas replicados.
Garantia de disponibilidade menor que Gossip pois cada gerenciador
de réplica receberá o mesmo conjunto de atualizações e aplicará essas
atualizações de maneira tal que os bancos de dados dos gerenciadores de
réplica sejam idênticos. Outra diferença é que o Bayou permite a detec-
ção/solução de conflitos da seguinte forma: Um gerenciador de réplica
ativa o procedimento de verificação de dependência antes de aplicar a
operação. Ele verifica se ocorreria um conflito caso a atualização fosse
aplicada e, para fazer isso, pode examinar qualquer parte do banco de
dados. Se a verificação de dependência indicar um conflito, então o
Bayou ativará o procedimento de integração da operação. Esse proce-
dimento altera a operação que será aplicada, de modo que ela obtenha
algo semelhante ao efeito pretendido, mas evite um conflito.
20. Explique com suas palavras como funciona o sistema de arqui-
vos desenvolvido pela Google.
O Google File System (GFS) é um sistema de arquivos criadopela Go-
ogle e pensado para seu ambiente. Ele suporta uma enorme quantidade
de dados processados diariamente. Um diferencial é o uso de muitas
máquinas de baixo custo com capacidade de armazenamento alta e su-
porte a muitos acessos. Os arquivos são divididos em partes de tamanho
fixo de 64 Mb, chamadas de chunck ; cada chunck é identificado por um
chuck handle de 64 bits; por confiabilidade cada chunck é replicado em
múltiplos chunkservers (por padrão, 3 réplicas). Um mestre GFS só
é contatado apenas para obter informações de metadados. Um cliente
8
GFS passa ao mestre um nome de arquivo e um índice de porção, es-
perando um endereço de contato para a porção. O endereço de contato
contém todas as informações para acessar o servidor de porção correto
para obter o arquivo de porção requisitado. O mestre GFS mantém, um
espaço de nomes junto com um mapeamento de nomes de arquivos para
porções. Cada porção tem um identificador associado que permitirá a
um servidor consulta-lo. O mestre monitora onde a porção está locali-
zada. Porções são replicadas para manipular falhas. O mestre GFS não
tenta manter uma contabilidade exata da localização de porções. Em
vez disso, contata ocasionalmente os servidores de porção para verificar
quais porções eles armazenam.
21. Comente sobre a utilização de grupos para implementar a atu-
alização de cópias replicadas.
Os grupos para implementação de cópias replicadas, no caso de um sis-
tema de baixa latência, facilita a atualização e diminuem a complexidade
do envio de mensagens, visto que as mensagens podem ser direcionadas
aos grupos.
22. Apresente as principais características do Sistemas de Arqui-
vos Coda.
O sistema de arquivos Coda tem como objetivo tratar de vários requi-
sitos que o AFS não atende, particularmente, o requisito de fornecer
alta disponibilidade a despeito da operação desconectada. Fornecer aos
usuários as vantagens de um repositório de arquivos compartilhado, mas
permitir que eles contassem inteiramente com recursos locais quando o
repositório estivesse parcial ou totalmente inacessível.
9