Principais problemas não resolvidos em sistemas distribuídos?

Inspirados por essa pergunta , quais são os principais problemas e soluções existentes que precisam ser aprimorados no domínio de sistemas distribuídos (teóricos).

Algo como protocolos de associação, consistência de dados?

Veja, por exemplo, Oito problemas em aberto na computação distribuída .

A complexidade do tempo distribuído de vários problemas gráficos ainda é uma questão em aberto.

Em geral, algoritmos de gráfico distribuído são uma área na qual esperamos ter (pelo menos assintoticamente) correspondência entre limites superior e inferior para a complexidade do tempo distribuído dos problemas gráficos. Por exemplo, para muitos problemas de otimização, limites estreitos são conhecidos . No entanto, existem muitos problemas clássicos de quebra de simetria que ainda são pouco compreendidos.

Não sabemos, por exemplo, quantas rodadas de comunicação são necessárias para encontrar um conjunto independente máximo , uma correspondência máxima , uma coloração de vértice adequada com cores ou uma coloração de bordas adequada com $\Delta+1$ cores em um gráfico com um grau máximo de Δ . Todos esses problemas são fáceis de resolver com algoritmos centralizados gananciosos e existem algoritmos distribuídos eficientes para cada um desses problemas, mas não sabemos se algum dos algoritmos atuais é ideal.$2\Delta-1$$\Delta$

Por exemplo, para todos esses problemas, existem algoritmos distribuídos determinísticos para o modelo LOCAL com tempos de execução de , em que n é o número de nós. É sabido que esses problemas não podem ser resolvidos no tempo O ( Δ ) + o ( log ∗ n ) rodadas, mas não se sabe se eles podem ser resolvidos no tempo o ( Δ ) $O(\Delta + \log^* n)$$n$$O(\Delta) + o(\log^* n)$$o(\Delta) + O(\log^* n)$rodadas. Em geral, não entendemos como os tempos de execução dependem do grau máximo - é o que chamo de problema de coordenação local .

O papel da aleatoriedade é outra questão importante. Por exemplo, muitos dos problemas mencionados acima podem ser resolvidos em tempo de polilog com algoritmos aleatórios (ou seja, o tempo é polilog em $n$ para qualquer valor de ), mas nenhum algoritmo determinístico de tempo de polilogio é conhecido para, por exemplo, conjuntos independentes máximos . Essas perguntas, assim como muitos outros problemas em aberto, são discutidas em mais detalhes na Seção 11 do livro recente de Barenboim e Elkin .$\Delta$

Acima, concentrei-me em questões específicas da computação distribuída. Também existem questões em aberto em algoritmos de gráficos distribuídos que têm conexões não triviais para abrir problemas na ciência da computação teórica em geral. Por exemplo, limites inferiores não constantes para o modelo de clique congestionado são uma grande questão em aberto na computação distribuída; descobriu-se recentemente que esses limites inferiores também implicariam novos limites inferiores para o ACC.

Problemas abertos em "Algoritmos distribuídos para árvores abrangentes mínimas (MST)": (listados em [1])

1. Relativo complexidade do tempo ,

   Algoritmos ótimos e limites inferiores são apresentados em [2] e referências aqui. A complexidade do tempo ideal continua sendo um problema em aberto.

2. Relativo complexidade da mensagem ,

   Quanto à complexidade da mensagem , embora o limite assintoticamente restrito de $O(m + n \log n)$ seja conhecido para o problema MST em gráficos gerais, encontrar as constantes reais permanece um problema em aberto.

3. Relativo modelo síncrono :

   $O(\log \log n)$

$O(\log n)$

[1] Algoritmos distribuídos para árvores de extensão mínima por Sergio Rajsbaum em "Encyclopedia of Algorithms", 2008.

[2] MST distribuído para gráficos de diâmetro constante de Lotker et al. Distrib. Comput., 2006.

$O(\log \log n)$

[4] Um algoritmo de aproximação distribuído rápido para árvores de abrangência mínima de Khan et al. DISC 2006.

veja também (mais recentemente) uma apresentação de slides "Problemas não resolvidos da ciência da computação na computação distribuída" de 2012 pelo pesquisador da Notre Dame Douglas Thain, que lidera seu laboratório de computação cooperativa. tem mais uma inclinação aplicada, mas as questões-chave listadas inevitavelmente levam a áreas teóricas.

• O problema do Kiloscale: qualquer fluxo de trabalho com simultaneidade suficiente deve ser capaz de executar corretamente em núcleos 1K pela primeira vez e sempre, sem ajuda do administrador de sistemas.

• O problema da parada: dado um fluxo de trabalho executado em mil nós, faça-o parar e limpar todo o estado associado com total segurança.

• O Problema da Dependência:

  (1) Dado um programa, descubra tudo o que ele realmente precisa para executar em uma máquina diferente.

  (2) Dado um processo, descubra os recursos (distribuídos) que ele realmente usa durante a execução.

  (3) Estenda 1 e 2 a um fluxo de trabalho inteiro.

• O problema do dimensionamento correto: dado um aplicativo (estruturado) e um determinado cluster, nuvem ou grade, escolha uma alocação de recursos que atinja um bom desempenho a um custo aceitável.

• O problema da solução de problemas: Quando ocorre uma falha no meio de uma pilha de software de 100 camadas, como e quando você relata / tenta novamente / ignora / suprime o erro?

• O problema de design: como os aplicativos devem ser projetados para serem adequados à computação distribuída?