Artigo algoritmos Distribuídos - TAF

Prévia do material em texto

ALGORITMOS DISTRIBUÍDOS 
 ​ Bruno F. S. Beltrame, Cristian Abramchuk, Jackson. F. Magnabosco, Marco Cavalett, 
Teyson Lorenzon 
Ciência da Computação – Universidade Regional Integrada do Alto Uruguai e das Missões 
Erechim (URI) 
Caixa Postal 743 – 99709-910 –Erechim – RS – Brasil 
{029603, 052630, 053428, 097819, 051162}@aluno.uricer.edu.br 
 
 
Abstract: ​The indispensable attribute of distributed systems is to allow several 
computers, positioned in opposite locations, to work together to accomplish a task, 
providing the sharing of resources and the distribution of services. However, due to 
the adversity of reaching a global consistency of the system, the development of 
distributed algorithms becomes an abundantly complex activity. In order to facilitate 
management, distributed algorithms often request a processor that performs a task 
differentiated from the others in a given application. This processor is usually called 
a coordinator or leader, and the problem of choosing a leader is to create a 
distributed algorithm for a given network of processors such that, when the 
execution of this algorithm is finished, one, and only one, of the processors is 
designated as leader. In this article a succinct study is made about the essential 
distributed algorithms, their main characteristics and applications 
Resumo: O indispensável atributo dos sistemas distribuídos é conceder que diversos 
computadores, posicionados em localizações opostas, trabalhem em conjunto para a 
cumprir-se de uma tarefa, proporcionando o compartilhamento de recursos e a 
distribuição dos serviços. Porém, devido à adversidade de se alcançar uma 
consistência global do sistema, o desenvolvimento de algoritmos distribuídos 
torna-se uma atividade abundantemente complexa. Objetivando facilitar a gestão, 
algoritmos distribuídos solicitam, muitas vezes, de um processador que exerça uma 
tarefa diferenciada dos demais numa dada aplicação. Este processador é 
normalmente intitulado de coordenador ou líder, e o problema de eleição de líder 
consiste em criar um algoritmo distribuído para uma dada rede de processadores tal 
que, ao terminar a execução deste algoritmo um, e apenas um, dos processadores 
seja designado líder. Neste artigo é feito um estudo sucinto sobre os essenciais 
algoritmos distribuídos, suas principais características e aplicações. 
Sumário 
 
Introdução 3 
Algoritmos 4 
2.1 Algoritmo de bully 4 
2.2 Algoritmo bizantino 4 
2.3 Relógio de Lamport 5 
2.4 Exclusão mútua 6 
Conclusão 7 
Referências Bibliográficas 8 
 
 
 
1. Introdução 
Os problemas são situações extremamente comuns na sociedade, alguns são simples outros 
mais complexos, e nos sistemas não é diferente. Em todos os casos, os problemas requerem 
tratamento, e em algumas situações requerem a cooperação de outras entidades para serem 
resolvidos. 
E pensando nisso foram desenvolvidos os Sistemas Distribuídos, onde nós 
independentes cooperam entre si para resolver problemas que não podem ser resolvidos 
individualmente. 
Para realizar processos em um sistema distribuído é necessário que haja sincronização 
entre os nós envolvidos, para que não ocorra falhas durante a execução, porém essa 
sincronização pode advir algumas falhas como dessincronização de relógios, deadlock, 
exclusão mútua, entre outros. 
Cada computador possui seu próprio relógio, porém é comum ocorrer divergência nos 
horários, e isso pode acarretar em transtornos em situações onde há a necessidade de 
identificar qual operação ocorreu primeiro. Da mesma forma ocorrem problemas em recursos 
locais, como a memória por exemplo, que não podem ser utilizados simultaneamente pelo 
processos, e problemas de deadlock, que podem ocorrer em situações de alocação de 
recursos. 
Para isso, foram desenvolvidos diversos algoritmos que tratam essas possíveis 
ocorrências. Algoritmos que serão apresentados no decorrer do artigo. 
 
2. Algoritmos 
Algoritmos Distribuídos são programas executados em sincronia com outros nós em uma 
rede compartilhada, que se comunicam e realização processos com um objetivo em comum. 
2.1 Algoritmo de bully 
Nascido em 1954 Hector Garcia Molina é um cientista da computação americano e docente 
nos departamentos de Ciência da Computação e Engenharia Elétrica da Universidade de 
Stanford. 
No ano de 1982 ele desenvolveu o algoritmo de ​bully​ que utiliza o método da eleição. 
Uma eleição é um procedimento para a escolha de um processo dentre um grupo de 
processos (tipicamente, para assumir a função de coordenador). 
A escolha deve ser única, apesar de vários processos se candidatarem e executarem 
algoritmos de eleição, concorrentemente. O processo coordenador pode falhar e um novo 
coordenador deve ser eleito. 
O líder pode ser escolhido de acordo com vários fatores, dentre eles pode-se citar 
como exemplo: um endereço IP, endereço físico do nó, quantidade de processamento ou 
qualquer identificação única, para que cada nó seja distinto. 
Contudo neste fato a topologia não é restrita a um anel e cada um dos processos pode 
se comunicar com qualquer outro no sistema. 
Este algoritmo possui esta denominação precisamente por seu comportamento 
valentão. 
O processo de maior identificador predomina sobre o de menor número e mesmo que 
um destes vença uma eleição, aceleradamente toma o posto do eleito sugerindo uma nova 
eleição. 
2.2 Algoritmo bizantino 
A tolerância prática a falhas bizantinas é um algoritmo de consenso criado no final dos anos 
90 por Barbara Liskov e Miguel Castro. 
A tolerância a falhas bizantinas (BFT) é o recurso de uma rede distribuída para achar 
um consenso mesmo quando alguns dos nós da rede não conseguem responder ou respondem 
com informações incorretas. 
Existe o problema do Generais Bizantinos onde três generais ou mais precisam chegar 
num consenso para decidir se irão atacar o seu inimigo em comum. Porém como eles 
precisam trocar informações nada lhes garante que a informação que será repassada a eles por 
mensageiros estará correta, e para que o ataque funcione ⅔ dos generais devem atacar, caso 
contrário a batalha será perdida. 
Falando sobre uma rede, para que o algoritmo seja eficaz os nós maliciosos da rede 
não podem igualar ou exceder a ⅓ do total de nós da rede. Quanto mais nós houver na rede 
mais provável que o algoritmo funcione pelo fato de ser mais difícil que o número de nós 
maliciosos cheguem a ⅓ . 
Cada rodada de consenso do pBFT se resumem em quatro fases: 
1° Um cliente envia uma solicitação ao nó líder (servidor principal) para chamar uma 
operação de serviço. 
2° O nó líder faz multicast da solicitação para os nós de backup. 
 3° Os nós executam a solicitação e, em seguida, enviam uma resposta ao cliente. 
4° O cliente aguarda f + 1 (f representa o número máximo de nós que podem estar 
com defeito) respostas de nós diferentes com o mesmo resultado. 
 
2.3 Relógio de Lamport 
Neste algoritmo, cada processo do sistema mantém um contador crescente C(b) e uma marca 
temporal C(a) na qual todos os processadores concordam; dessa forma, estão sujeitos as 
seguintes propriedades: 
1. Se ​a​ acontece antes de ​b​ no mesmo processo, então ​C(a) < C(b)​. 
2. Se ​a e ​b representam, respectivamente, o envio e o recebimentode uma 
mensagem, então ​C(a) < C(b)​. 
3. Sejam ​a​ e ​b​ eventos quaisquer, então ​C(a) ≠ C(b) 
Ordenação total dos eventos se dá quando é possível definir a ordem de quaisquer 
dois eventos; de acordo com Lamport, nenhum timer terá a mesma marcação temporal, então 
basta ordenar os eventos de acordo com o tempo que ocorreram e desfazer conflitos 
(empates) com base em outra propriedade escolhida de forma arbitrária, como por exemplo, 
seu identificador. Quando esse desempate não é feito se tem uma ordenação parcial e quando 
é feito se tem uma ordenação total. 
Nesse algoritmo, apenas um processo pode utilizar um recurso por vez, então os 
processos devem sincronizar para evitar conflitos, necessitando da ordenação total. 
Os relógios de Lamport obedecem as seguintes regras: 
1. Um processo incrementa seu contador antes de cada evento daquele processo; 
2. Quando um processo envia uma mensagem, este inclui o valor de seu contador 
junto da mensagem; 
3. No recebimento de uma mensagem, o processo atualiza seu contador para o 
valor maior entre o próprio valor e o valor do contador recebido na mensagem; 
Com base neste sistema, foi criado muitos algoritmos distribuídos, como exclusão 
mútua, onde a base de funcionamento e ordenação de eventos e processos obedecem as regras 
do relógio. 
 
2.4 Exclusão mútua 
Exclusão mútua mais conhecida como mutex é uma técnica de sincronização que permite 
assegurar o acesso exclusivo de leitura e gravação a recursos compartilhados por duas ou 
mais entidades. Seu objetivo é prevenir quando uma entidade está alterando os dados a outra 
não consegue fazer a alteração do mesmo assim prevenindo que um dado não sobrescreva o 
outro. 
Os requisitos para implantação do algoritmo são: 
● Nunca duas entidades podem estar simultaneamente em suas regiões críticas; 
● Deve ser independente da quantidade e desempenho dos processadores; 
● Nenhuma entidade fora da região crítica pode ter a exclusividade desta; 
● Nenhuma entidade deve esperar eternamente para entrar em sua região crítica. 
A técnica pode ser implementada com duas formas primitivas básicas lock onde 
garante a exclusividade da região crítica no ponto de entrada da região e unlock onde libera a 
exclusividade da região crítica no ponto de saída da região. 
Usando o exemplo simples de threads podemos explicar como os algoritmos de mutex 
funcionam 
● Thread 1 entra na região crítica 
● Thread 2 tenta entrar na região crítica 
● Thread 1 sai da região crítica e thread 2 entra na região crítica 
● Thread 2 sai da região crítica. 
 
3. Conclusão 
Este trabalho proporcionou um grande aprofundamento quanto a técnicas para tratamento de 
falhas relacionadas a sistemas distribuídos, possibilitando a comunicação e compartilhamento 
de recursos entre diversos computadores sem ocorrência de falhas. Demonstra-se também 
muito proveitoso para futuras implementações onde requerem transmissão ou comunicação 
de dados entre máquinas. 
4. Referências Bibliográficas 
Algoritmos de bully. Disponível em 
<​http://repositorio.unicamp.br/bitstream/REPOSIP/276061/1/Alencar_JuceleFrancade_M.pdf
>. Acesso em 04/04/2020. 
Algoritmos de bully. Disponível em <​https://wiki.python.org.br/AlgoritmoBully​>. Acesso em 
04/04/2020. 
Algoritmos Distribuídos, Markus Endler. Disponível em 
<​http://www-di.inf.puc-rio.br/~endler/courses/DA/transp/D-Algos.PDF​>. Acesso em 
01/04/2020. 
Algoritmos Distribuídos. Disponível em 
<​https://www.inf.pucrs.br/~gustavo/disciplinas/sd/material/slides_algosdistr.pdf​>. Acesso em 
01/04/2020. 
Distributed Algorithm. Disponível em <​https://en.wikipedia.org/wiki/Distributed_algorithm​>. 
Acesso em 01/04/2020. 
Exclusão Mútua (mutex). Disponível em 
<​https://edisciplinas.usp.br/pluginfile.php/3061851/mod_resource/content/2/36-Mutex-v27.p
df​>. Acesso em 02/04/2020. 
Practical Byzantine Fault Tolerance(pBFT), Parikshit Hooda. Disponível em 
<​https://www.geeksforgeeks.org/practical-byzantine-fault-tolerancepbft​/​>.Acesso em 
02/04/2020. 
Understanding Blockchain Fundamentals, Georgios Konstantopoulos. Dispoível em 
<​https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantin
e-fault-tolerance-245f46fe8419​>. Acesso em 02/04/2020. 
 
Rodrigues, R.J.D.S., Lima, R.A. and José, D.A.M., 2017. Algoritmo para sincronizaçao de 
relógios fısicos em sistemas distribuıdos. ​ERRC 2017​, p.42. Disponível em 
<​https://www.ufsm.br/unidades-universitarias/ctism/wp-content/uploads/sites/360/2019/06/A
NAIS_ERRC_2017.pdf#page=54​>. Acesso em 05/04/2020. 
 
Rodrigues, L.E., 2003. Sumários das aulas e exames de Tolerˆancia a Faltas Distribuıda 
2003-2004. Disponível em 
<​https://www.gsd.inesc-id.pt/~ler/docencia/tfd0304/bib/Guiao.pdf​>. Acesso em 05/04/2020 
 
http://repositorio.unicamp.br/bitstream/REPOSIP/276061/1/Alencar_JuceleFrancade_M.pdf
https://wiki.python.org.br/AlgoritmoBully
http://www-di.inf.puc-rio.br/~endler/courses/DA/transp/D-Algos.PDF
https://www.inf.pucrs.br/~gustavo/disciplinas/sd/material/slides_algosdistr.pdf
https://en.wikipedia.org/wiki/Distributed_algorithm
https://edisciplinas.usp.br/pluginfile.php/3061851/mod_resource/content/2/36-Mutex-v27.pdf
https://edisciplinas.usp.br/pluginfile.php/3061851/mod_resource/content/2/36-Mutex-v27.pdf
https://www.geeksforgeeks.org/practical-byzantine-fault-tolerancepbft/
https://www.geeksforgeeks.org/practical-byzantine-fault-tolerancepbft/
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
https://www.ufsm.br/unidades-universitarias/ctism/wp-content/uploads/sites/360/2019/06/ANAIS_ERRC_2017.pdf#page=54
https://www.ufsm.br/unidades-universitarias/ctism/wp-content/uploads/sites/360/2019/06/ANAIS_ERRC_2017.pdf#page=54
https://www.gsd.inesc-id.pt/~ler/docencia/tfd0304/bib/Guiao.pdf