Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-pos:4-pos [2019/06/09 21:53]
lachmanfrantisek
+++ mgr-szz:in-pos:4-pos [2020/04/12 16:56] (aktuální)
@@ Řádek 1: / Řádek 1: @@
-====== IN-POS 4. Modely distribuovaných systémů ======
+====== IN-POS . Modely distribuovaných systémů ======
 ===== Zadání =====
@@ Řádek 23: / Řádek 23: @@
 DS:
   * umožňují souběžné řešení programů
-  * neexistuje globální čas
   * každá komponenta (včetně propojovací sítě) může selhávat a obnovovat činnost nezávisle na okolí.
     * ostatní se o stavu nedozvídají
@@ Řádek 45: / Řádek 44: @@
 <box 90% blue|Cristianův algoritmus synchronizace hodin>
-Klient pošle dotaz Časovému serveru a od získaného času odečte polovinu obrátky dotazu.
+Klient pošle dotaz **časovému serveru** a od získaného času přičte polovinu obrátky dotazu.
 </box>
 <box 90% blue|Berkeley algoritmus synchronizace hodin>
   - MASTER uzel se periodicky ptá na čas SLAVE uzlů.
-  - Odečte polovinu obrátky.
+  - Přičte polovinu obrátky.
   - Zprůměruje a odešle aktuální hodnotu SLAVE uzlům.
 </box>
@@ Řádek 99: / Řádek 98: @@
 </box>
-=== Globální stav ===
+==== Detekce ukončení ====
+Algoritmus synchronizace ukončení má za úkol zabezpečit následující:
+V případě, že všechny procesy jsou ve stavu ukončen, pak se v konečném čase tuto skutečnost všechny procesy dozví.
+<box 90% blue|Dijkstra-Scholten (DS)>
+  * Jestliže graf procesů je strom, pak každý listový proces při přechodu do stavu ukončen pošle signál svému otci.
+  * Jakmile proces dostane signály od všech svých synů, pošle signál svému otci.
+  * Jestliže všechny signály dostane iniciační proces, je distribuovaný výpočet ukončen.
+</box>
 <box 90% blue|Global State Recording Algorithm Candy & Lamport>
@@ Řádek 114: / Řádek 124: @@
     * zná zprávy v "éteru"
     * Kanály jsou FIFO, tedy je globální momentka smysluplná ((ne)zahrnuté zprávy jsou odděleny v kanálech MARKERy).
+</box>
+=== Commit protokoly ===
+Řeší atomicitu distribuované transakce.
+<box 90% blue|2-fázový commit protokol>
+Distribuovaná dohoda, zda transakci končit řádně, či krachovat v prostředí s výpadky uzlů.
+  * ➕ řeší problém atomického ukončení
+    * jestli jedna subtransakce krachuje, krachuje celá transakce
+    * jestli se ukončí řádně všechny subtransakce, ukončí se řádně i celá transakce
+fáze:
+  * **Hlasovací fáze**
+    * koordinátor žádá o závazek k rozhodnutí, že subtransakci řádně ukončí
+    * participant ověří subtransakci na konzistenci dat a odpoví
+  * **Fáze vydání rozhodnutí**
+    * Koordinátor vydává na základě získaných odpovědí rozhodnutí zda řádně ukončit, nebo krachovat.
+      * Zprávy commit/abort.
 </box>
@@ Řádek 356: / Řádek 389: @@
   * **participant**
     * může kdykoliv volat koordinátora požadavkem ''abort-transaction'', pokud není schopen pokračovat v řešení subtransakce.
-</box>
-==== Detekce ukončení ====
-== Commit protokoly ==
-Řeší atomicitu distribuované transakce.
-<box 90% blue|2-fázový commit protokol>
-Distribuovaná dohoda, zda transakci končit řádně, či krachovat v prostředí s výpadky uzlů.
-  * ➕ řeší problém atomického ukončení
-    * jestli jedna subtransakce krachuje, krachuje celá transakce
-    * jestli se ukončí řádně všechny subtransakce, ukončí se řádně i celá transakce
-fáze:
-  * **Hlasovací fáze**
-    * koordinátor žádá o závazek k rozhodnutí, že subtransakci řádně ukončí
-    * participant ověří subtransakci na konzistenci dat a odpoví
-  * **Fáze vydání rozhodnutí**
-    * Koordinátor vydává na základě získaných odpovědí rozhodnutí zda řádně ukončit, nebo krachovat.
-      * Zprávy commit/abort.
 </box>
@@ Řádek 388: / Řádek 396: @@
 <box 90% red|Problém volby vůdce>
-Každž výpočet podle volebního algoritmu ve skupině procesů DS musí v konečném čase končit konfigurací, ve které je jeden jediný uzel v roli vůdce.
+Každý výpočet podle volebního algoritmu ve skupině procesů DS musí v konečném čase končit konfigurací, ve které je jeden jediný uzel v roli vůdce.
 Každý proces se během existence může nacházet ve třech stavech:
@@ Řádek 429: / Řádek 437: @@
 <box 90% blue|Ring algorithm (Chang, Roberts)>
-Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected.
+Využitelnou topologií je obousměrný kruh. Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected.
   * Každý proces je ve stavu ''participant'', nebo ''non-participant''.
@@ Řádek 445: / Řádek 453: @@
   * ➕ sledování stavu ''participant''/''non-participant'' umožňujue likvidovat zbytečné násobné běhy.
   * ➖ výpadek uzlu značí výpadek celé úlohy
+  * nejhorší případ: O(n*n) zpráv
+  * očekávaný počet zpráv: O(n log n) zpráv
 </box>
@@ Řádek 454: / Řádek 465: @@
   * Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti <m>2^r</m>)
     * Ostatní pouze přeposílají zprávy.
+  * složitost: O(n log n)
 </box>
@@ Řádek 460: / Řádek 473: @@
 Použitelnost:
-  * proces může poslat zprávu každému z ostatních procesů.
+  * Proces může poslat zprávu každému z ostatních procesů.
   * Mohou se vyskytovat výpadky uzlů.
     * Poznán na základě timeoutu.
@@ Řádek 484: / Řádek 497: @@
 ==== Vliv topologie a její znalosti/neznalosti na složitost řešení problému ====
-FIXME: bohužel jsem nenašel vhodné materiály a nejsem si jistý, co by tento bod měl všechno obsahovat (IV100 jsem neměl)  --- //[[lachmanfrantisek@gmail.com|František Lachman]] 2019/06/09 20:58//
+FIXME: nejsem si 100% jistý, co se zde očekává (resp. z čeho čerpat)
+  * Efektivita algoritmu velmi závisí na topologii sítě.
+  * Zajímá nás **komunikační složitost**, případně časová složitost.
+<box 90% red|Horní odhad pro problém>
+Existuje algoritmus, který pro všechny topologie, vstupy, časování,... pracuje správně a vymění nejvíc f(n) zpráv.
+</box>
+<box 90% red|Dolní odhad pro problém>
+Pro každý algoritmus existuje kombinace topologie, vstupu, časování,... že buď nepracuje správně, nebo vymění alespoň f(n) zpráv.
+</box>
+  * Časté topologie:
+    * **úplný graf**
+        * každý komunikuje přímo s každým
+    * **kruh**
+      * každý má levého a pravého souseda
+      * všichni jsou uspořádání do kruhu
+    * **jednosměrný kruh**
+      * každý má jen jednoho souseda
+      * po N přeposláních se zpráva dostane zpět k původci
+    * **2D/3D mřížka**
+    * **strom**
+  * Pro tyto topologie existují často efektivnější algoritmy, protože lze spoléhat na jejich vlastnosti.
+  * Pro globální algoritmy se může efektivita lišit na základě grafových vlastností:
+    * hustota grafu
+    * orientovanost
+    * poloměr
+  * Pro tvorbu paralelních algoritmů je nejprve potřebné zvládnout několik principielních úloh:
+    * prohledávání uzlů
+      * shout-and-echo (4m zpráv, 2diam(G) čas)
+      * DFS (2m zpráv, 2m čas)
+      * Awerbuch (4m zpráv, 4n−2 čas)
+      * BFS:
+        * Cheung’83 (<m>m^3</m> zpráv, m čas)
+        * Cheung,Zhu’87 (<m>m^2</m> zpráv, <m>m^2</m> čas)
+    * komunikace mezi uzly
+    * volba vůdce
+      * globální algoritmus (<m>\Omega (n \log n)</m> zpráv)
+  * Další důležité parametry:
+    * jednosměrnost/obousměrnost hran
+    * (ne)znalost sítě/sousedů
+    * existuje globální čas
+    * očíslování hran
+    * identifikace jednotlivých uzlů
@@ Řádek 491: / Řádek 553: @@
   * slidy pa150 (podzim 2017)
   * http://statnice.dqd.cz/mgr-szz:in-pos:1-pos
+  * http://statnice.dqd.cz/mgr-szz:in-tei:8-tei

mgr-szz/in-pos/4-pos.1560110011.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru