Uspořádání zpráv je jedna z garancí definovaných komunikačním modelem distribuovaného systému, která určuje, v jakém pořadí jsou zprávy doručovány aplikacím.

Typy uspořádání

Musíš vědět, jaké garance pořadí systém nabízí:

FIFO uspořádání

• Garance: Zprávy od jednoho konkrétního odesílatele dorazí ve správném pořadí.
• Příklad: Když já pošlu “$A$” a pak “$B$”, všichni dostanou “$A$” a pak “$B$”. Ale mezi to se může vklínit zpráva od někoho jiného.

  Kauzální uspořádání (causal ordering)

  Je to garance doručovacího protokolu, která zajišťuje, že fyzické doručení zpráv respektuje jejich kauzální závislost.

1. Vztah ke kauzální závislosti

Zatímco kauzální závislost (A→B) je teoretický vztah mezi dvěma událostmi (happened-before relate), kauzální uspořádání je praktický mechanismus, který tento vztah vynucuje v síti.

Formální definice: Pokud odeslání zprávy $m_1​$ kauzálně předchází odeslání zprávy $m_2$​ (Send(m1​)→Send(m2)), pak systém garantuje, že každý uzel, který přijme obě zprávy, musí doručit $m_1$​ aplikaci předtím, než doručí $m_2$​.

2. Rozdíl oproti FIFO

• FIFO: Řeší pouze pořadí od jednoho odesílatele ($m_1$​ a $m_2$​ jsou od procesu P).
• Kauzální: Řeší pořadí napříč celým systémem (řetězec závislostí může jít přes více uzlů: $P_1$​ pošle $m_1​$ → $P_2$​ přijme a pošle $m_2​$).

  3. Implementace (jak se to pozná?)

  Protokol nemůže tušit obsah zpráv (neví, že $m_2$​ je odpověď na $m_1$​). Musí spoléhat na metadata.

• Nástroj: logický čas#Vektorové hodiny (vector clocks).
• Princip: Zpráva $m_2​$ si nese informaci (vektor): “Jsem závislá na zprávě m1​ od procesu P1​.”
• Vynucení: Pokud přijde m2​ k příjemci dříve než m1​, příjemce vidí v jejím vektoru závislost, kterou nemá splněnou. Zpráva m2​ je zadržena (Hold-back Queue), dokud po síti nedorazí opožděná m1​

  4. Výhoda (Proč to děláme?)

• Umožňuje modely konzistence distribuovaného systému#Causal Consistency (Kauzální).
• Je efektivnější než totální uspořádání, protože neblokuje zprávy, které spolu nesouvisí (tzv. souběžné zprávy). Pokud $m_x​∣∣m_y​$ (nejsou na sobě závislé), mohou být doručeny v libovolném pořadí.

  Totální uspořádání (total ordering)

• Garance: Všichni vidí všechno naprosto stejně.
• Pokud server A vidí pořadí zpráv $M_1​,M_2​,M_3​$, pak server B, C i D musí vidět $M_1​,M_2​,M_3​$.
• Použití: Nutné pro state machine replication (SMR)** (aby měly všechny databáze na konci stejná data). Je to nejpomalejší a nejtěžší na implementaci.

Vztah mezi jednotlivými broadcast modely