Friksjon (effekt og varighet)

8 Referencial Te´orico

Os algoritmos distribu´ıdos se diferem dos algoritmos paralelos, que executam em um mesmo equipamento com mem´oria compartilhada. Os distribu´ıdos se caracterizam pela troca de mensagens entre os elementos processados.

Algoritmos distribu´ıdos emergem em v´arias aplica¸c˜oes, incluindo telecomunica¸c˜oes, processamento de informa¸c˜ao distribu´ıdo, computa¸c˜ao cient´ıfica e controle de processos em tempo real.

Uma parte importante do trabalho de construir um sistema para aplica¸c˜oes dis- tribu´ıdas ´e o desenho, a implementa¸c˜ao e a an´alise desses algoritmos.

Os diversos algoritmos distribu´ıdos v˜ao diferir em v´arios atributos, entre os principais est˜ao:

• M´etodo comunica¸c˜ao inter-processos (IPC): Algoritmos distribu´ıdos executam em diferentes processadores que precisam se comunicar de alguma forma. M´etodos comuns de comunica¸c˜ao incluem envio de mensagens ponto a ponto ou difus˜ao e execu¸c˜ao de chamadas de procedimento remoto (RPC);

• Modelo de tempo: Os modelos de tempo podem ser divididos em dois extremos. S´ıncronos e ass´ıncronos. Nos modelos s´ıncronos os algoritmos executam passo a passo todos ao mesmo tempo. Nos modelos ass´ıncronos, os passos podem ser exe- cutados em momentos diferentes e em diferentes velocidades. Existem tamb´em os modelos parcialmente s´ıncronos onde os alguma informa¸c˜ao de tempo ´e comparti- lhada. Por exemplo um rel´ogio compartilhado.

• Modelos de falha: Os algoritmos podem ser requisitados a tolerar um conjunto limitado de comportamento err´atico. Alguns exemplos de falhas incluem, falha dos processadores, atraso nas mensagens, ou mesmo, falhas arbitr´arias chamadas bizantinas.

• Tipos de problemas: Os algoritmos tamb´em se diferem nos tipos de problemas aos quais pretendem solucionar. Alguns exemplos s˜ao aloca¸c˜ao de recursos, co- munica¸c˜ao, consenso entre os membros, controle de concorrˆencia detec¸c˜ao de dea-

dlocks, snapshots globais, sincroniza¸c˜ao.

Segundo Lynch (Lynch 1996), a principal divis˜ao que podemos fazer entre os al- goritmos distribu´ıdos se d´a pelos seus modelos de tempo s´ıncrono e ass´ıncrono. Para

Referencial Te´orico 9

explica¸c˜ao dos dois modelos, definiremos o algoritmo distribu´ıdo como um grafo direci- onado G = (N, D), onde n = |N | e m = |D|. Para 1 ≤ i, j ≤ n, ni denota um membro de N , chamado n´o, se j 6= i ent˜ao (ni → nj) denota um membro de D, chamado aresta direcionada. As arestas saindo de ni s˜ao chamadas Outi ⊆ D e as arestas em dire¸c˜ao a ni s˜ao chamadas Ini ⊆ D. N´os ser˜ao chamados vizinhos se (ni → nj) ∈ D ou (nj → ni) ∈ D. O conjunto de vizinhos de ni ser´a chamado N eighidividido em I N eighi e O N eighi respectivamente para os vizinhos de ni onde (ni → nj) ∈ D e (nj → ni) ∈ D. Num contexto de tratamento de mensagens, chamaremos de msgi uma mensagem de ni.

No modelo s´ıncrono ´e assumido que os componentes executam computa¸c˜ao simulta- neamente em resposta a um rel´ogio global. A cada passo, o processo ni ´e invocado, se for um n´o com permiss˜ao de gerar mensagens espontˆaneas ni ∈ N0, envia mensagens para os vizinhos. Se existirem mensagens em msgi, o processo ni processa a entrada, executa computa¸c˜ao referente a essas mensagens e envia uma ou mais mensagens pelos seus canais de sa´ıda Outi, como visto no Algoritmo 2.1. No modelo s´ıncrono, M SGi(s) a mensagem ´e recebida a cada passo s. ´E importante notar que a chamada do pro- cesso ni acontece independente de existirem ou n˜ao mensagens para receber, apesar do processamento poder depender da existˆencia de mensagens.

Algoritmo 2.1:S Template Input: s = 0, M SGi(0) = ∅ 2

2 Action: if n_i ∈ N₀ then 3 Executa processamento;

4 Envia uma mensagem em cada aresta do conjunto Out_i (possivelmente vazio) Input: s > 0, M SGi(1), ..., M SGi(s) sendo que origin(msg) = ck ∈ Ini com 1 ≤

k ≤ |Ini| para msg ∈ Ss_r=1M SGi(r) 6

6 Action: begin

7 Executa processamento;

8 Envia uma mensagem em cada aresta do conjunto Out_i (possivelmente vazio) As restri¸c˜oes de tempo dos algoritmos s´ıncronos n˜ao ´e encontrada na pr´atica na maioria dos sistemas distribu´ıdos, mas esse modelo ´e ´util para entender os problemas e

10 Referencial Te´orico

Com o uso desse sinal dizemos que as a¸c˜oes executadas por esse algoritmo s˜ao atˆomicas, ou seja, n˜ao podem ser interrompidas pela chegada de uma mensagem. Um modelo gen´erico de algoritmo ass´ıncrono ´e apresentado no Algoritmo 2.2.

Algoritmo 2.2:A Template Input: msgi = nil

2

2 Action: if n_i ∈ N₀ then 3 Executa processamento;

4 Envia uma mensagem em cada aresta do conjunto Out_i (possivelmente vazio) Input: msgi sendo que origin(msg) = ck∈ Ini com 1 ≤ k ≤ |Ini|

6

6 Action: if B_k then

7 begin

8 Executa processamento;

9 Envia uma mensagem em cada aresta do conjunto Out_i (possivelmente

vazio)

Algoritmos ass´ıncronos mais port´aveis e podem ser executados em ambientes com modelos de tempo s´ıncrono. Algumas vezes, esses algoritmos n˜ao podem atingir solu¸c˜oes em tempo esperado ou mesmo n˜ao atingir nenhuma solu¸c˜ao

No modelo parcialmente s´ıncrono assume-se que existe rel´ogio s´ıncrono entre os ele- mentos. A maioria dos algoritmos reais s˜ao implementados dessa forma. S˜ao algoritmos em geral eficientes, por´em, relativamente fr´ageis quanto a qualquer viola¸c˜ao dos pressu- postos de tempo.

Lynch (Lynch 1996) divide a pesquisa em sistemas distribu´ıdos em dois campos teoria dinˆamica e teoria est´atica. A teoria est´atica, tem foco em sistemas est´aveis, com redes confi´aveis onde os participantes s˜ao conhecidos. A teoria dinˆamica enfoca as particularidades dos sistemas distribu´ıdos dinˆamicos como:

• n´umero desconhecido de n´os participantes; • n´os podem entrar, sair e retornar;

• mobilidade dos n´os; difus˜ao Local, onde a informa¸c˜ao alcan¸ca v´arios n´os geografi- camente pr´oximos;

• sucesso no envio das mensagens depende de fatores de distˆancia e propaga¸c˜ao de sinal;

Referencial Te´orico 11

• conten¸c˜ao devido a colis˜oes e perda de mensagens.

A maioria dos sistemas distribu´ıdos modernos se encaixa no paradigma dinˆamico como por exemplo, aplica¸c˜oes Cliente Servidor, redes P2P, comunica¸c˜oes sem fio.

As primeiras aplica¸c˜oes ponto a ponto (P2P) se popularizaram atrav´es de servi¸cos de compartilhamento de arquivos para a Internet. A ideia principal deste servi¸co ´e que os arquivos estejam armazenadas e sejam disponibilizados nas m´aquinas dos pr´oprios usu´arios da aplica¸c˜ao. Ele funciona da seguinte maneira: cada usu´ario pode descarregar os arquivos que est˜ao armazenados em computadores de outros usu´arios, em contrapar- tida, ele dever´a disponibilizar arquivos para que outros usu´arios tamb´em possam obtˆe-los de sua m´aquina.