Come convertire un algoritmo centralizzato in un algoritmo distribuito?

Question

Esiste un algoritmo o una procedura per convertire un algoritmo centralizzato in un algoritmo distribuito?C'è qualche risultato teorico o analisi della complessità pertinente?

Answer 1

sicuro. Se si dispone di un sistema distribuito con N macchine, è possibile eseguire sempre l'algoritmo centralizzato sulla macchina 1 e lasciare che le macchine 2..nn si siedono inattivo.

Se stai chiedendo se tutti gli algoritmi sequenziali possano essere parallelati, questa è una domanda aperta, ma si ritiene che la risposta sia: vedere il Classe di complessità NC . Come afferma Wikipedia,

.

Ci sono probabilmente alcuni problemi trattabili che sono "intrinsecamente sequenziali" e non possono essere significativamente impegnati usando il parallelismo.

P-Problemi completi sono buoni candidati per problemi che possono suscettibili di accelerare per parallelismo.

Se stai chiedendo se tutti gli algoritmi possano essere resi affidabili in un sistema distribuito, cioè una domanda sottile che dipende da quali tipi di fallimenti che stai considerando. Potresti guardare in Protocolli di consenso , replica della macchina dello stato e Cap Teorem .