Globální stav v DS

• Lokální stav procesu = hodnoty proměnných, alokované zdroje, stav vykonávání programu.

• Globální stav DS = lokální stav všech procesů DS a stavy všech kanálů mezi nimi.

• Řez = rozdělení události v systému na dvě skupiny.

  • Ty co se již staly a ty co se ještě nestaly.

• Snapshot = Globální stav DS v daném okamžiku.

  • Stav (konzistentního) řezu.

Konzistentní řez a konzistentní snapshot

• Konzistentní řez $C$: Pokud událost $b\in C\wedge a\to b$, pak $a\in C$.
• Postup výpočtu v DS je posloupnost konzistentních řezů.
• Konzistentní snapshot je zachycení stavu konzistentního řezu.
• c1 je nekonzistentní, c2 je konzistentní řez.

Chandy-Lamport algoritmus

• Algoritmus využívající techniku distribuovaný snímek.
• Slouží k výpočtu snapshotu.

Postup algoritmu:

1. Iniciátor uloží svůj stav, pošle zprávu s markerem (snapshot request).
2. Proces obdrží zprávu s markerem:
3. Poprvé:
   • Uloží svůj stav.
   • Uloží příchozí kanál (ze kterého market přišel) jako prázdný (zprávy přijaté po marketu nejsou součástí snímku).
   • Pošle marker zprávy všem ostatním procesům přes své výstupní kanály.
4. Jindy: Uloží stav na kanálu.
5. Proces s markerem dostane zprávu bez markeru

• Musí být z okamžiku před snapshotem,
• přepošle ji iniciátorovi, aby ji přidal

• FIFO kanály (jinak problém)

Dijkstra-Scholten algoritmus

• Algoritmus pro detekci ukončení výpočtu.
• Jeho cílem je určit, kdy všechny uzly v DS dokončili svůj běh a jsou v bezpečném stavu pro ukončení celého systému.
• V síti buduje kostru (podobné volbě leadera v ad-hoc síti).
• Posílají se dva typy zpráv - SIGNAL a ACK.

Princip:

• Každý uzel je aktivní (pracuje) nebo pasivní.
• Každý uzel eviduje svůj deficit, což je rozdíl mezi poslanými a přijatými SIGNAL a ACK (na vstupu i na výstupu). Na začátku jsou oba $0$.
• Iniciátor pošle SIGNAL.
• Uzel pošle ACK pokud deficit na vstupu je větší než $1$, nebo deficit na vstupu je $1$ a na výstupu je $0$ a uzel je pasivní.

Předchozí otázka Následující otázka

Všechny otázky