# 2024_: Комп'ютерні системи і мережі. Контрольна робота. [Прізвище, ім'я та по батькові]().
[TOC]

# [Тема. Синхронізація часу](https://hackmd.io/-JThi2LTTLGPRElx4eQQew#mjx-eqn%3A%CE%BE_a.2:~:text=%D0%BD%D0%B0%20%D1%86%D1%8C%D0%BE%D0%BC%D1%83%20%D1%82%D0%B0%D0%B9%D0%BC%D0%B5%D1%80%D1%96%3F-,%D0%A3%D0%B7%D0%B3%D0%BE%D0%B4%D0%B6%D0%B5%D0%BD%D0%BD%D1%8F%20%D1%87%D0%B0%D1%81%D1%83,Edit%20from%20here,-2%20%D0%A1%D0%B8%D0%BD%D1%85%D1%80%D0%BE%D0%BD%D1%96%D0%B7%D0%B0%D1%86%D1%96%D1%8F%20%D1%87%D0%B0%D1%81%D1%83)

:::info

Для виконання контрольної роботи Ви повинні скопіювати текст завдання (у форматі md ) та створити, використовуючи цей текст, на хостингу hack.md лист контрольної роботи із зазначенням Вашого прізвища, імені та по батькові.

Відразу після закінчення контрольної роботи ви маєте надіслати посилання на опублікований лист з розв'язаннями. Лист повинен бути опублікований з правами читання та правки **signed-in users**.
Остаточну оцінку буде поставлено після співбесіди у вибраних питаннях на знання записаних на Вашому листі контрольної роботи відповідей.
:::

## [Афінні моделі комп'ютерних годинників та неузгодженості](https://hackmd.io/-JThi2LTTLGPRElx4eQQew#mjx-eqn%3A%CE%BE_a.2:~:text=%D0%B2%D0%B0%D1%80%D1%82%D1%96%D1%81%D1%82%D1%8C%20%D0%B0%D1%82%D0%BE%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%20%D0%B3%D0%BE%D0%B4%D0%B8%D0%BD%D0%BD%D0%B8%D0%BA%D0%B0%3F-,2.2%20%D0%90%D1%84%D1%96%D0%BD%D0%BD%D1%96%20%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%96%20%D0%BA%D0%BE%D0%BC%D0%BF%27%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%B8%D1%85%20%D0%B3%D0%BE%D0%B4%D0%B8%D0%BD%D0%BD%D0%B8%D0%BA%D1%96%D0%B2%20%D1%82%D0%B0%20%D0%BD%D0%B5%D1%83%D0%B7%D0%B3%D0%BE%D0%B4%D0%B6%D0%B5%D0%BD%D0%BE%D1%81%D1%82%D1%96,Edit%20from%20here,-2.2.1%20%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%B0%20%D0%B0%D1%84%D1%96%D0%BD%D0%BD%D0%B0)

$$
\tau(t) = \theta_0 + \sigma\cdot t = \theta_0 + (1+\epsilon)\cdot t \tag{𝜏|1}
$$
де
$\theta_0$ - розузгодження комп'ютерного годинника з ідеальним годинником у початковий момент,
$\sigma \approx 1$ - швидкість ходу комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту,
$|\epsilon| \ll 1$- дрейф (відхилення швидкості) комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту.
$$
\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}
$$
$$
\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$).
- [ ] *Чи є функції $\tau(t)$ і $\theta_{1,2}(t)$ монотонно зростаючими? Доведіть.*
---
---
---
---
- [ ] *Чи є показання реальних кварцових годинників та неузгодженість пари реальних кварцових годинників монотонними функціями? Обґрунтуйте.*
---
---
---
---
- [ ] *Якщо ми знаємо $\tau_1(t)$, $\tau_2(t)$, $\theta$, $\varepsilon$, як дізнатися час атомного годинника?*
---
---
---
---
- [ ] *Якщо ми знаємо $\theta_1$, $\epsilon_1$, $\theta_2$, $\epsilon_2$, за якою формулою можна обчислювати залежність показань часу другого годинника від першого: $\tau_2(\tau_1)$?*
---
---
---
---
- [ ] *Запропонуйте процедуру (метод) визначення $\varepsilon$-дрейфу другого годинника відносно до першого*
---
---
---
---

## [Простий протокол синхронізації годинника](https://hackmd.io/-JThi2LTTLGPRElx4eQQew#mjx-eqn%3A%CE%BE_a.2:~:text=%D0%BF%D1%80%D0%BE%D1%82%D0%BE%D0%BA%D0%BE%D0%BB%20%D1%81%D0%B8%D0%BD%D1%85%D1%80%D0%BE%D0%BD%D1%96%D0%B7%D0%B0%D1%86%D1%96%D1%97%20%D0%B3%D0%BE%D0%B4%D0%B8%D0%BD%D0%BD%D0%B8%D0%BA%D0%B0-,%D0%A3%20%D0%B4%D0%BE%D1%81%D0%B8%D1%82%D1%8C%20%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%B8%D1%85%20%D1%81%D1%86%D0%B5%D0%BD%D0%B0%D1%80%D1%96%D1%8F%D1%85%20%D1%83%D0%B7%D0%B3%D0%BE%D0%B4%D0%B6%D0%B5%D0%BD%D0%BD%D1%8F%20%D1%87%D0%B0%D1%81%D1%83%20%D0%BC%D0%BE%D0%B6%D0%BD%D0%B0%20%D0%B7%D0%BD%D0%B5%D1%85%D1%82%D1%83%D0%B2%D0%B0%D1%82%D0%B8,%D0%B3%D0%BE%D0%B4%D0%B8%D0%BD%D0%BD%D0%B8%D0%BA%D1%96%D0%B2%20.,-Comment)

У досить простих сценаріях узгодження часу можна знехтувати $\varepsilon$-дрейфом пар годинників і оцінювати тільки початкову відносну неузгодженість $\theta_0$ годинників .

- [ ] *Опишіть Ваші варіанти таких сценаріїв.*
---
---
---
---
## [Початкова оцінка поточної неузгодженості](#Початкова-оцінка-поточної-неузгодженості)
Початкова оцінка $\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$ годинників ?*
---
---
---
---

$$
\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)
---
---
---
---

Для [каналів з асиметричними затримками](#огляд-асиметрії) можна переписати систему рівнянь ($\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$?*

---
---
---
---

### [Коефіцієнт асиметрії](#Коефіцієнт-асиметрії)
Якщо нам відомі пряма (*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), якщо припущення про симетричність затримок виявилося хибним, не перевищує ${1 \over 2}\left|{\xi_a-1\over \xi_a +1}\right|\Delta$*
---
---
---
---
- [ ] *Якою може бути мінімальна помилка $|\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$?*
---
---
---
---

## [Практичне завдання](replit.com)

Розглянемо мережну програму, в якій два клієнти (js програми всередині браузерів), що знаходяться, можливо, дуже далеко один від одного і від сервера, обмінюються своїм поточним часом, використовуючи тільки HTTP GET fetch() на боці браузерів.

- [ ] Варіант 1. *Опишіть механізм і напишіть фрагменти коду на клієнтах і сервері, відповідальних за якомога більш своєчасну передачу свого часу першим клієнтом, що підключився, - другому за запитом другого клієнта. Які основні проблеми, пов'язані з використаним протоколом, Вам необхідно вирішити для виконання завдання?*
---
---
---
---

- [ ] Варіант 2. *Опишіть механізм і напишіть фрагменти коду на клієнтах і сервері, що відповідають якомога більш своєчасну передачу свого часу другим клієнтом, що підключився, - першому. Які основні проблеми, пов'язані з використаним протоколом, Вам необхідно вирішити для виконання завдання?*
---
---
---
---

* server.js

var express = require('express');
...
...
...

* client1 HTML

   <div id=Info></div>
   ....
   ....
   ....

* client1 javascript

 ...
 ...
 // get time
 setInterval(function () {
                          ....
                          ....
                          }, 100);
...                          

* client2 HTML

   <div id=Info></div>
   ....
   ....
   ....

* client2 javascript

 ...
 ...
 // req time
 ...                          
 ...

### [Вибір варіанта практичного завдання]()

Вибрати варіант за формулою
$$v = 1 + (d\mod 2),$$
де d – ваш день народження.

Якщо ви встигли запрограмувати Ваше рішення, треба надати посилання на invite Вашого проекту

# [Інформаційні матеріали]()

[2024: Комп'ютерні системи і мережі. 3. Узгодження стану. Синхронізація часу](https://hackmd.io/@ArthMax/CSNTimeSync)