Децентралізована синхронізація

Децентралізована синхронізація в розподілених системах

Це варіант, коли зовнішній годинник відсутній і треба за скінченну кількість тактів встановити локальний таймер в одне локальне значення.

Як синхронізувати цілком однакові вузли, які не мають затримки:

Задача синхронізації ланцюжку стрільців(Джона Майхілла)

S₀ – початковий стан в якому знаходяться всі вузли; S – стан попередньої готовності.

Агенти між собою обмінюються сигналами з різною «швидкістю»(з якою затр. вузол який передав сигнал передасть повідомлення іншому вузлу)

Крайній вузол відправляє в ланцюжок одночасно 2 сигнали ”а₁” та ”а₃” при цьому специфічно поводиться крайній вузол, він їх віддзеркалить (після цього крайній вузол при отриманні сигналу ”а” переходить в стан S₁).

Всі інші вузли виконують такий алгоритм:

Ø Якщо отриманий 1 сигнал, то передати його далі по ланцюжку;

Ø Якщо отримано 2-ва сигнали то віддзеркалити їх, і передати далі по ланцюжку, а також перейти в стан S;

Ø Якщо даний вузол і 2 його сусіди знаходяться в стані, S то зробити потрібну дію (зробити «постріл»).