ModelosEditar
Muitas tarefas que gostaríamos de automatizar utilizando um computador são do tipo de perguntas-respostas: gostaríamos de fazer uma pergunta e o computador deveria produzir uma resposta. Na teoria da informática, tais tarefas são chamadas problemas computacionais. Formalmente, um problema computacional consiste em instâncias juntamente com uma solução para cada instância. As instâncias são perguntas que podemos fazer, e as soluções são respostas desejadas a estas perguntas.
A informática teórica procura compreender quais os problemas computacionais que podem ser resolvidos utilizando um computador (teoria da computabilidade) e quão eficientemente (teoria da complexidade computacional). Tradicionalmente, diz-se que um problema pode ser resolvido utilizando um computador se conseguirmos conceber um algoritmo que produza uma solução correcta para qualquer instância dada. Tal algoritmo pode ser implementado como um programa de computador que corre num computador de uso geral: o programa lê uma instância de problema a partir da entrada, executa algum cálculo, e produz a solução como saída. Formalismos tais como máquinas de acesso aleatório ou máquinas Turing universais podem ser utilizados como modelos abstractos de um computador de uso geral sequencial executando tal algoritmo.
O campo da computação simultânea e distribuída estuda questões semelhantes no caso de múltiplos computadores, ou um computador que executa uma rede de processos de interacção: que problemas computacionais podem ser resolvidos numa tal rede e com que eficiência? Contudo, não é nada óbvio o que se entende por “resolver um problema” no caso de um sistema concorrente ou distribuído: por exemplo, qual é a tarefa do desenhador do algoritmo, e qual é o equivalente concorrente ou distribuído de um computador de uso geral sequencial?
A discussão abaixo centra-se no caso de vários computadores, embora muitos dos problemas sejam os mesmos para processos simultâneos executados num único computador.
Três pontos de vista são comummente utilizados:
Algoritmos paralelos no modelo de memória partilhada
- Todos os processadores têm acesso a uma memória partilhada. O desenhador do algoritmo escolhe o programa executado por cada processador.
- Um modelo teórico são as máquinas de acesso aleatório paralelo (PRAM) que são utilizadas. Contudo, o modelo clássico PRAM assume o acesso síncrono à memória partilhada.
- Programas de memória partilhada podem ser estendidos a sistemas distribuídos se o sistema operativo subjacente encapsular a comunicação entre nós e praticamente unificar a memória em todos os sistemas individuais.
- Um modelo que esteja mais próximo do comportamento de máquinas multiprocessadoras do mundo real e tenha em conta o uso de instruções de máquina, tais como Compare-and-swap (CAS), é o de memória partilhada assíncrona. Existe um vasto conjunto de trabalhos sobre este modelo, cujo resumo pode ser encontrado na literatura.
Algoritmos paralelos no modelo de passagem de mensagens
- O desenhador do algoritmo escolhe a estrutura da rede, bem como o programa executado por cada computador.
- Modelos como circuitos booleanos e redes de classificação são utilizados. Um circuito booleano pode ser visto como uma rede de computadores: cada porta é um computador que executa um programa de computador extremamente simples. Da mesma forma, uma rede de classificação pode ser vista como uma rede de computadores: cada comparador é um computador.
Algoritmos distribuídos em modelo de passagem de mensagens
- O desenhador do algoritmo apenas escolhe o programa de computador. Todos os computadores executam o mesmo programa. O sistema deve funcionar correctamente independentemente da estrutura da rede.
- Um modelo comummente utilizado é um gráfico com uma máquina de estado finito por nó.
No caso de algoritmos distribuídos, os problemas computacionais estão tipicamente relacionados com os gráficos. Muitas vezes o gráfico que descreve a estrutura da rede informática é a instância do problema. Isto é ilustrado no exemplo seguinte.
Um exemploEditar
Considerar o problema computacional de encontrar uma coloração de um dado gráfico G. Campos diferentes podem ter as seguintes abordagens:
Algoritmos centralizados
- O gráfico G é codificado como uma string, e a string é dada como entrada para um computador. O programa de computador encontra uma coloração do gráfico, codifica a coloração como uma string, e produz o resultado.
Algoritmos paralelos
- Again, o gráfico G é codificado como uma string. Contudo, vários computadores podem aceder à mesma cadeia de caracteres em paralelo. Cada computador pode concentrar-se numa parte do gráfico e produzir uma coloração para essa parte.
>li> O foco principal é a computação de alto desempenho que explora o poder de processamento de múltiplos computadores em paralelo.
Algoritmos distribuídos
- O gráfico G é a estrutura da rede de computadores. Existe um computador para cada nó de G e uma ligação de comunicação para cada extremidade de G. Inicialmente, cada computador só conhece os seus vizinhos imediatos no gráfico G; os computadores devem trocar mensagens entre si para descobrir mais sobre a estrutura de G. Cada computador deve produzir a sua própria cor como saída.
- O foco principal é a coordenação do funcionamento de um sistema distribuído arbitrário.
Embora o campo dos algoritmos paralelos tenha um foco diferente do campo dos algoritmos distribuídos, há muita interacção entre os dois campos. Por exemplo, o algoritmo Cole-Vishkin para coloração gráfica foi originalmente apresentado como um algoritmo paralelo, mas a mesma técnica também pode ser usada directamente como um algoritmo distribuído.
Além disso, um algoritmo paralelo pode ser implementado ou num sistema paralelo (usando memória partilhada) ou num sistema distribuído (usando passagem de mensagens). A fronteira tradicional entre algoritmos paralelos e distribuídos (escolher uma rede adequada vs. executar em qualquer rede) não se situa no mesmo lugar que a fronteira entre sistemas paralelos e distribuídos (memória partilhada vs. passagem de mensagens).
Medidas de complexidadeEditar
Em algoritmos paralelos, mais um recurso para além do tempo e espaço é o número de computadores. De facto, muitas vezes existe um compromisso entre o tempo de funcionamento e o número de computadores: o problema pode ser resolvido mais rapidamente se houver mais computadores a funcionar em paralelo (ver aceleração). Se um problema de decisão pode ser resolvido em tempo polilogarítmico utilizando um número polinomial de processadores, então diz-se que o problema está na classe NC. A classe NC pode ser definida igualmente bem utilizando o formalismo PRAM ou circuitos booleanos – as máquinas PRAM podem simular eficazmente circuitos booleanos e vice-versa.
Na análise dos algoritmos distribuídos, é normalmente dada mais atenção às operações de comunicação do que aos passos computacionais. Talvez o modelo mais simples de computação distribuída seja um sistema síncrono em que todos os nós operam em modo de passos de bloqueio. Este modelo é geralmente conhecido como o modelo LOCAL. Durante cada ronda de comunicação, todos os nós em paralelo (1) recebem as últimas mensagens dos seus vizinhos, (2) realizam cálculos locais arbitrários, e (3) enviam novas mensagens aos seus vizinhos. Em tais sistemas, uma medida central de complexidade é o número de rondas de comunicação síncrona necessárias para completar a tarefa.
Esta medida de complexidade está intimamente relacionada com o diâmetro da rede. Que D seja o diâmetro da rede. Por um lado, qualquer problema calculável pode ser resolvido trivialmente num sistema distribuído síncrono em rondas de comunicação aproximadamente 2D: basta reunir toda a informação num local (rondas D), resolver o problema, e informar cada nó sobre a solução (rondas D).
Por outro lado, se o tempo de execução do algoritmo for muito menor do que as rondas de comunicação D, então os nós da rede devem produzir a sua saída sem ter a possibilidade de obter informação sobre partes distantes da rede. Por outras palavras, os nós devem tomar decisões globalmente consistentes com base na informação disponível na sua vizinhança D local. Muitos algoritmos distribuídos são conhecidos com o tempo de funcionamento muito menor do que as rondas D, e compreender quais os problemas que podem ser resolvidos por tais algoritmos é uma das questões centrais de investigação do campo. Tipicamente um algoritmo que resolve um problema em tempo polilogarítmico no tamanho da rede é considerado eficiente neste modelo.
Outra medida comummente utilizada é o número total de bits transmitidos na rede (cf. complexidade de comunicação). As características deste conceito são tipicamente capturadas com o modelo CONGEST(B), o qual é igualmente definido como o modelo LOCAL, mas onde mensagens únicas só podem conter bits B.
Outros problemasEdit
Problemas computacionais tradicionais tomam a perspectiva de que o utilizador faz uma pergunta, um computador (ou um sistema distribuído) processa a pergunta, depois produz uma resposta e pára. Contudo, há também problemas em que o sistema é obrigado a não parar, incluindo o problema dos filósofos do jantar e outros problemas semelhantes de exclusão mútua. Nestes problemas, o sistema distribuído deve coordenar continuamente a utilização de recursos partilhados para que não ocorram conflitos ou bloqueios.
Existem também desafios fundamentais que são exclusivos da computação distribuída, por exemplo os relacionados com a tolerância a falhas. Exemplos de problemas relacionados incluem problemas de consenso, tolerância a falhas bizantinas, e auto-estabilização.
A investigação está também centrada na compreensão da natureza assíncrona dos sistemas distribuídos:
- Os sincronizadores podem ser utilizados para executar algoritmos síncronos em sistemas assíncronos.
- Os relógios lógicos fornecem um acontecimento causal – antes da ordenação dos eventos.
- Algoritmos de sincronização do relógio fornecem carimbos de tempo físicos globalmente consistentes.
ElectionEdit
Eleição de coordenador (ou eleição de líder) é o processo de designação de um único processo como organizador de alguma tarefa distribuída entre vários computadores (nós). Antes do início da tarefa, todos os nós da rede ou desconhecem qual o nó que irá servir de “coordenador” (ou líder) da tarefa, ou não conseguem comunicar com o coordenador actual. Após a execução de um algoritmo de eleição do coordenador, contudo, cada nó em toda a rede reconhece um nó particular e único como coordenador da tarefa.
Os nós da rede comunicam entre si para decidir qual deles entrará no estado de “coordenador”. Para isso, precisam de algum método a fim de quebrar a simetria entre eles. Por exemplo, se cada nó tiver identidades únicas e comparáveis, então os nós podem comparar as suas identidades, e decidir que o nó com a identidade mais elevada é o coordenador.
A definição deste problema é frequentemente atribuída a LeLann, que a formalizou como um método para criar um novo token numa rede de anel token em que o token foi perdido.
Os algoritmos de eleição do coordenador são concebidos para serem económicos em termos de bytes totais transmitidos, e de tempo. O algoritmo sugerido por Gallager, Humblet, e Spira para gráficos gerais não direccionados teve um forte impacto na concepção de algoritmos distribuídos em geral, e ganhou o Prémio Dijkstra por um papel influente na computação distribuída.
Muitos outros algoritmos foram sugeridos para diferentes tipos de gráficos de rede, tais como anéis não direccionados, anéis unidireccionais, gráficos completos, grelhas, gráficos Euler direccionados, e outros. Um método geral que dissocia a questão da família de gráficos da concepção do algoritmo de eleição do coordenador foi sugerido por Korach, Kutten, e Moran.
A fim de realizar a coordenação, os sistemas distribuídos empregam o conceito de coordenadores. O problema da eleição do coordenador é escolher um processo de entre um grupo de processos sobre diferentes processadores num sistema distribuído para actuar como coordenador central. Existem vários algoritmos eleitorais de coordenador central.
Propriedades dos sistemas distribuídosEditar
Até agora o foco tem sido a concepção de um sistema distribuído que resolva um dado problema. Um problema de investigação complementar é o estudo das propriedades de um dado sistema distribuído.
O problema de paragem é um exemplo análogo do campo da computação centralizada: é-nos dado um programa de computador e a tarefa é decidir se este pára ou corre para sempre. O problema de paragem é indecidível no caso geral, e naturalmente compreender o comportamento de uma rede informática é pelo menos tão difícil como compreender o comportamento de um computador.
No entanto, há muitos casos especiais interessantes que são decidíveis. Em particular, é possível raciocinar sobre o comportamento de uma rede de máquinas de estado finito. Um exemplo é dizer se uma determinada rede de máquinas de estado finito em interacção (assíncronas e não determinísticas) pode chegar a um impasse. Este problema é PSPACE-completo, ou seja, é decidível, mas não é provável que exista um algoritmo eficiente (centralizado, paralelo ou distribuído) que resolva o problema no caso de grandes redes.