Новый алгоритм позволил синхронизировать устройства без GPS и ведущего узла

В распределенных системах, таких как сети умных датчиков или группы роботов, каждый узел имеет собственные аппаратные часы. Они могут запускаться в разное время и поэтому изначально показывать разные значения. Кроме того, из-за производственных допусков и изменений температуры часы постепенно дрейфуют: одни начинают спешить, другие — отставать. Когда системе необходимо выполнять согласованные действия, например записывать события в общий журнал или поочередно включать исполнительные механизмы, такая рассинхронизация становится критической проблемой.

Эту задачу можно решать с помощью единого источника точного времени или назначенного ведущего узла, по которому синхронизируются остальные устройства. Однако глобальный сигнал может быть недоступен — например, в подземных коммуникациях, при плотной городской застройке или в космосе, — а связь с ведущим узлом может оборваться или сам он может выйти из строя. Его переназначение в условиях непостоянной связи усложняет работу системы. Поэтому в таких случаях применяются полностью децентрализованные алгоритмы, в которых устройства обмениваются информацией только с соседями и совместно вырабатывают общую временную шкалу.

Долгое время в этой области преобладали алгоритмы, где каждый узел периодически получает показания времени от соседей, вычисляет среднее значение и корректирует по нему свои часы. Со временем значения сходятся. Однако такой подход плохо подходит для логического времени.

Логическое время — это программный счетчик, определяющий порядок событий. Его главное требование — монотонность, то есть невозможность движения назад. Событие с меткой 100 не может после корректировки оказаться раньше события с меткой 99, иначе нарушается причинно-следственная связь в системе.

Существующие алгоритмы не удовлетворяют этому требованию. Если часы одного из узлов сильно спешат, для приближения к среднему значению им пришлось бы вернуться к меньшему значению. В результате уже зафиксированные события могут поменять порядок, что недопустимо для многих приложений — от промышленной автоматики до медицинских систем.

Исследователи СПбГУ и Университета «Сириус» предложили иной подход. Вместо среднего значения вся сеть ориентируется на максимальное логическое время. Результаты исследования опубликованы в научном журнале Scientificreports.

«Стремление к максимуму естественным образом устраняет проблему отката часов. Чтобы догнать максимум, никому не нужно уменьшать свои показания. Но если безоговорочно ориентироваться на максимальное значение, алгоритм становится чувствительным к шумам и помехам: даже одиночный сбой способен заставить всю сеть следовать случайному выбросу», — отметил профессор кафедры системного программирования СПбГУ Олег Граничин.

Чтобы избежать этой проблемы, авторы адаптировали алгоритм softmax, широко применяемый в машинном обучении. Благодаря этому устройствам не приходится откатывать свои часы назад, а синхронизация остается устойчивой даже при ошибках передачи данных.

Исследователи центра искусственного интеллекта и науки и о данных СПбГУ Иван Архипов, Евгений Крохалев и Олег Граничин продолжили работу в другой статье, посвященной распределенной обработке данных в беспроводных сенсорных сетях. Они показали, что эффективность обмена информацией зависит не только от алгоритма обработки данных, но и от того, как устройства регулируют мощность передачи сигнала. Предложенный подход позволяет одновременно экономить заряд батарей, сохранять работоспособность сети при выходе отдельных узлов из строя и поддерживать высокую точность вычислений.

Вместе обе работы предлагают новые методы построения надежных и энергоэффективных распределенных систем, востребованных в интернете вещей, промышленной автоматике и робототехнике.