Tri par insertion dans un système distribué

Question

Comment le tri par insertion gère-t-il plusieurs copies d'un tableau dans un système distribué? Je demande parce qu'il est plus facile de lire des données que de les écrire. Quel sera le coût de l'algorithme dans un système distribué en termes de nombre de mises à jour?

Answer 1

Cela dépend totalement de votre version du tri d'insertion distribuée. Une solution peut être la suivante:

1. Le tableau A (avec n éléments) est partagé avec tous les nœuds du système.
2. Le tableau A peut être partitionné en sous-tableaux A1, A2, A3, ..., Ap, où p est le nombre de machines dans le système. Ce partitionnement est effectué distribué. C'est-à-dire que chaque noeud trouve la limite inférieure et la limite supérieure de son sous-tableau. (ceci peut être fait en trouvant des médianes et en divisant le tableau et en trouvant à nouveau la médiane et ainsi de suite.)
3. Maintenant, chaque noeud peut trier sa tranche en utilisant le tri d'insertion.
4. Les sous-matrices triées dans chaque noeud peuvent être fusionnées soit par un tri de type tri d'insertion.

Remarque: Il n'est pas correct de mesurer l'efficacité d'un algorithme distribué en comptant le nombre de mises à jour. Dans la mesure où de nombreuses mises à jour sont effectuées simultanément, la complexité totale de l'exécution doit être prise en compte.