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

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

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


### Пример кода для создания простейшей статической диаграммы
* HTML

<script src="https://visjs.github.io/vis-timeline/standalone/umd/vis-timeline-graph2d.min.js"></script>
<div id="visualization"></div>

* javascript

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

// 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);

### Динамическое добавление данных

    let t1 = new Date() ; 
    let  rtt = t1-t0   
          dataset.add({ x: count++ , y: rtt })  
           graph2d.setWindow(0, count+1, { animation: false });

### Динамическое добавление данных для разных групп

count++
 dataset.add({ x: count , y: rtt1, group: 1})  
 dataset.add({ x: count , y: rtt2, group: 2})  
  graph2d.setWindow(0, count); 

#### Пример графика с двумя группами значений

### Использование графика с несколькими группами для создания диаграммы суммирования потоков (скан-диаграммы)
Если нам поступают одновременно $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://www.wikiwand.com/en/Data_synchronization)

Распознавание сбоев и ошибок и обезпечение устойчивости к ним
**Согласование времени**

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

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

Рис. Шаг обмена сообщениями между клиентом и сервером в алгоритме синхронизации

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

Начальная оценка текущего рассогласования $\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

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

  <script src="/timesync/timesync.js"></script> 
   <div id=Info></div>

* client javascript

  // 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/)