Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b36pdv [2025/06/04 22:40] – [Typy detekčních protokolů] zapleka3 | statnice:bakalar:b4b36pdv [2025/06/04 22:52] (current) – [Logické hodiny a kauzalita] zapleka3 | ||
|---|---|---|---|
| Line 765: | Line 765: | ||
| * **Úplnost** je zaručena. | * **Úplnost** je zaručena. | ||
| * **Průměrný čas detekce**: | * **Průměrný čas detekce**: | ||
| - | * %% \frac{e}{e - 1} \mathcal{T} | + | * $\frac{e}{e - 1} \mathcal{T}$ |
| + | * průměrná délka detekčního cyklu v SWIM protokolu | ||
| * Dobře funguje i ve velkých systémech (1000+ uzlů). | * Dobře funguje i ve velkých systémech (1000+ uzlů). | ||
| Line 783: | Line 784: | ||
| * Každý proces $p_i$ má své hodiny $\mathcal{C}_i$ udržované v rozmezí $\delta$ od nějakého **externího referenčního času** $\mathcal{S}$. | * Každý proces $p_i$ má své hodiny $\mathcal{C}_i$ udržované v rozmezí $\delta$ od nějakého **externího referenčního času** $\mathcal{S}$. | ||
| * Např. atomové hodiny, UTC, NTP servery. | * Např. atomové hodiny, UTC, NTP servery. | ||
| - | * Formálně: %% |\mathcal{C}_i - \mathcal{S}| \leq \delta | + | * $|\mathcal{C}_i - \mathcal{S}| \leq \delta$ |
| + | * Každý uzel se snaží držet v intervalu | ||
| * Typický příklad: **NTP (Network Time Protocol)**. | * Typický příklad: **NTP (Network Time Protocol)**. | ||
| === Interní synchronizace === | === Interní synchronizace === | ||
| * Zajišťuje, | * Zajišťuje, | ||
| - | * Formálně: | + | * Formálně: |
| + | * Rozdíl mezi hodinami dvou uzlů je nejvýše $\delta$ | ||
| * Není vázaná na žádný „reálný čas“, ale zajistí, že uzly se navzájem „drží při sobě“. | * Není vázaná na žádný „reálný čas“, ale zajistí, že uzly se navzájem „drží při sobě“. | ||
| * Např. **Berkeley algorithm**. | * Např. **Berkeley algorithm**. | ||
| Line 798: | Line 801: | ||
| * Server odpoví, a klient si upraví svůj čas podle: | * Server odpoví, a klient si upraví svůj čas podle: | ||
| - | %% \mathcal{C}_i := t + \frac{\mathcal{T}_{RT} - l_{\text{min}} - l' | + | $\mathcal{C}_i := t + \frac{\mathcal{T}_{RT} - l_{\text{min}} - l' |
| + | * RTT mínus odhadnutá minimální latence tam i zpět, děleno dvěma | ||
| + | |||
| + | Očekávaná **chyba synchronizace** je: $\leq \frac{\mathcal{T}_{RT} - l_{\text{min}} - l' | ||
| - | Očekávaná **chyba synchronizace** je: %% \leq \frac{\mathcal{T}_{RT} - l_{\text{min}} - l' | ||
| Lokální čas lze zvyšovat okamžitě, ale **nelze ho vracet zpět** – místo toho se mění rychlost přibývání. | Lokální čas lze zvyšovat okamžitě, ale **nelze ho vracet zpět** – místo toho se mění rychlost přibývání. | ||
| Line 809: | Line 814: | ||
| * Latence se odhaduje pomocí offsetu: | * Latence se odhaduje pomocí offsetu: | ||
| - | %% o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2} | + | $o = \frac{(t_1^{r} - t_2^{r} + t_2^{s} - t_1^{s})}{2}$ |
| + | * vypočtený odhad ofsetu mezi hodinami klienta a serveru | ||
| ==== Logické hodiny a kauzalita ==== | ==== Logické hodiny a kauzalita ==== | ||
| Line 832: | Line 838: | ||
| Důležité: | Důležité: | ||
| - | * Jestliže $e_1 \rightarrow e_2$, pak %% \mathcal{C}(e_1) < \mathcal{C}(e_2) | + | * Jestliže $e_1 \rightarrow e_2$, pak $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ |
| - | * Ale: | + | * Ale: $\mathcal{C}(e_1) < \mathcal{C}(e_2)$ **neznamená**, |
| ⇒ Lamportovy hodiny **respektují kauzalitu**, | ⇒ Lamportovy hodiny **respektují kauzalitu**, | ||
