Como converter um algoritmo centralizado em um algoritmo distribuído?

Question

Existe algum algoritmo ou procedimento para converter um algoritmo centralizado em um algoritmo distribuído?Existe algum resultado teórico ou análise de complexidade relevante?

Answer 1

Claro.Se você tiver um sistema distribuído com N máquinas, poderá sempre executar o algoritmo centralizado na máquina 1 e deixar as máquinas 2..N ociosas.

Se você está perguntando se todos os algoritmos sequenciais podem ser paralelizados, essa é uma questão em aberto, mas acredita-se que a resposta seja não:Veja o Classe de complexidade NC.Como afirma a Wikipédia,

provavelmente existem alguns problemas tratáveis ​​que são "inerentemente sequenciais" e não podem ser significativamente acelerados pelo uso do paralelismo.

Problemas P-completos são bons candidatos para problemas que provavelmente não são passíveis de aceleração por paralelismo.

Se você está perguntando se todos os algoritmos podem se tornar confiáveis ​​em um sistema distribuído, essa é uma questão sutil que depende dos tipos de falhas que você está considerando.Você pode investigar protocolos de consenso, replicação de máquina de estado, e a Teorema CAP.