So konvertieren Sie einen zentralisierten Algorithmus in einen verteilten Algorithmus?

Question

Gibt es einen Algorithmus oder ein Verfahren, um einen zentralisierten Algorithmus in einen verteilten Algorithmus umzuwandeln?Gibt es theoretisches Ergebnis oder relevante Komplexitätsanalyse?

Answer 1

sicher. Wenn Sie ein verteiltes System mit N-Maschinen haben, können Sie den zentralen Algorithmus immer auf der Maschine 1 ausführen und die Maschinen 2..n im Leerlauf setzen.

Wenn Sie fragen, ob alle sequentiellen Algorithmen parallelisiert werden können, ist das eine offene Frage, aber es wird angenommen, dass die Antwort nein ist: Sehen Sie sich das NC-Komplexitätsklasse . Wie Wikipedia heißt,

Es gibt wahrscheinlich einige taktlose Probleme, die "inhärent sequentiell" sind und nicht signifikant unter Verwendung der Parallelität aufgeführt werden können.

p-vollständige Probleme sind gute Kandidaten für Probleme, die wahrscheinlich nicht mit Parallelität beschleunigt werden.

Wenn Sie fragen, ob alle Algorithmen in einem verteilten System zuverlässig gemacht werden können, ist dies eine subtile Frage, die davon abhängt, welche Arten von Fehlern Sie in Betracht ziehen. Sie könnten in Zustandsmaschine Replikation und der Kappe theorem .