Computação distribuída

Um sistema distribuído é um sistema cujos componentes estão localizados em diferentes computadores em rede, que se comunicam e coordenam suas ações passando mensagens uns para os outros. Computação distribuída é um campo da ciência da computação que estuda sistemas distribuídos.

Os componentes de um sistema distribuído interagem entre si para atingir um objetivo comum. Três desafios significativos dos sistemas distribuídos são: manter a simultaneidade dos componentes, superar a falta de um relógio global e gerenciar a falha independente dos componentes. Quando um componente de um sistema falha, o sistema inteiro não falha. Exemplos de sistemas distribuídos variam de sistemas baseados em SOA a jogos on-line massivamente multijogador e aplicativos ponto a ponto.

Um programa de computador executado em um sistema distribuído é chamado de programa distribuído, e programação distribuída é o processo de escrever tais programas. Existem muitos tipos diferentes de implementações para o mecanismo de passagem de mensagens, incluindo HTTP puro, conectores semelhantes a RPC e filas de mensagens.

Computação distribuída também se refere ao uso de sistemas distribuídos para resolver problemas computacionais. Na computação distribuída, um problema é dividido em várias tarefas, cada uma das quais é resolvida por um ou mais computadores, que se comunicam entre si por meio de troca de mensagens.

Introdução

A palavra distribuído em termos como "sistema distribuído", "programação distribuída" e "algoritmo distribuído" originalmente se referia a redes de computadores onde computadores individuais eram fisicamente distribuídos dentro de alguma área geográfica. Os termos são hoje usados em um sentido muito mais amplo, referindo-se até mesmo a processos autônomos que rodam no mesmo computador físico e interagem entre si por passagem de mensagens.

Embora não haja uma definição única de um sistema distribuído, as seguintes propriedades de definição são comumente usadas como:

• Existem várias entidades computacionais autônomas (computadores ou nós), cada um com sua própria memória local.
• As entidades comunicam-se umas com as outras por mensagem.

Um sistema distribuído pode ter um objetivo comum, como resolver um grande problema computacional; o usuário então percebe a coleção de processadores autônomos como uma unidade. Alternativamente, cada computador pode ter seu próprio usuário com necessidades individuais, e o objetivo do sistema distribuído é coordenar o uso de recursos compartilhados ou fornecer serviços de comunicação aos usuários.

Outras propriedades típicas de sistemas distribuídos incluem o seguinte:

• O sistema tem de tolerar falhas em computadores individuais.
• A estrutura do sistema (topologia de rede, latência de rede, número de computadores) não é conhecida com antecedência, o sistema pode consistir em diferentes tipos de computadores e links de rede, e o sistema pode mudar durante a execução de um programa distribuído.
• Cada computador tem apenas uma visão limitada e incompleta do sistema. Cada computador pode saber apenas uma parte da entrada.

Computação paralela e distribuída

(a), (b): um sistema distribuído.
(c): um sistema paralelo.

Sistemas distribuídos são grupos de computadores em rede que compartilham um objetivo comum para seu trabalho. Os termos "computação simultânea", "computação paralela" e "computação distribuída" têm muita sobreposição, e nenhuma distinção clara existe entre eles. O mesmo sistema pode ser caracterizado tanto como "paralelo" e "distribuído"; os processadores em um sistema distribuído típico são executados simultaneamente em paralelo. A computação paralela pode ser vista como uma forma particular fortemente acoplada de computação distribuída, e a computação distribuída pode ser vista como uma forma fracamente acoplada de computação paralela. No entanto, é possível classificar aproximadamente sistemas concorrentes como "paralelos" ou "distribuído" usando os seguintes critérios:

• Em computação paralela, todos os processadores podem ter acesso a uma memória compartilhada para trocar informações entre processadores.
• Em computação distribuída, cada processador tem sua própria memória privada (memória distribuída). A informação é trocada por mensagens de passagem entre os processadores.

A figura à direita ilustra a diferença entre sistemas distribuídos e paralelos. A Figura (a) é uma visão esquemática de um sistema distribuído típico; o sistema é representado como uma topologia de rede na qual cada nó é um computador e cada linha que conecta os nós é um link de comunicação. A Figura (b) mostra o mesmo sistema distribuído com mais detalhes: cada computador tem sua própria memória local e as informações podem ser trocadas apenas passando mensagens de um nó para outro usando os links de comunicação disponíveis. A Figura (c) mostra um sistema paralelo no qual cada processador tem acesso direto a uma memória compartilhada.

A situação é ainda mais complicada pelos usos tradicionais dos termos algoritmo paralelo e distribuído que não correspondem exatamente às definições acima de sistemas paralelos e distribuídos (veja abaixo para discussão mais detalhada). No entanto, como regra geral, a computação paralela de alto desempenho em um multiprocessador de memória compartilhada usa algoritmos paralelos, enquanto a coordenação de um sistema distribuído de larga escala usa algoritmos distribuídos.

História

O uso de processos simultâneos que se comunicam por meio de troca de mensagens tem suas raízes nas arquiteturas de sistemas operacionais estudadas na década de 1960. Os primeiros sistemas distribuídos amplamente difundidos foram as redes de área local, como a Ethernet, que foi inventada na década de 1970.

A ARPANET, uma das predecessoras da Internet, foi introduzida no final da década de 1960, e o e-mail da ARPANET foi inventado no início da década de 1970. O e-mail tornou-se o aplicativo de maior sucesso da ARPANET e é provavelmente o exemplo mais antigo de um aplicativo distribuído em larga escala. Além da ARPANET (e sua sucessora, a Internet global), outras primeiras redes mundiais de computadores incluíam a Usenet e a FidoNet da década de 1980, ambas usadas para dar suporte a sistemas de discussão distribuídos.

O estudo da computação distribuída tornou-se seu próprio ramo da ciência da computação no final dos anos 1970 e início dos anos 1980. A primeira conferência no campo, Symposium on Principles of Distributed Computing (PODC), data de 1982, e sua contraparte International Symposium on Distributed Computing (DISC) foi realizada pela primeira vez em Ottawa em 1985 como o International Workshop on Distributed Algorithms on Graphs.

Arquiteturas

Várias arquiteturas de hardware e software são usadas para computação distribuída. Em um nível inferior, é necessário interconectar várias CPUs com algum tipo de rede, independentemente de essa rede ser impressa em uma placa de circuito ou composta por dispositivos e cabos fracamente acoplados. Em um nível superior, é necessário interligar os processos executados nessas CPUs com algum tipo de sistema de comunicação.

A programação distribuída geralmente cai em uma das várias arquiteturas básicas: cliente-servidor, três camadas, n camadas ou ponto a ponto; ou categorias: acoplamento solto ou acoplamento apertado.

• Cliente-servidor: arquiteturas onde os clientes inteligentes contatam o servidor para dados, em seguida, formatar e exibi-lo para os usuários. Entrada no cliente é comprometida de volta ao servidor quando representa uma mudança permanente.
• Três níveis: arquiteturas que movem a inteligência do cliente para um nível médio para que os clientes sem estado possam ser usados. Isso simplifica a implementação de aplicativos. A maioria das aplicações web são de três níveis.
• n-tier: arquiteturas que se referem tipicamente a aplicações web que encaminham ainda mais seus pedidos para outros serviços empresariais. Este tipo de aplicação é o mais responsável pelo sucesso dos servidores de aplicações.
• Peer-to-peer: arquiteturas onde não há máquinas especiais que fornecem um serviço ou gerenciar os recursos da rede. Em vez disso, todas as responsabilidades são uniformemente divididas entre todas as máquinas, conhecidas como pares. Peers pode servir tanto como clientes e como servidores. Exemplos desta arquitetura incluem BitTorrent e a rede bitcoin.

Outro aspecto básico da arquitetura de computação distribuída é o método de comunicação e coordenação do trabalho entre processos simultâneos. Através de vários protocolos de passagem de mensagens, os processos podem se comunicar diretamente uns com os outros, normalmente em uma relação mestre/escravo. Alternativamente, um "centrado em banco de dados" A arquitetura pode permitir que a computação distribuída seja feita sem qualquer forma de comunicação direta entre processos, utilizando um banco de dados compartilhado. A arquitetura centrada no banco de dados, em particular, fornece análises de processamento relacional em uma arquitetura esquemática que permite a retransmissão do ambiente ao vivo. Isso permite funções de computação distribuída dentro e além dos parâmetros de um banco de dados em rede.

Aplicativos

Os motivos para usar sistemas distribuídos e computação distribuída podem incluir:

• A própria natureza de uma aplicação pode exigir o uso de uma rede de comunicação que conecta vários computadores: por exemplo, dados produzidos em um local físico e necessários em outro local.
• Há muitos casos em que o uso de um único computador seria possível em princípio, mas o uso de um sistema distribuído é benéfico por razões práticas. Por exemplo:
  • Pode permitir armazenamento e memória muito maiores, computação mais rápida e maior largura de banda do que uma única máquina.
  • Ele pode fornecer mais confiabilidade do que um sistema não distribuído, pois não há um único ponto de falha. Além disso, um sistema distribuído pode ser mais fácil de expandir e gerenciar do que um sistema uniprocessador monolítico.
  • Pode ser mais econômico para obter o nível de desempenho desejado usando um cluster de vários computadores low-end, em comparação com um único computador high-end.

Exemplos

Exemplos de sistemas distribuídos e aplicações de computação distribuída incluem o seguinte:

• redes de telecomunicações:
  • redes telefônicas e redes celulares,
  • redes de computadores como a Internet,
  • redes de sensores sem fio,
  • algoritmos de roteamento;
• aplicações de rede:
  • Redes World Wide Web e peer-to-peer,
  • jogos online multijogador massivamente e comunidades de realidade virtual,
  • bancos de dados distribuídos e sistemas de gestão de banco de dados distribuídos,
  • sistemas de arquivos de rede,
  • cache distribuído como amortecedores de explosão,
  • sistemas de processamento de informações distribuídas, como sistemas bancários e sistemas de reservas de companhias aéreas;
• controle de processo em tempo real:
  • sistemas de controle de aeronaves,
  • sistemas de controle industrial;
• computação paralela:
  • computação científica, incluindo computação em cluster, computação em grade, computação em nuvem e vários projetos de computação voluntária,
  • renderização distribuída em gráficos de computador.
• peer-to-peer

Fundamentos teóricos

Modelos

Muitas tarefas que gostaríamos de automatizar usando um computador são do tipo pergunta-resposta: gostaríamos de fazer uma pergunta e o computador deveria produzir uma resposta. Na ciência da computação teórica, tais tarefas são chamadas de problemas computacionais. Formalmente, um problema computacional consiste em instâncias juntamente com uma solução para cada instância. Instâncias são perguntas que podemos fazer, e soluções são respostas desejadas para essas perguntas.

A ciência da computação teórica procura entender quais problemas computacionais podem ser resolvidos usando um computador (teoria da computabilidade) e com que eficiência (teoria da complexidade computacional). Tradicionalmente, diz-se que um problema pode ser resolvido usando um computador se pudermos projetar um algoritmo que produza uma solução correta para qualquer instância. Tal algoritmo pode ser implementado como um programa de computador executado em um computador de uso geral: o programa lê uma instância do problema a partir da entrada, realiza alguns cálculos e produz a solução como saída. Formalismos como máquinas de acesso aleatório ou máquinas de Turing universais podem ser usados como modelos abstratos de um computador sequencial de propósito geral executando tal algoritmo.

O campo da computação simultânea e distribuída estuda questões semelhantes no caso de vários computadores ou de um computador que executa uma rede de processos interativos: quais problemas computacionais podem ser resolvidos em tal rede e com que eficiência? No entanto, 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 projetista do algoritmo e qual é o equivalente concorrente ou distribuído de um computador sequencial de propósito geral?

A discussão abaixo se concentra no caso de vários computadores, embora muitos dos problemas sejam os mesmos para processos simultâneos em execução em um único computador.

Três pontos de vista são comumente usados:

Algoritmos paralelos no modelo de memória compartilhada

• Todos os processadores têm acesso a uma memória compartilhada. O designer de algoritmos escolhe o programa executado por cada processador.
• Um modelo teórico é as máquinas paralelas de acesso aleatório (PRAM) que são usadas. No entanto, o modelo PRAM clássico assume acesso síncrono à memória compartilhada.
• Programas de memória compartilhada podem ser estendidos para sistemas distribuídos se o sistema operacional subjacente encapsula a comunicação entre nós e praticamente unifica a memória em todos os sistemas individuais.
• Um modelo que está mais próximo do comportamento de máquinas multiprocessadoras do mundo real e leva em conta o uso de instruções da máquina, tais como Comparar e Despertar (CAS), é o de memória compartilhada assíncrona. Há um amplo corpo de trabalho neste modelo, um resumo do qual pode ser encontrado na literatura.

Algoritmos paralelos no modelo de passagem de mensagens

• O designer de algoritmos escolhe a estrutura da rede, bem como o programa executado por cada computador.
• Modelos como circuitos booleanos e redes de classificação são usados. Um circuito booleano pode ser visto como uma rede de computador: cada portão é 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 no modelo de passagem de mensagens

• O designer de algoritmos só escolhe o programa de computador. Todos os computadores executam o mesmo programa. O sistema deve funcionar corretamente, independentemente da estrutura da rede.
• Um modelo comumente usado é um gráfico com uma máquina de estado finito por nó.

No caso de algoritmos distribuídos, os problemas computacionais são tipicamente relacionados a grafos. Freqüentemente, o gráfico que descreve a estrutura da rede de computadores é a instância do problema. Isto é ilustrado no exemplo seguinte.

Um exemplo

Considere o problema computacional de encontrar uma coloração de um determinado gráfico G. Campos diferentes podem adotar 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 cadeia de caracteres e produz o resultado.

Algoritmos paralelos

• Novamente, o gráfico G é codificado como uma string. No entanto, vários computadores podem acessar a mesma cadeia em paralelo. Cada computador pode se concentrar em uma parte do gráfico e produzir uma coloração para essa parte.
• O foco principal é a computação de alto desempenho que explora o poder de processamento de vários computadores em paralelo.

Algoritmos distribuídos

• O gráfico G é a estrutura da rede de computadores. Há um computador para cada nó de G e um link de comunicação para cada borda de G. Inicialmente, cada computador só sabe sobre seus vizinhos imediatos no gráfico G; os computadores devem trocar mensagens uns com os outros para descobrir mais sobre a estrutura de G. Cada computador deve produzir sua própria cor como saída.
• O foco principal é a coordenação da operação de um sistema distribuído arbitrário.

Embora o campo de algoritmos paralelos tenha um foco diferente do campo de algoritmos distribuídos, há muita interação entre os dois campos. Por exemplo, o algoritmo de Cole-Vishkin para coloração de grafos foi originalmente apresentado como um algoritmo paralelo, mas a mesma técnica também pode ser usada diretamente como um algoritmo distribuído.

Além disso, um algoritmo paralelo pode ser implementado em um sistema paralelo (usando memória compartilhada) ou em um sistema distribuído (usando passagem de mensagens). A fronteira tradicional entre algoritmos paralelos e distribuídos (escolher uma rede adequada vs. rodar em qualquer rede dada) não está no mesmo lugar que a fronteira entre sistemas paralelos e distribuídos (memória compartilhada vs. passagem de mensagens).

Medidas de complexidade

Nos algoritmos paralelos, outro recurso além do tempo e do espaço é o número de computadores. De fato, muitas vezes há um compromisso entre o tempo de execução e o número de computadores: o problema pode ser resolvido mais rapidamente se houver mais computadores executando em paralelo (consulte aceleração). Se um problema de decisão pode ser resolvido em tempo polilogarítmico usando um número polinomial de processadores, diz-se que o problema está na classe NC. A classe NC pode ser definida igualmente bem usando o formalismo PRAM ou circuitos booleanos - as máquinas PRAM podem simular circuitos booleanos de forma eficiente e vice-versa.

Na análise de algoritmos distribuídos, geralmente é dada mais atenção às operações de comunicação do que às etapas computacionais. Talvez o modelo mais simples de computação distribuída seja um sistema síncrono em que todos os nós operam de maneira padronizada. Esse modelo é comumente conhecido como modelo LOCAL. Durante cada rodada de comunicação, todos os nós em paralelo (1) recebem as últimas mensagens de seus vizinhos, (2) executam cálculos locais arbitrários e (3) enviam novas mensagens para seus vizinhos. Em tais sistemas, uma medida de complexidade central é o número de rodadas de comunicação síncrona necessárias para concluir a tarefa.

Essa medida de complexidade está intimamente relacionada ao diâmetro da rede. Seja D o diâmetro da rede. Por um lado, qualquer problema computável pode ser resolvido trivialmente em um sistema distribuído síncrono em aproximadamente 2 D rodadas de comunicação: basta reunir todas as informações em um local (D rodadas), resolva o problema e informe cada nó sobre a solução (D rodadas).

Por outro lado, se o tempo de execução do algoritmo for muito menor que D rodadas de comunicação, então os nós da rede devem produzir sua saída sem ter a possibilidade de obter informações sobre partes distantes da rede. Em outras palavras, os nós devem tomar decisões globalmente consistentes com base nas informações disponíveis em sua vizinhança D local. Muitos algoritmos distribuídos são conhecidos com tempo de execução muito menor que D rodadas, e entender quais problemas podem ser resolvidos por tais algoritmos é uma das questões centrais de pesquisa da área. Tipicamente um algoritmo que resolve um problema em tempo polilogarítmico no tamanho da rede é considerado eficiente neste modelo.

Outra medida comumente usada é o número total de bits transmitidos na rede (cf. complexidade da comunicação). Os recursos desse conceito são normalmente capturados com o modelo CONGEST(B), que é definido de forma semelhante ao modelo LOCAL, mas onde mensagens únicas podem conter apenas B bits.

Outros problemas

Os problemas computacionais tradicionais assumem a perspectiva de que o usuário faz uma pergunta, um computador (ou um sistema distribuído) processa a pergunta, então produz uma resposta e para. No entanto, também existem problemas em que o sistema é obrigado a não parar, incluindo o problema dos filósofos jantando e outros problemas de exclusão mútua semelhantes. Nesses problemas, o sistema distribuído deve coordenar continuamente o uso de recursos compartilhados para que não ocorram conflitos ou impasses.

Há também desafios fundamentais exclusivos da computação distribuída, por exemplo, aqueles relacionados à tolerância a falhas. Exemplos de problemas relacionados incluem problemas de consenso, tolerância a falhas bizantinas e auto-estabilização.

Muita pesquisa também está focada em entender a natureza assíncrona dos sistemas distribuídos:

• Sincronizadores podem ser usados para executar algoritmos síncronos em sistemas assíncronos.
• Relógios lógicos fornecem uma causal aconteceu antes de ordenar eventos.
• Os algoritmos de sincronização do relógio fornecem carimbos de tempo físico globalmente consistentes.

Eleição

Eleição do coordenador (ou eleição do líder) é o processo de designar um único processo como o organizador de alguma tarefa distribuída entre vários computadores (nós). Antes que a tarefa seja iniciada, todos os nós da rede não sabem qual nó servirá como o "coordenador" (ou líder) da tarefa, ou incapaz de se comunicar com o coordenador atual. Depois que um algoritmo de eleição do coordenador foi executado, no entanto, cada nó em toda a rede reconhece um nó específico e exclusivo como o coordenador da tarefa.

Os nós da rede se comunicam entre si para decidir qual deles entrará no "coordenador" estado. Para isso, precisam de algum método para quebrar a simetria entre eles. Por exemplo, se cada nó tiver identidades únicas e comparáveis, os nós podem comparar suas identidades e decidir que o nó com a identidade mais alta é o coordenador.

A definição desse problema é frequentemente atribuída a LeLann, que o formalizou como um método para criar um novo token em uma rede token ring na qual o token foi perdido.

Os algoritmos de eleição do coordenador são projetados para serem econômicos em termos de total de bytes transmitidos e tempo. O algoritmo sugerido por Gallager, Humblet e Spira para grafos gerais não direcionados teve um forte impacto no projeto de algoritmos distribuídos em geral e ganhou o Prêmio Dijkstra por um artigo influente em computação distribuída.

Muitos outros algoritmos foram sugeridos para diferentes tipos de grafos de rede, como anéis não direcionados, anéis unidirecionais, grafos completos, grades, grafos de Euler direcionados e outros. Um método geral que separa a questão da família de grafos do projeto do algoritmo de eleição do coordenador foi sugerido por Korach, Kutten e Moran.

Para realizar a coordenação, os sistemas distribuídos empregam o conceito de coordenadores. O problema de eleição do coordenador consiste em escolher um processo dentre um grupo de processos em diferentes processadores em um sistema distribuído para atuar como o coordenador central. Existem vários algoritmos de eleição do coordenador central.

Propriedades de sistemas distribuídos

Até agora o foco tem sido desenhar um sistema distribuído que resolva um determinado problema. Um problema de pesquisa complementar é estudar as propriedades de um determinado sistema distribuído.

O problema da parada é um exemplo análogo do campo da computação centralizada: recebemos um programa de computador e a tarefa é decidir se ele para ou continua para sempre. O problema da parada é indecidível no caso geral e, naturalmente, entender o comportamento de uma rede de computadores é pelo menos tão difícil quanto entender o comportamento de um computador.

No entanto, existem 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 interação (assíncrona e não determinística) pode atingir 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.