Pr-1st-1.1-m09-Slajd06

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Sortowanie rozproszone – przykład

Sortowanie rozproszone – przykład


Każdy zprocesów ma za zadanie uporządkować (posortować) przypisany mu na wstępie zbiór <math<\mathcal{X}_{i+1}</math> i wyznaczyć element .

Następnie procesy wysyłają elementy do swoich lewych sąsiadów ioczekują na odpowiedź zawierającą . Po otrzymaniu wiadomości zwartością , a przed wysłaniem odpowiedzi, proces wyznacza nowy element .

W ogólności, nowo wyznaczony może być równy otrzymanemu ostatnio . Następnie każdy z procesów wysyła odpowiedź ze swoim elementem maksymalnym do prawego sąsiada. Po otrzymaniu odpowiedzi, procesy znów sortują zbiory <math<\mathcal{X}_{i+1}</math> i jeśli wwyniku tego sortowania wartość różnić się będzie od poprzednio wysłanego elementu minimalnego, to proces wysyła ten nowy element do lewego sąsiada.


Cel sortowania rozproszonego zostaje osiągnięty, gdy uporządkowany zostanie każdy zbiór <math<\mathcal{X}_{i}</math>, a ponadto dla każdego .


<< Poprzedni slajd | Spis treści | Następny slajd >>