Pr-1st-1.1-m03-Slajd14

Relacja poprzedzania zdarzeń

Zbiór zdarzeń ${{ℰ}}_i$ procesu $P_i$ jest w pełni uporządkowany, według kolejności ich występowania w czasie lokalnym t. Ze względu jednak na nieprzewidywalne czasy transmisji i brak wiedzy o czasie globalnym $\tau$, uporządkowanie w praktyce zbioru $\mathrm{\Lambda }$ zdarzeń wszystkich procesów $P_i\in {𝒫}$, stanowi poważną trudność. Oznaczmy przez $\mapsto$ relację poprzedzania (ang. happen before, causal precedence, happened before) zdefiniowaną na zbiorze $\mathrm{\Lambda }$ w następujący sposób: $E_i^k\mapsto E_j^l⟺\{\begin{array}{l}\text{1)}i=j\wedge k<l,\text{ lub }\\ \text{2)}i\ne j\text{ oraz }{E}_i^k\text{ jest zdarzeniem }e\mathrm{\_}send(P_i,P_j,M)\text{ wysłania wiadomości }M,\\ \text{ a zdarzenie }{E}_j^l\text{ jest zdarzeniem }e\mathrm{\_}receive(Pi,Pj,M)\text{ odbioru tej samej wiadomości, lub }\\ \text{3)}\text{ istnieje sekwencja zdarzeń }{E}^0,E^1,E^2,\dots ,E^s\text{, taka że }{E}^0=E_i^k,E^s=E_j^l\text{ i dla każdej pary }⟨E^u,E^{u+1}⟩\\ \text{ gdzie }0\le u\le s-1\text{, zachodzi 1) albo 2).}\end{array}$

Relacja poprzedzania jest antysymetryczna i przechodnia, a więc jest relacją częściowego porządku.

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