---
# System prepended metadata

title: ArticleFormulas

---

[TOC]
## 1. Помилки оцінки неузгодженості  між часовими помітками клієнта та сервера

Для зручності для простих мережевих систем, наприклад, що складаються з двох вузлів і одного каналу зв'язку (загалом асиметричного) ми будемо позначати опорний вузол для синхронізації як сервер, а вузол, що синхронізується до сервера як клієнт. Таку саму термінологію ми використовуватимемо і для топології зв'язку типу "зірка". При цьому годинникові позначки сервера, що визначаються по годинниках сервера, ми будемо позначати латинськими літерами, а годинникові позначки клієнта, що визначаються годинами клієнта, ми позначатимемо малими грецькими літерами.

Початкова оцінка $\tilde\theta_0 = T_0 - \tau_0$ поточної неузгодженості  між часовими помітками клієнта та сервера в системі без дрейфу годинників [2]:
$$
  \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$ — часова помітка клієнта про прийом пакету у відповідь. 
Ці показання годинників використовуються для розрахунку $\tilde\theta_0$ та визначення неузгодженості між часовими системами.
Нехай $\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\theta_0 = (T_1-\Delta/2) - \tau_0$. 

Щоб отримати вираз ($\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.
$$

Припустимо, що ми маємо дві затримки: пряму $\delta_f$ і зворотну $\delta_b$. Якщо ми припускаємо, що вони симетричні, то ми припускаємо, що $\delta_f = \delta_b = \frac{\Delta}{2}$, де $\Delta$ - це загальна затримка. 
Але в реальності ці затримки можуть бути асиметричними. Тоді ми можемо визначити коефіцієнт асиметрії $\xi_a = \frac{\delta_f}{\delta_b}$, який в  лежить в межах $(0,\infty)$, а в симетричних каналах дорівнює 1. 

**Тверження 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$|4}
$$

**Доказ.**
Розглянемо компоненти помилки $|\partial\theta|=|\tilde\theta_0-\theta|$. Якщо ми використовуємо формулу ($\tildeθ_0$|1) для оцінки $\tilde\theta_0$, то ми отримуємо $\tilde\theta_0 = \frac{\Delta}{2} = \frac{\delta_f + \delta_b}{2}$.  Але якщо затримки асиметричні, то реальне значення $\theta$ буде відрізнятися. Ми можемо визначити $\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$.


**Тверження 2.** Верхня межа оцінки ($\partial\theta$|4) помилки $\partial\theta$ є точною та фіксуючою. Тобто
$$
\partial\theta = {\xi_a-1\over \xi_a +1}{\Delta \over 2}
\tag{$\partial\theta$|5}
$$


 Якщо припущення про симетричність затримок виявилося хибним, але нам відомий коефіцієнт асиметрії $\xi_a$, скоригована помилка $\partial\theta'=\tilde\theta_0'-\theta=(\tilde\theta_0+\partial\theta)-\theta$ визначення поточної неузгодженості $\tilde\theta_0$ за формулою ($\tildeθ_0$|1),  дорівнює 0.

**Доказ.**
Якщо нам відомий коефіцієнт $\xi_a$, то ми можемо скоригувати нашу оцінку $\tilde\theta_0$ так, щоб врахувати асиметрію. Замість використання в системі ($\tildeθ_0$|3) виразу $\frac{\Delta}{2}$, ми можемо використати формулу $\frac{\xi_a \cdot \Delta}{\xi_a + 1}$, яка враховує асиметрію. 

Тоді скоригована помилка буде $|\partial\theta|'=|\tilde\theta_0'-\theta| = \left|\frac{\xi_a \cdot \Delta}{\xi_a + 1} - \frac{\xi_a \cdot \Delta}{\xi_a + 1}\right| = 0$.

Отже, якщо нам відомий коефіцієнт асиметрії $\xi_a$, то скоригована помилка визначення поточної неузгодженості $\tilde\theta_0$ за формулою ($\tildeθ_0$|1) буде рівна нулю, незалежно від того, чи виявилося припущення про симетричність затримок хибним. Це доводить, що знання  $\xi_a$ дозволяє нам точно визначити поточну неузгодженість мережевих годинників, навіть якщо затримки асиметричні.


## 2. Інтервали оцінки неузгодженості  між часовими помітками клієнтів та сервера

### 2.1 Інтервал невизначеності 

Якщо для інформаційного каналу нам відомі межі вимірювань коефіцієнта асиметрії $[\xi_\min, \xi_\max]$, то ми отримуємо інтервал невизначеності для оцінки $\tilde\theta_0 = T_0 - \tau_0$ поточної неузгодженості  між часовими помітками клієнта та сервера:

$$
 \left[\tilde\theta_\min,\tilde\theta_\max\right] = 
    \left[
     \tilde\theta_0 +    \partial\theta_\min,
     \tilde\theta_0 + \partial\theta_\max,
    \right]
    =
    \left[
    \tilde\theta_0 +{\xi_\min-1\over \xi_\min +1}{\Delta \over 2},
    \tilde\theta_0 +{\xi_\max-1\over \xi_\max +1}{\Delta \over 2}
    \right]
$$
Легко показати, що $\tilde\theta_\min<\tilde\theta_\max$ . Насправді розглянемо  $\partial\theta$ як функцію від $\xi$ при $\Delta$ розглядаємому як параметр. Оскільки  функція $\partial\theta_\Delta(\xi)={\xi-1\over \xi +1}{\Delta \over 2}$ є монотонно зростаючою на інтервалі $[0,\infty]$, то і функція $\tilde\theta(\xi)=\tilde\theta_0 + \partial\theta_\Delta(\xi)$ також є монотонно-зростаючою функцією, тобто  $\tilde\theta(\xi_\min)<\tilde\theta(\xi_\max)$, оскільки $\xi_\min<\xi_\max$ . І отже $\tilde\theta_\min<\tilde\theta_\max$ .

### 2.2 Умови уточнення інтервалів параметрів синхронізації

Якщо ми розглядаємо пов'язану інформаційну мережеву систему з кількістю вузлів більшим 2 і фізична топологія, що лежить в основі побудови каналів зв'язку цієї системи, містить незалежні канали (або частини каналів) між усіма парами вузлів цієї системи, у нас з'являється можливість уточнення інтервалів параметрів синхронізації між клієнтами та сервером, тобто зменшення інтервалів невизначеності $\left[\tilde\theta_\min,\tilde\theta_\max\right]_i$ $i$-го клієнта з сервером.
Для цього слід між клієнтами $i$ та $j$ встановити безпосереднє з'єднання (у сучасному інтернеті це нетривіальне завдання, але одним із варіантів є з'єднання за протоколом WebRTC), вибрати одного з цих клієнтів, наприклад $i$, тимчасовим сервером і виконати процедуру синхронізації годинників між ними з визначенням інтервалу $\left[\tilde\theta_\min,\tilde\theta_\max\right]_{ij}$ невизначеності для оцінки $\tilde\theta_{ij} = \tau_i - \tau_j$ поточної неузгодженості  між часовими помітками клієнта $i$ та клієнта $j$. В ідеальній узгодженій системі з трьох вузлів - сервера, клієнта $i$, клієнта $j$, має виконуватися рівність:
$$
 \tilde\theta_{0,i}+\tilde\theta_{i,j} = \tilde\theta_{0,j},
$$
де $\tilde\theta_{0,i}, \tilde\theta_{i,j}, \tilde\theta_{0,j}$ - це оцінки  поточної неузгодженості  між часовими помітками сервера з клієнтом $i$,  клієнта $i$ з клієнтом $j$, та сервера з клієнтом $j$ відповідно.

### 2.3 Методи узгодження інтервалів.

Однак ми маємо замість точних оцінок інтервали і тому маємо виконати узгодження інтервалів. Це можна зробити багатьма способами, адекватність яких потребує подальших досліджень. У нашій роботі ми коротко окреслимо два способи.

#### 2.3.1 Узгодження інтервалів за допомогою використання інтервальної арифметики.
Першим кроком у цьому підході буде отримання суми інтервалів. 
Розглянемо інтервали $[a,b]$ та $[c,d]$. Тоді їхньою сумою згідно [4] буде 
$[a,b]+[c,d] = [a+c,b+d]$.  А потім ми уточнюємо інтервал $[e,f]$ з отриманим сумарним інтервалом  $[a+c,b+d]$ за формулою  

$$ [e',f']=[\max(a+c,e), \min(b+d),f]$$

#### 2.3.2 Узгодження інтервалів за допомогою методів нечітких множин.
У цьому підході на інтервалах визначаються нечіткі множини і, крім самих інтервалів, слід задати функції приналежності до нечітких множин (наприклад, трикутну функцію приналежності), функції узгодження інтервалів (наприклад, мінімум) та методу нормалізації нечітких множин.


## 3. Точна координація роботи розподілених додатків реального часу

Однак, навіть точне розв'язання задачі синхронізації годинників у вузлах мережі не вирішує завдання координації роботи розподілених додатків реального часу. Ми стверджуємо, що, незважаючи на неможливість точної синхронізації годинників без знання коефіцієнта асиметрії $\xi_a$, є можливість **точної координації майбутніх подій** в частинах розподілених додатків для детермінованих каналів зв’язку. 



Для каналів зв’язку з недетерминованими затримками потрібна розробка ймовірнісних протоколів кратного узгодження у часі дій.

