Comment convertir un algorithme centralisé en un algorithme distribué?

Question

existe-t-il un algorithme ou une procédure pour convertir un algorithme centralisé en un algorithme distribué?Y a-t-il un résultat théorique ou une analyse de complexité pertinente?

Answer 1

Bien sûr. Si vous avez un système distribué avec N machines, vous pouvez toujours exécuter l'algorithme centralisé sur la machine 1 et laisser des machines 2..n Sit inactif.

Si vous demandez si tous les algorithmes séquentiels peuvent être parallélédisés, c'est une question ouverte, mais on croit que la réponse est non: voir le Classe de complexité NC . Comme les états Wikipedia,

Il y a probablement des problèmes traitants qui sont "intrinsèquement séquentiels" et ne peuvent pas être augmentés de manière significative en utilisant du parallélisme.

Les problèmes de P-complète sont de bons candidats aux problèmes susceptibles de ne pas accélérer par le parallélisme.

Si vous demandez si tous les algorithmes peuvent être fiables dans un système distribué, c'est une question subtile qui dépend de quels types de défaillances que vous envisagez. Vous pourriez regarder dans Protocoles de consensus , Réplication de la machine d'état et le THEOREM CAP .