---
# System prepended metadata

title: '2022: Компьютерные системы и сети. Лекция 7.'
tags: [Old, CSN, Lecture]

---

# 2022: Компьютерные системы и сети. Лекция 7.   
[TOC]
# Согласование состояния распределенной системы

## [Диаграммы визуализации графиков Vis.graph2d](https://visjs.github.io/vis-timeline/examples/graph2d/)
  ![](https://i.imgur.com/pm19EAL.png)


 ### [Пример простейшей диаграммы](https://visjs.github.io/vis-timeline/examples/graph2d-generated/codepen.09e7f1d995f6f20c3d4272892981b24757b039f3bf6eb3f212bf3a65bdb06215.html)  
 
 ![](https://i.imgur.com/6wEt0ZJ.png)

### Пример кода для создания простейшей статической диаграммы
 * HTML 
```htmlmixed=
<script src="https://visjs.github.io/vis-timeline/standalone/umd/vis-timeline-graph2d.min.js"></script>
<div id="visualization"></div>
```


*  javascript

```js=
var items = [
  { x: "2022-04-11", y: 10 },
  { x: "2022-04-12", y: 25 },
  { x: "2022-04-13", y: 30 },
  { x: "2022-04-14", y: 10 },
  { x: "2022-04-15", y: 15 },
  { x: "2022-04-16", y: 30 },
];

var dataset = new vis.DataSet(items);
var graph2d = new vis.Graph2d(visualization, dataset)
```
## [Построение динамических графиков](https://nodejsexpress.arthmax.repl.co/)

### Инициализация  vis.Graph2d
```js=
// Initialization of  vis.Graph2d
var groups = new vis.DataSet();
 let count = 0
 var items = [];
  var dataset = new vis.DataSet(items);
 var options = {};
   var graph2d = new vis.Graph2d(visualization, dataset, groups, options);

```
### Динамическое добавление данных
```js
    let t1 = new Date() ; 
    let  rtt = t1-t0   
          dataset.add({ x: count++ , y: rtt })  
           graph2d.setWindow(0, count+1, { animation: false });
```
### Динамическое добавление данных для разных групп
```js
count++
 dataset.add({ x: count , y: rtt1, group: 1})  
 dataset.add({ x: count , y: rtt2, group: 2})  
  graph2d.setWindow(0, count); 
```
#### Пример графика с двумя группами значений
![](https://i.imgur.com/pf5d0Xa.png)

### Использование графика с несколькими группами для создания диаграммы суммирования потоков (скан-диаграммы)
 Если нам поступают одновременно $n$ однотипных потоков данных  $X_i(t),\, i \in [0,n-1]$ где $i$ - номер потока, $t$ - дискретное время, то для  создания диаграммы суммирования потоков необходимо выполнить следующие шаги:  
 1) Преобразование поступающих данных в потоки $Y_i$ определяемых как
    $$
      Y_0(t) = X_0(t) \\
      Y_i(t) = Y_{i-1}(t) + X_i(t), \, i>0
    $$
 2) Стандартная групповая визуализация потоков $Y_i$
 3) Необязательная раскраска областей между графиками потоков
 
## Проблемы синхронизации и согласования состояний
 Термин **синхронизация** описывает две разные, но близкие концепции: 
 * *синхронизация процессов*
 * *синхронизация дaнных*. 
  
  *Синхронизация процессов* относится к ситуациям, когда множество процессов должны дождаться общей точки во времени или выполнить фазу "рукопожатия", для достижения соглашения или свершения некоторой последовательности действий.
  
  *Синхронизация данных* описывает концепцию согласования множества копий данных (состояний) или поддержку целостности данных. 
  
 [В локальных системах:](https://www.wikiwand.com/en/Synchronization_(computer_science))
  Согласование состояния памяти и кэша
  Согласование состояния файловой системы
  Согласование транзакций
  
 [В распределенных системах:](https://www.wikiwand.com/en/Data_synchronization)
  ....
  
  Асинхронное и синхронное согласование данных
  Согласование состояний распределенных приложений
  [![](https://i.imgur.com/mbXzRQo.png)](https://www.wikiwand.com/en/Data_synchronization)

  Распознавание сбоев и ошибок и обезпечение устойчивости к ним
  **Согласование времени**
  ![](https://i.imgur.com/tcE8kkl.png)

  
## Синхронизация времени
### [Алгоритм синхронизации часов](https://www.wikiwand.com/en/Network_Time_Protocol#:~:text=dim.%22%5B32%5D%5Bb%5D-,Clock%20synchronization%20algorithm,-Round%2Dtrip%20delay)


Алгоритм синхронизации часов клиента и сервера выполняется в  ходе обмена короткими синхронизирующими и тестирующими состояние канала связи сообщениями.

![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/NTP-Algorithm.svg/440px-NTP-Algorithm.svg.png)
Рис. Шаг обмена сообщениями между клиентом и сервером в алгоритме синхронизации

#### Начальная оценка текущего рассогласования

Начальная оценка текущего рассогласования $\theta_0$ между временными метками клиента и сервера:
$$
  \theta_0= \frac{(t_1-t_0)+(t_2-t_3)}{2}
$$
где
$t_0$ — временная метка клиента о передаче пакета запроса,
$t_1$ — временная метка сервера приема пакета запроса,
$t_2$ — временная метка сервера передачи ответного пакета и
$t_3$ — временная метка клиента о приеме ответного пакета,

и круговой задержки $\delta$:
$$
\delta = (t_3-t_0)-(t_2-t_1)
$$
Чтобы получить выражение для  начального смещения $\theta_0$, необходимо решить систему, предполагая, что задержка сигнала от клиента к серверу равна задержке от сервера к клиенту:
$$
 t_0 +\theta_0+\frac{1}{2}\delta=t_1 \\
 t_3 +\theta_0-\frac{1}{2}\delta=t_2
$$
#### Уточнение параметра рассогласования

Часто  предположение о симметричности задержек оказывается ложным. Поэтому для получения более точной оценки  $\theta'$ необходимо реализовать схему уточнения на следующих шагах алгоритма  синхронизации.
 Для каналов с асимметричными задержками можно переписать систему уравнений в виде системы с ограничением:
 $$
 t_0 +\theta'+p\cdot\delta=t_1 \\
 t_3 +\theta'-(1-p)\cdot\delta=t_2 \\
   0 < p < 1,
$$
где $p$ - параметр асимметрии (для симметричных задержек $p=1/2$) 

**Вопрос. Почему нельзя решить данную систему непосредственно ?**

 *Уточнение величины асимметрии удобнее всего проводить с помощью односторонних протоколов, таких, как [UDP](https://en.wikipedia.org/wiki/UserDatagramProtocol)  и протоколов, основанных на них, напрмер, [WebRTC](https://ru.wikipedia.org/wiki/WebRTC).*
**Задание.  Обосновать данный тезис**

### Упрощенный вариант алгоритма синхронизации

Для сетевых распределенных игр требуется простой метод синхронизации часов. В идеале он должен обладать следующими свойствами: быть достаточно точным, быстро сходиться, быть простым в реализации и способным работать на протоколах с подтверждением доставки, таких как TCP или WebSockets.

Упрощенный вариант алгоритма ( похожий на [SNTP](https://ru.wikipedia.org/wiki/SNTP)) с этими свойствами выглядит следующим образом:

1) Клиент отмечает свое местное время $t_0$ в пакете «запрос времени» и отправляет на сервер

2) После получения сообщения от клиента сервер отмечает свое локальное время $t_1$ и возвращает его клиенту (считается, что сервер настолько быстро работает, что $t_1=t_2$)

3) После получения клиентом $t_1$, клиент вычитает свое текущее время $t_3$ из отправленного времени $t_0$ и делит на два, чтобы вычислить задержку $\delta$ (опять мы считаем, что сервер настолько быстро работает, что $\delta= t_3-t_0$).
Далее клиент вычитает  текущее время $t_3$ из времени сервера $t_1$, чтобы определить "слепую дельту" времени клиента и сервера, и добавляет к ней половинную задержку $\delta/2$ , чтобы получить оценку $\theta$.

"Слепую дельту" можно немедленно использовать для обновления часов, так как она установит локальные часы, по крайней мере, в правильное приблизительное положение (хотя бы, в правильный часовой пояс!)

Клиент повторяет шаги с 1 по 3 пять или более раз, каждый раз делая паузу в несколько секунд. Другой трафик может быть разрешен на время, но его следует свести к минимуму для достижения наилучших результатов.
Результаты получения пакетов накапливаются и сортируются по значениям задержек. Средняя задержка определяется путем выбора средней точки (медианы) из этого упорядоченного списка.
Все образцы выше примерно 1 стандартного отклонения ($\sigma$) от медианы отбрасываются, а оставшиеся образцы усредняются с использованием среднего арифметического.

*Можно модифицировать описанный алгоритм, учитывая наблюдаемое вероятностное распределения задержек, которое сильно отличается от гауссовского. В частности, на протяжении десятков секунд можно получить строгий минимум времени задержки.*

### [Библиотека 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);
```
 # Ресурсы
1. [Network Time Protocol](https://www.wikiwand.com/en/Network_Time_Protocol)
2. [A Stream-based Time Synchronization Technique For Networked Computer Games](https://web.archive.org/web/20160310125700/http://mine-control.com/zack/timesync/timesync.html) 
3. [SNTP](https://ru.wikipedia.org/wiki/SNTP)
5. [Building blocks of UDP](https://hpbn.co/building-blocks-of-udp/)
6. [WebRTC](https://hpbn.co/webrtc/)