# 2025: Комп'ютерні системи і мережі. 3. Узгодження стану. Синхронізація часу
[TOC]
# [1 Проблеми синхронізації та узгодження станів розподіленої системи]((https://en.wikipedia.org/wiki/Synchronization_(computer_science)))
## 1.1 Визначення
Термін **синхронізація** визначає три різні, але близькі концепції:
* *синхронізація процесів*
* *синхронізація даних*
* *синхронізація часу*
*Синхронізація процесів* відноситься до ситуацій, коли процеси повинні дочекатися загальної точки в часі або виконати фазу "рукостискання", для досягнення угоди або здійснення деякої послідовності дій.
*Синхронізація даних* описує концепцію узгодження множини копій даних (станів) або підтримку цілісності даних.
*Синхронізація годинників* — це проблема координації незалежних годинників в розподілених комп'ютерних мережах. Навіть якщо початково вони налаштовані точно, реальні годинники відрізнятимуться через певний проміжок часу через дрейф годинника, викликаний тим, що годинники відраховують час з дещо іншою швидкістю.
## 1.2 Cинхронізація у локальних системах
[1.У локальних системах синхронізація це:](https://www.wikiwand.com/en/Synchronization_(computer_science))
* Узгодження стану пам'яті та кешу
* Узгодження стану файлової системи
* Погодження транзакцій
## 1.3 Cинхронізація у розподiлених системах
[У розподiлених системах синхронізація це:](https://www.wikiwand.com/en/Data_synchronization)
* Синхронізація часу
* Асинхронне та синхронне узгодження даних
* Погодження станів розподілених додатків
* Розпізнавання збоїв та помилок та забезпечення стійкості до них
[](https://www.wikiwand.com/en/Data_synchronization)
- [ ] *Питання. Надточний 64-розрядний таймер, синхронізований з атомним годинником, відраховує тики з частотою 1000 гігаГерц. Які мінімальні та максимальні інтервали часу можна відраховувати на цьому таймері?*
**Узгодження часу**
# [2 Синхронізація часу](https://en.wikipedia.org/wiki/Clock_synchronization)
## 2.1 Проблема з годинниками
У розподіленій системі немає єдиного глобального годинника. Кожен комп'ютер
(будь-який обчислювальний пристрій) має власний годинник, і їхні матеріали, фізичні властивості, тактова частота різні. Крім того, залежно від фізичного стану навколишнього середовища, де розміщено комп'ютери, коливання температури можуть впливати на хід годинників. Таким чином, жодні годинники ніколи не будуть абсолютно однаковими з точки зору вимірювання часу. Між двома годинниками може бути різниця в кілька мілісекунд або навіть секунд.
### 2.1.1 Неузгодженість годинників $\theta$
Різниця $\theta$ між часом на двох годинниках називається **неузгодженістю годинників**. І ця різниця змінюється з часом. Тому неузгодженість пари годинників - це функція точного часу $t$ -- правильне її позначення $\theta(t)$. Ми будемо вважати, що точний час $t$ узгоджений з високоточними атомними годинниками і визначається щодо заданих реперних точок у часі та нульового меридіана. При цьому для конкретного комп'ютера, не підключеного до атомного годинника, цей точний час локально недоступний. Комп'ютер може наближатися до точного часу $t$ з більшими або меншими помилками, що визначаються інтернет-інфраструктурою та протоколами [NTP](https://en.wikipedia.org/wiki/Network_Time_Protocol), [PTP](https://en.wikipedia.org/wiki/Precision_Time_Protocol) та іншими протоколами синхронізації.
### 2.1.2 Дрейф годинника $\epsilon$
Немає стабільної частоти годинника, тобто з часом тактова частота буде іншою. Різниця тактових частот одного годинника за певний інтервал часу називається **дрейфом тактової частоти**. Звичайні кварцові годинники відхиляються приблизно на 1 секунду за 11–12 днів. Швидкість дрейфу змінюється від годинника до годинника.
- [ ] *Який дрейф кварцового годинника за 1 хвилину?*
- [ ] *Який дрейф атомного годинника за 1 хвилину?*
- [ ] *Який дрейф кварцового годинника за 1 секунду?*
- [ ] *Який дрейф атомного годинника за 1 секунду?*
- [ ] *Яка вартість кварцового годинника?*
- [ ] *Яка вартість атомного годинника?*
## [2.2 Афінні моделі комп'ютерних годинників та неузгодженості]()
### [2.2.1 Проста афінна модель комп'ютерного годинника]()
Ми будемо припускати просту афінну модель комп'ютерного годинника.
Використовуючи позначення точного часу $t$, відображення часу $\tau(t)$ годинника в узлі мережі з достатньою для короткочасних мережевих завдань точністю задовольняє виразу
$$
\tau(t) = \theta_0 + \sigma\cdot t = \theta_0 + (1+\epsilon)\cdot t \tag{𝜏|1}
$$
де
$\theta_0$ - розузгодження комп'ютерного годинника з ідеальним годинником у початковий момент,
$\sigma \approx 1$ - швидкість ходу комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту,
$|\epsilon| \ll 1$- дрейф (відхилення швидкості) комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту.
Якщо $\sigma$ -завжди позитивна величина, близька до 1, то $\epsilon$ - мала величина, яка може приймати як позитивні так і негативні значення.
Причина для вибору математичної моделі (𝜏|1) годинника полягає в тому, що це
найпростіша модель, яка відображає реальність, у якій годинник не є
синхронізований до високоточних атомних годинників через неномінальні швидкості та зміщення. Ця модель припускає не тільки розузгодження $\theta_0$ комп'ютерного годинника з ідеальним годинником у початковий момент, але і постійний та невідомий $\epsilon$-дрейф годинника. Модель була перевірена як достатно точна для багатьох типів годинників.
Якщо ми працюємо з мережею, де кожен вузел має свій номер, ми індексуватимемо зазначені величини. Наприклад, якщо в мережі два комп'ютери (комп'ютер 1 і комп'ютер 2), ми так запишемо моделі їх годинників:
$$
\begin{align}
\tau_1(t) = \theta_1 + \sigma_1\cdot t = \theta_1 + (1+\epsilon_1)\cdot t ,\\
\tau_2(t) = \theta_2 + \sigma_2\cdot t = \theta_2 + (1+\epsilon_2)\cdot t
\end{align} \tag{$𝜏_1,𝜏_2$|2}
$$
### [2.2.2 Модель неузгодженості двох годинників]()
Оскільки в більшості додатків на 7 рівні OSI немає API доступу до високоточних атомних годинників, абсолютну синхронізацію годинників необхідно замінити на відносну - один (або іноді декілька) годинників виступають як опорний (майстер-годинник), а решта синхронізує свої годинники щодо опорного годинника.
Тоді неузгодженість двох годинників, де перший годинник - опорний, можна записати як
$$
\begin{align}
\theta_{1,2}(t) = \tau_1(t) - \tau_2(t)
= (\theta_1 - \theta_2) + (\sigma_1-\sigma_2)t =\\
=(\theta_1 - \theta_2) + (\epsilon_1-\epsilon_2)t
=\theta_0 + \varepsilon t
\end{align} \tag{$θ_{12}$|3}
$$
де $\theta_0$ -початкова відносна неузгодженість, а $\varepsilon$ - дрейф другого годинника відносно до першого ($|\varepsilon|\ll 1$).
[](https://www.desmos.com/calculator/zjtvrrrdge)
- [ ] Чи є функції $\tau(t)$ і $\theta(t)$ монотонно зростаючими? Доведіть.
- [ ] Чи є показання реальних кварцових годинників та неузгодженість пари реальних кварцових годинників монотонними функціями? Обґрунтуйте.
- [ ] *Якщо ми знаємо $\tau_1(t)$, $\tau_2(t)$, $\theta$, $\varepsilon$, як дізнатися час атомного годинника?*
- [ ] *Якщо ми знаємо $\theta_1$, $\epsilon_1$, $\theta_2$, $\epsilon_2$, за якою формулою можна обчислювати залежність показань часу другого годинника від першого: $\tau_2(\tau_1)$?*
- [ ] *Запропонуйте процедуру (метод) визначення $\varepsilon$-дрейфу другого годинника відносно до першого*
## [2.3 Простий алгоритм синхронізації годинника](https://www.wikiwand.com/en/Network_Time_Protocol#:~:text=dim.%22%5B32%5D%5Bb%5D-,Clock%20synchronization%20algorithm,-Round%2Dtrip%20delay)
### [2.3.1 Простий протокол синхронізації годинника]()
У досить простих сценаріях узгодження часу можна знехтувати $\varepsilon$-дрейфом пар годинників і оцінювати тільки початкову відносну неузгодженність $\theta_0$ годинників .
- [ ] *Опишіть Ваші варіанти таких сценаріїв.*
Алгоритм (протокол) синхронізації годинникiв клієнта і сервера виконується в ході обміну короткими повідомленнями, що синхронізують і тестують стан каналу зв'язку.
**Мал.** Крок обміну повідомленнями між клієнтом та сервером в алгоритмі синхронізації
### [2.3.2 Початкова оцінка поточної неузгодженості](#Початкова-оцінка-поточної-неузгодженості)
Початкова оцінка $\tilde\theta_0 = T_0 - \tau_0$ поточної неузгодженості між часовими мітками клієнта та сервера:
$$
\tilde\theta_0= \frac{(T_1-\tau_0)+(T_2-\tau_3)}{2} \tag{$\tildeθ_0$|1}
$$
де
$\tau_0$ — часова помітка клієнта про передачу пакета запиту,
$T_1$ — часова помітка сервера прийому пакета запиту,
$T_2$ — часова помітка сервера передачі пакету у відповідь,
$\tau_3$ — часова помітка клієнта про прийом пакету у відповідь.
- [ ] *Що означають показання $T_0$, $\tau_1$, $\tau_2$, $T_3$ годинників ?*
Нехай $\Delta_\text{rtt}= \tau_3 - \tau_0$ - сліпа кругова затримка, а $\Delta_S=T_2-T_1$ - внутрішня затримка відповіді сервера. Кругова затримка $\Delta$, скоригована на внутрішню затримку відповіді сервера:
$$
\Delta= \Delta_\text{rtt} - \Delta_S = (\tau_3-\tau_0)-(T_2-T_1) \tag{$\Delta$|2}
$$
Щоб отримати вираз ($\tildeθ_0$|1) для початкової синхрокорекції $\tilde\theta_0$ між годинниками клієнта та сервера, необхідно розв'язати систему ($\tildeθ_0$|3), *припускаючи, що затримка сигналу від клієнта до сервера **дорівнює** затримці від сервера до клієнта*:
$$
\left\{
\begin{array}
\, \tau_0 +\tilde\theta_0 + \frac{1}{2}\Delta=T_1 \\
\, \tau_3 +\tilde\theta_0 - \frac{1}{2}\Delta=T_2 \tag{$\tildeθ_0$|3}
\end{array}
\right.
$$
- [ ] *Поясніть побудову системи лінійних рівнянь* ($\tildeθ_0$|3)
### [2.3.3 Уточнення параметру неузгодженості для каналів з асиметричними затримками]()
Часто припущення про симетричність затримок виявляється хибним. Тому для більш точної оцінки $\theta_0$ необхідно реалізувати схему уточнення на наступних кроках алгоритму синхронізації.
Для [каналів з асиметричними затримками](#огляд-асиметрії) можна переписати систему рівнянь ($\tildeθ_0$|3) як системи з обмеженням (θ,p|4):
$$
\left\{
\begin{array}
. \tau_0 +\theta_0+p\cdot\Delta=T_1 \\
\;\;\;\tau_3 +\theta_0-(1-p)\cdot\Delta=T_2 \\ \tag{θ,p|4}
0 < p < 1,
\end{array}
\right.
$$
де $p$ - параметр асиметрії (для симетричних затримок $p=1/2$)
- [ ] **Питання. Чому не можна розв'язати систему (θ,p|4) безпосередньо вiдносно до $\theta_0$ та $p$?**
### [2.3.4 Коефіцієнт асиметрії](#Коефіцієнт-асиметрії)
Якщо нам відомі пряма (*forward*) $\delta_f$ і зворотна (*backward*) $\delta_b$ затримки ($\Delta=\delta_f+\delta_b$), то коефіцієнт асиметрії $\xi_a$ визначається як
$$
\xi_a = { \delta_f \over \delta_b } \tag{$ξ_a$|5}
$$
Для симетричних затримок $\xi_a=1$.
- [ ] *В якому діапазоні може бути величина $\xi_a$?*
Маючи параметр $p$, коефіцієнт асиметрії затримок $\xi_a$ можна визначити як $$
\xi_a = { p \over 1-p } \tag{$ξ_a$|6}
$$
- [ ] *Як було отримано формулу $(ξ_a|6)$?*
*Уточнення величини асиметрії - це важке завдання, навіть із використанням односторонніх протоколів, таких, як [UDP](https://en.wikipedia.org/wiki/UserDatagramProtocol) і протоколів, заснованих на них, наприклад, [WebRTC](https://ru.wikipedia.org/wiki/WebRTC), якщо відсутні заздалегідь синхронізовані пари атомних годинників*
- [ ] **Завдання. Обґрунтувати цю тезу**
- [ ] *Доведіть, що помилка $|\partial\theta|=|\tilde\theta_0-\theta|$ визначення поточної неузгодженості за формулою ($\tildeθ_0$|1), якщо припущення про симетричність затримок виявилося хибним, не перевищує $\left|{\xi_a-1\over \xi_a +1}\right|{\Delta \over 2}$*
- [ ] *Якою може бути мінімальна помилка помилка $|\partial\theta|$ визначення поточної неузгодженості $\tilde\theta_0$ за формулою ($\tildeθ_0$|1), якщо припущення про симетричність затримок виявилося хибним, але нам відомий коефіцієнт асиметрії $\xi_a$? Доведіть!*
- [ ] *За якою формулою можна розрахувати помилку $|\partial\theta|=|\tilde\theta_0-\theta|$ визначення поточної неузгодженості $\theta_0$ годинників, якщо нам відомий параметр асиметрії $p$?*
- [ ] *За якою формулою можна розрахувати початкове неузгодження $\theta_0$
годинників, якщо нам відомий параметр асиметрії $p$ ?*
- [ ] *За якою формулою можна розрахувати початкове неузгодження $\theta_0$
годинників, якщо нам відомий коефіцієнт асиметрії $\xi_a$?*
### [2.3.5 Огляд асиметрії затримок для різних каналів зв’язку](https://poe.com/s/c9bvviHmLAsltDghNKn2)
Ось [огляд асиметрії затримок](#огляд-асиметрії) для різних каналів зв’язку, які використовуються протоколами TCP/IP,UDP, HTTP/2 і HTTP/3:
#### [Локальні мережі, побудовані на кабелях зi звитою парою]()
:::spoiler Оглядова інформація
Локальні мережі, побудовані на кабелях зi звитою парою, як і традиційний Ethernet, зазвичай демонструють дуже низьку асиметрію затримки. Деякі ключові причини цього:
Короткі кабелі: кабелі типу "звита пара", які використовуються для локальних мереж, зазвичай мають довжину лише десятки метрів. На цих коротких відстанях затримки прямого та зворотного поширення сигналу майже однакові, що призводить до мінімальної асиметрії. Оптоволоконні та бездротові мережі охоплюють набагато більші відстані, створюючи більше можливостей для накопичення асиметрії.
Проста інфраструктура: комутатори та маршрутизатори локальної мережі мають відносно просту конструкцію та створюють невелику затримку обробки. Вони не виконують таких складних функцій, як перекодування, шифрування або інкапсуляція, які можуть додати додаткову затримку в одному напрямку. Таким чином, асиметрія, спричинена обладнанням, низька.
Низька конкуренція: локальні мережі зазвичай мають надлишкову смугу пропускання та відчувають незначну конкуренцію чи перевантаження під час нормальної роботи. Таким чином, немає додаткових затримок у черзі або повторній передачі в одному напрямку проти іншого.
Відсутність накладних витрат на інкапсуляцію: протоколи локальної мережі, такі як Ethernet, не додають великих накладних витрат на інкапсуляцію з великою кількістю метаданих протоколу. Фреймування мінімальне, тому немає додаткової затримки під час аналізу чи генерації заголовків протоколу в одному напрямку.
Деякі виміряні значення або оцінки асиметрії затримки в локальних мережах, створених за допомогою Ethernet на звитій парі, включають:
• В межах однієї будівлі або поверху: по суті, відсутня вимірна асиметрія. Затримки прямого та зворотного ходу знаходяться в межах рівня шуму 1 мс або менше.
Асиметрія затримки $\approx 1$.
• На кількох поверхах будівлі: незначна додаткова асиметрія через трохи довші кабельні лінії та патч-панелі, можливо, до 5 мс.
Асиметрія затримки $\approx 1.1 ... 1.2$.
• У великому офісному містечку: додані незначні стрибки перемикання можуть додати додаткові 1-2 мс в одному напрямку для загальної затримки до 10 мс і коефіцієнта асиметрії 1.2-1.5.
:::
#### [Волоконно-оптичні канали]()
:::spoiler Оглядова інформація
Волоконно-оптичні канали зазвичай мають дуже низьку асиметрію затримки. Наприклад, трансконтинентальне оптоволоконне з’єднання в США може мати пряму затримку 10 мс і зворотну затримку 12 мс, що дає коефіцієнт асиметрії затримки $1.2$.
Основними причинами будь-якої асиметрії є оптимізація маршруту та затримки обробки обладнання. Загалом волокно має мінімальну асиметрію.
:::
#### [Бездротові канали]()
##### [WiFi]()
:::spoiler Оглядова інформація
Локальні мережі WiFi демонструють низьку асиметрію затримки, коли навантаження низькі, але вищу асиметрію під навантаженням через суперечки та повторні передачі. Виміряні коефіцієнти асиметрії затримки WiFi 1.5-2.5 є звичайними.
:::
##### [Мобільні мережі]()
:::spoiler Оглядова інформація
Мережі стільникового зв’язку зазвичай демонструють вищу асиметрію затримки, часто в 2 рази або більше. Виміряні коефіцієнти асиметрії в 3.0-5.0 не є рідкістю. Основними причинами є надмірна кількість передплачених радіоінтерфейсів, перекодування медіа та накладні витрати на інкапсуляцію.
:::
##### [Супутникові Інтернет-з’єднання]()
:::spoiler Оглядова інформація
Супутникові Інтернет-з’єднання сумно відомі дуже високою асиметрією затримки, часто в 10 разів або більше. Це пов’язано зі значно вищою затримкою висхідної лінії зв’язку для надсилання даних на супутник порівняно з низхідною лінією зв’язку. Повідомлялося про виміряні співвідношення 10.0-50.0 асиметрії. Велика затримка поширення 500 мс або більше домінує над будь-яким іншим фактором.
:::
#### Деякі приклади виміряних даних асиметрії затримки
* Локальні мережі, побудовані на кабелях зi звитою парою: в межах однієї будівлі або поверху затримки прямого та зворотного ходу знаходяться в межах рівня 1 мс або менше. Асиметрія затримки $\approx 1.0$
* Трансконтинентальне волокно США: 10 мс вперед / 12 мс назад;
Асиметрія затримки $\approx 0.83$
* Мережа WiFi при навантаженні 30%: 20 мс вперед / 32 мс назад;
Асиметрія затримки $\approx 0.63$
* Мобільна мережа LTE: 60 мс вперед / 180 мс назад;
Асиметрія затримки $\approx 0.33$
* Геостаціонарна супутникова лінія: 600 мс вперед / 3000 мс назад;
Асиметрія затримки $\approx 0.2$
:::danger
Таким чином, існують значні відмінності в асиметрії затримки між типами мереж. У локальних мережах на звитій парі практично відсутня асиметрія. Оптоволокно та Wi-Fi демонструють помірну асиметрію, мобільні мережі – середню асиметрію, а супутникові – надзвичайну асиметрію. Протоколи можуть певною мірою адаптуватися, але висока асиметрія неминуче впливає на продуктивність, особливо для програм, чутливих до затримки.
:::
### [2.3.6 Оцінки помилки неузгодженості між часовими помітками клієнта та сервера]()
**Твердження 1.** Помилка $\partial\theta=\tilde\theta_0-\theta$ визначення поточної неузгодженості годинників за формулою ($\tildeθ_0$|1) обмежена нерівністю:
$$
|\partial\theta|\le{1 \over 2}\left|{\xi_a-1\over \xi_a +1}\right|\Delta
\tag{$\partial\theta$|7}
$$
:::spoiler Розгляд
**Доказ.**
Припустимо, що ми маємо дві затримки: пряму $\delta_f$ і зворотну $\delta_b$.
Визначимо коефіцієнт асиметрії $\xi_a = \frac{\delta_f}{\delta_b}$.
Якщо вони симетричні, то $\delta_f = \delta_b = \frac{\Delta}{2}$, де $\Delta=\delta_f + \delta_b$ - це загальна затримка.
Якщо ми використовуємо формулу ($\tildeθ_0$|1) для оцінки $\tilde\theta_0$, то ми отримуємо
$$
\tilde\theta_0 = \frac{\Delta}{2} = \frac{\delta_f + \delta_b}{2}
$$
Ми можемо визначити $\delta_f = \xi_a \cdot \delta_b = \xi_a \cdot \frac{\Delta}{\xi_a + 1}$.
Тоді максимальна помилка буде $|\partial\theta|=|\tilde\theta_0-\theta| = \left|\frac{\Delta}{2} - \frac{\xi_a \cdot \Delta}{\xi_a + 1}\right| = \frac{1}{2}\left|\frac{\xi_a - 1}{\xi_a + 1}\right|\Delta$.
:::
Наприклад, якщо для волоконно-оптичних каналів виміряний коефіцієнт асиметрії ξ=0.9 і ми синхронізуємо годинник у протилежних точках земної кулі з круговою затримкою розповсюдження сигналу Δ=200 мілісекунд, можна поліпшити песимістичну похибку синхронізації, рівну 100 мілісекундам, до приблизно 5 мілісекунд.
**Твердження 2.** Cкоригована помилка $\partial\theta'= \hat\theta_0-\theta$ визначення поточної неузгодженості $\hat\theta_0$ за формулою $\hat\theta_0 = \frac{\xi_a\cdot \Delta}{\xi_a + 1}$ дорівнює 0.
:::spoiler Розгляд
Якщо нам відомий коефіцієнт асиметрії $\xi_a$, то ми можемо скоригувати нашу оцінку $\hat\theta_0$ так, щоб врахувати асиметрію. Замість використання в формулі ($\tildeθ_0$|3) виразу $\frac{\Delta}{2}$, ми можемо використати формулу $\frac{\xi_a \cdot \Delta}{\xi_a + 1}$, яка враховує асиметрію.
Тоді скоригована помилка буде $|\partial\theta|'=|\hat\theta_0-\theta| = \left|\frac{\xi_a \cdot \Delta}{\xi_a + 1} - \frac{\xi_a \cdot \Delta}{\xi_a + 1}\right| = 0$.
:::
Таким чином, якщо існує можливість отримання явної інформації про асиметрію каналу або її неявного обчислення по геоданим вузлів, гістограм затримок, встановленого точного обладнання та можливими системами машинного навчання за цими даними, можна виконувати синхронізацію годинників в глобальних мережах з субмілісекундною точністю.
Ще більш радикальним кроком у цьому напрямі є вдосконалення протоколів та обладнання маршрутизації в мережі інтернет, таке, що у кожному пакеті передачі даних має існувати поле часу передачі пакета, інформація у якому оновлюється від вузла до вузла. При цьому кожна лінія зв'язку повинна мати точну характеристику часу передачі його медіа, і ця інформація повинна бути доступна маршрутизаторам.
### [2.3.7 Спрощений варіант алгоритму синхронізації годинників](https://ua.wikipedia.org/wiki/SNTP)
Для мережних розподілених додатків, наприклад, комп'ютерних ігор, часто потрібний простий метод синхронізації годинника. В ідеалі він повинен мати такі властивості: бути досить точним, швидко сходитися, бути простим у реалізації і здатним працювати на протоколах з підтвердженням доставки, таких як TCP або WebSockets.
#### [2.3.7.1 Варіант алгоритму, схожий на SNTP]()
Спрощений варіант алгоритму (схожий на [SNTP](https://ua.wikipedia.org/wiki/SNTP)) з цими властивостями виглядає так:
:::info
1) Клієнт відзначає свій місцевий час $\tau_0$ у пакеті «запит часу» та відправляє на сервер
2) Після отримання повідомлення від клієнта сервер відзначає свій локальний час $T_1$ і повертає його клієнту (вважається, що сервер настільки швидко працює, що $T_1-T_2=0$)
3) Після отримання клієнтом повідомлення з часом $T_1$ він віднімає свій відправлений час $\tau_0$ з поточного часу $\tau_3$ і ділить на два, щоб обчислити коригувальний параметр $\Delta/2$ (знову ми вважаємо, що сервер настільки швидко працює, що $\Delta=\Delta_\text{rtt}=\tau_3-\tau_0$).
Далі клієнт віднімає поточний час $\tau_3$ вiд часу сервера $T_1$ (або $T_1$ вiд $\tau_0$), щоб визначити "сліпу" коррекцію часу клієнта та сервера, і додає до неї половинну затримку $\Delta/2$, щоб отримати оцінку неузгодженості $\tilde\theta_0$.
"Сліпу" коррекцію часу клієнта та сервера можна негайно використовувати для початкової роботи з годинником, оскільки вона коригує показання локального годинника принаймні у правильне приблизне положення (хоча б у правильний часовий пояс, якщо між годинниками є великі розбіжності!)
Клієнт повторює кроки з 1-го по 3-й п'ять або більше разів, щоразу роблячи паузу в кілька секунд. Інший трафік може бути дозволений на якийсь час, але його слід звести до мінімуму для досягнення найкращих результатів.
4. Результати отримання пакетів накопичуються та сортуються за значеннями затримок. Середня затримка визначається шляхом вибору середньої точки (медіани) із цього впорядкованого списку.
Всі пакети вище приблизно 1 стандартного відхилення від медіани відкидаються, а пакети, що залишилися, усереднюються з використанням середнього арифметичного (як один з варіантів) для отримання поточного усередненого значення неузгодженості годинників (параметра синхронізації) $\overline\theta_0$ .
:::
#### [2.3.7.2 Модифікації алгоритму, враховуючи ймовірнісний розподіл затримок]()
>Можна модифікувати описаний алгоритм, враховуючи ймовірнісний розподіл затримок, що сильно відрізняється від [Гаусiвського](https://en.wikipedia.org/wiki/Normal_distribution). Можна, наприклад, спробувати використати [зміщений розподіл Пуассона](https://en.wikipedia.org/wiki/Displaced_Poisson_distribution) aбo [зміщений eкспоненційний розподіл](https://pssc.org.ph/wp-content/pssc-archives/The%20Philippine%20Statistician/1998/07_Estimation%20of%20Parameters%20of%20the%20Displaced%20Exponential%20Distribution.pdf). Зокрема, протягом десятків секунд з великою ймовірністю можна отримати строгий мінімум часу затримки. Замість середньоарифметичного як оцінку поточного усередненого параметра синхронізації $\theta$ можна використовувати оцінку мінімума, а також моду та інші.
Приклад гістограми розподілу $\Delta_\text{rtt}$ при зв'язку з віддаленим сервером.
Гістограма є реалізацією деякого випадкового процесу, який визначається поточною структурою каналу та роботою на ньому маршрутизаторів, повторювачів, буферів тощо, та її форма визначається щільністю розподілу цього випадкового процесу. Вісь $х$ - це час затримки в мілісекундах, вісь $y$ - відсоткове співвідношення відповідних затримок.
Ці ілюстративні дані допоможуть у виборі відповідного закону розподілу затримок $\Delta_\text{rtt}$ поширення сигналу каналом зв'язку та залежного від них розподілу параметра синхронізації $\theta_0$
- [ ] *Подумайте, чому не можна використовувати максимальну затримку як оцінку $\Delta_\text{rtt}$ ?*
Можна також отримати оцінки $p$ (або $\xi_a$) асиметрії затримок, якщо надсилати послідовність запитів із заздалегідь відомими відмітками часу, якщо якимсь чином вдалось синхронізувати годинники клиєнта та сервера.
### [2.3.8 Приклад програми](https://replit.com/join/lgkmtvrxut-arthmax)
## [2.4 Библиотека timesync](https://npm.runkit.com/timesync)
Бібліотека timesync реалізує простий, але швидкий і досить точний (вважаючи канал симетричним) метод уточнення параметра синхронізації для розподілених клієнт-серверних програм реального часу.
Приклад серверного коду підключення бібліотеки та обробника запиту на синхронізацію:
* server.js
```js=
var express = require('express');
var timesyncServer = require('timesync/server');
// create an express app
var port = 8081;
var app = express();
app.listen(port);
console.log('Server listening at http://localhost:' + port);
// serve static index.html -------------------------
app.get('/', express.static(__dirname));
// handle timesync requests -------------------------
app.use('/timesync', timesyncServer.requestHandler);
```
Приклад клієнтського коду підключення бібліотеки та запитів на синхронізацію та час:
* client HTML
```htmlembedded=
<script src="/timesync/timesync.js"></script>
<div id=Info></div>
```
* client javascript
```json=
// create a timesync instance
var ts = timesync.create({
server: '/timesync',
interval: 10000
});
// get notified on changes in the offset ---------------
ts.on('change', function (offset) {
Info.innerHTML += 'offset: ' + offset + ' ms<br>');
});
// get synchronized time
setInterval(function () {
let now = new Date(ts.now());
Info.innerHTML +='now: ' + now.toISOString() + ' ms<br>');
}, 1000);
```
#### [Приклад використання tymesync](https://replit.com/join/wevfzaxnbz-arthmax)
# [3. Часова координації подій ]()
## [3.1 Типі програм у реальному часі, які потребують синхронізованої координації]().
Навіть точне розв'язання задачі синхронізації годинників у вузлах мережі не вирішує завдання **синхронізованої координації роботи** розподілених додатків реального часу. Ось кілька прикладів типів програм у реальному часі, які потребують синхронізованої координації.
### [3.1.1 Розподілені системи управління](https://en.wikipedia.org/wiki/Distributed_control_system)
<img src=https://hackmd.io/_uploads/H1D7EDW7A.png width=500>
Розподілені системи управління у промисловій автоматизації та системах управління. Приклади включають системи керування електростанціями, виробничі складальні лінії та системи керування рухом. Синхронізована координація забезпечує спільну дію різних компонентів системи в потрібний час, запобігаючи конфліктам і забезпечуючи безперебійну роботу.
### [3.1.2 Спільне редагування в режимі реального часу](https://en.wikipedia.org/wiki/Collaborative_real-time_editor):
<img src=https://hackmd.io/_uploads/BkEcSP-mC.png width=500>
Спільне редагування в режимі реального часу: програми, які дозволяють кільком користувачам спільно редагувати документ або працювати над проектом у режимі реального часу, вимагають синхронізованої координації. Приклади включають платформи для спільної розробки програмного забезпечення. Механізми синхронізації гарантують, що зміни, внесені різними користувачами, застосовуються в правильному порядку та є видимими для всіх учасників у режимі реального часу.
### [3.1.3 Розподілені мультимедійні системи](https://www.geeksforgeeks.org/distributed-multimedia-systems/)
<img src=https://hackmd.io/_uploads/H1yGqPWXC.png width=500>
Розподілені мультимедійні системи, такі як відеоконференції та потокові послуги, потребують синхронізованої координації для доставки медіа-потоків в режимі реального часу та забезпечення безперебійної взаємодії з користувачем. Те ж саме стосується і розподіленої симуляції та віртуальних середовищ, які вимагають синхронізації для координації дій та взаємодії об'єктів на всіх вузлах.
### [3.1.4 Розподілені системи фінансової торгівлі](https://medium.com/prooftrading/building-a-high-performance-trading-system-in-the-cloud-341db21be100):
<img src=https://hackmd.io/_uploads/HkBInPZXA.png width=500>
Розподілені системи фінансової торгівлі: системи високочастотної торгівлі та фінансові ринки, які включають кількох розподілених учасників, вимагають синхронізованої координації. У цих системах точність координації дій у часі має вирішальне значення для здійснення угод, узгодження замовлень і підтримки чесних та ефективних ринків.
## [3.2 Координація майбутніх подій в мережевій системі]()
Для вирішення вирішення завданнь координації роботи розподілених додатків реального часу можна використовувати прикладні протоколи взаємодії компонентів розподілених додатків, подібні до базових протоколів синхронізації часу, для **координації майбутніх подій** в мережевій системі. Незважаючи на неможливість точної синхронізації годинників, є можливість **точної координації майбутніх подій** в частинах розподілених додатків для детермінованих каналів зв’язку. Для каналів зв’язку з недетерминованими затримками потрібна розробка ймовірнісних протоколів кратного узгодження у часі дій.
# [Завдання на лабораторну роботу 3]()
:::info
Протестувати та продемонструвати результати оцінки випадкових величин для браузерної сторони додатку, що запускається:
а) на комп’ютері, пов’язаному провідним зв’язком з мережею інтернет;
б) на комп’ютері, пов’язаному WiFi-зв’язком з мережею інтернет;
в) на мобільному пристрої, пов’язаному з мережею інтернет через мобільні (стільникові) канали;
Самостійно вибрати передбачуваний Вами закон розподілу випадкової величини з набору:
а) [Гаусовий розподіл](https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5)
б) [Зміщений розподіл Пуассона](https://en.wikipedia.org/wiki/Displaced_Poisson_distribution)
в) [Зміщений експоненційний розподіл](https://pssc.org.ph/wp-content/pssc-archives/The%20Philippine%20Statistician/1998/07_Estimation%20of%20Parameters%20of%20the%20Displaced%20Exponential%20Distribution.pdf)
Для обраного розподілу за даними роботи клієнт-серверної програми отримати оцінки випадкової величини :
* min *- мінімум*
* $q_{1/4}$ *- перший (або нижній) квартiль*
* $q_{2/4}=q_{1/2}=$ med *- медіана або другий квартiль*
* avg *- середнє арифметичне*
* mode *- мода*
* $q_{3/4}$ *- третій (або верхній) квартiль*
* max *- максимум*
* stddev *- стандартне відхилення*
* $I_q = q_{3/4} - q_{1/4}$ *- інтерквартiльний розмах*
:::
## [Варіант 1. Спрощена синхронізація годинника клієнта та годинника сервера]()
Створити на хостингу glitch.com (replit.com) клієнт-серверний додаток, що, використовуючи протокол HTTP, виконує синхронізацію годинника клієнта та годинника сервера ([обчислення поправки](#Початкова-оцінка-поточної-неузгодженості) $\theta_0$) та online порівняння її з роботою бібліотеки [tymesync](https://npm.runkit.com/timesync), приймаючи гіпотезу симетричності каналу. Дайте оцінку похибки методу визначення початкової синхрокорекції $\theta_0$.
## [Варіант 2. Синхронізація годинників клієнтів]()
Напишіть серверно-клієнтський додаток, що, використовуючи протокол HTTP, виконує синхронізацію годинника клієнта 2 з клієнтом 1 як майстер-годинником, приймаючи гіпотезу симетричності каналів. Дайте оцінку похибки методу визначення початкової синхрокорекції $\theta_0$.
:::info
## Таблиця результатів
Подати отримані результати в таблиці:
| Тип каналу та величини | min | $q_{1/4}$ | med | avg| mode|$q_{3/4}$ |max|stddev| $I_q$|
| -------- | ----| -------- | --- | ---| --- |----------|---| ---- | ---- |
| wired $\theta$ | | |
| wifi $\theta$ | | |
| mobile $\theta$ | | |
| wired $\xi_a$ | | |
| wifi $\xi_a$ | | |
| mobile $\xi_a$ | | |
:::
# Ресурси
1. [Synchronization](https://en.wikipedia.org/wiki/Synchronization_(computer_science))
3. [Clock synchronization](https://en.wikipedia.org/wiki/Clock_synchronization)
4. [Poincaré-Einstein synchronisation ](https://en.wikipedia.org/wiki/Einstein_synchronisation)
5. [Cristian's algorithm](https://en.wikipedia.org/wiki/Cristian%27s_algorithm)
6. [Berkeley_algorithm](https://en.wikipedia.org/wiki/Berkeley_algorithm)
7. [Network Time Protocol](https://www.wikiwand.com/en/Network_Time_Protocol)
8. [A Stream-based Time Synchronization Technique For Networked Computer Games](https://web.archive.org/web/20160310125700/http://mine-control.com/zack/timesync/timesync.html)
9. [SNTP](https://ru.wikipedia.org/wiki/SNTP)
10. [Building blocks of UDP](https://hpbn.co/building-blocks-of-udp/)
11. [WebRTC](https://hpbn.co/webrtc/)
12. [Probabilistic clock synchronization](https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/Cristian.pdf)
13. [Tannenbaum. Distributed Systems Principles and Paradigms](https://vowi.fsinf.at/images/b/bc/TU_Wien-Verteilte_Systeme_VO_%28G%C3%B6schka%29_-_Tannenbaum-distributed_systems_principles_and_paradigms_2nd_edition.pdf)
14. [clock-synchronization-and-monotonic-clocks](https://inelpandzic.com/articles/clock-synchronization-and-monotonic-clocks/)
14. [Delay Asymmetry Correction Model](https://curve.carleton.ca/system/files/etd/74f0b075-d19e-4255-bcc3-b297e876783e/etd_pdf/561dc5d8c3aa529b23a94b5e40fa9845/rahman-delayasymmetrycorrectionmodelforieee1588synchronization.pdf)
15. [Network Simulator](https://www.nsnam.org/)
15. [timesync](https://github.com/enmasseio/timesync/tree/49b1131c47f4387518fe295b148906d88b99eb7d)
16. [Put An Atomic Clock in Your PC - Open Source Time Card](https://youtu.be/YKApDtJjXU4)
17. [Build a Stratum 1 Time Server Using a Raspberry Pi Pico](https://youtu.be/pyVCHX4H7bM)
18. [unichron API](https://www.clockwork.io/unichron/)
19. [ngrok.com](https://ngrok.com/)
20. [Exponential_smoothing](https://en.wikipedia.org/wiki/Exponential_smoothing)
21. [Сучасний підручник з JavaScript](https://uk.javascript.info/)
22. [Дата і час](https://uk.javascript.info/date)
23. [Distributed Systems: Synchronisation in Complex Systems](https://blog.sofwancoder.com/distributed-systems-synchronisation-in-complex-systems)
# [Поради та застосування AI](https://poe.com/)
1) [chatGPT](https://poe.com/s/EwdNcFeYbIGy4npfaDXV)
2) [GPT4](https://poe.com/s/mFyy2U3fFlMGu3h6xYmN)
3) [Claud++](https://poe.com/s/c9bvviHmLAsltDghNKn2)
Sign in with Wallet
Connect another wallet