Синхронізація в розподілених системах: централізовані служби часу

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

GMT – Grinwich meridian time

UTC – Universal Coordinated Time

Є механізм корегування показів UTC до астрономічного часу.

International Atomac Time

Узагальнена схама централізованої синхронізації

Зовнішній

годинник

20. Синхронізація в розподілених системах: відмітки часу Лампорта

В логічному часі на відміну від фізичного важлива лише послідовність подій, а не точний час їх виникнення.

а в

t

Предекат Лампорта ставить 1 подію перед іншою.

Всі процеси згідні з тим, що з початку відбулася подія а, а пізніше в. В розподіленій системі це означає:

1) а і в події, які відбулися в 1 процесі, то

а –>в істина

2) якщо а - це відправка повідомлення, в – отримання цього повідовлення, то

а –> в істина

Якщо для 2 подій не виконуються умови 1 і 2, то вони називаються паралельними.

Транзитивність:

а –>в в –>с, то а –>с .

Відмітки часу Лампорта – це цілі числа, які ставляться у відповідність події.

Алгоритм Лампорта (присвоєння відміток):

1. Будь яким двом подіям в 1 процесі призначаються відмітки, різняться хоча б на 1.

2. Кожне повідомлення супроводжується відміткою Лампорта відправника.

3. Якщо ця відмітка більша за показ логічного годинника отримувача, то він встановлюється в це значення.

Векторні відмітки часу додатково враховують причинно-наслідкові зв’язки.

21. Алгоритми голосування в розподілених системах.

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

Необхідні умови для здійснення голосування:

1) кожний вузол знає кількість інших вузлів N;

2) кожний вузол має ідентифікатор (наприклад MAC-адресу);

3) всі вузли поєднанні між собою каналами зв’язку;

Приклади алгоритмів голосування в розподілених системах:

1) алгоритм забіяки;

2) алгоритм голосування на кільці;

3) рандомізований алгоритм голосування;

22. Голосування в розподілених системах: алгоритм забіяки.

Усі вузли мають ID і знають ID інших вузлів. Схема вузлів кожний з кожним.

Алгоритм:

1) Вузол, який претендує на лідерство розсилає усім іншим вузлам, з номерами більшими за його, повідомлення у голосуванні.

2) Якщо йому ніхто не відповів то він стає лідером і повідомляє про це усім іншим клієнтам. Інакше, якщо він отримав відповідь «ОК» то він не стає лідером.

3) Агент, який отримав повідомлення про голосування, відсилає агенту який прислав повідомлення, відповідь «ОК» і виконує п.п. 1,2

Характеристика: в такий спосіб буде вибрано вузол-лідер (вузол з найбільшим номером) за скінчений час.

23. Голосування в розподілених системах: алгоритм голосування на кільці.

Алгоритм:

1) Всі вузли мають ID і поєднанні в кільце з 2-ома сусідніми вузлами.

2) Якщо номер отриманий від свого сусіда більший за власний, тоді він пересилає його по кільцю. Якщо свій номер більший, тоді пересилає свій номер по кільцю (іншому з двох сусідніх вузлів).

3) Якщо вузол отримав свій ID то він лідер в даній групі вузлів і повідомляє інші вузли групи про те що він лідер.

24. Голосування в розподілених системах: рандомізований алгоритм голосування

Необхідні умови:

1) Вузли не мають ID.

2) Всі вузли взаємодіють по одно-направленій кільцевій схемі.

3) Кількість вузлів N відома усім вузлам.

Опис алгоритму:

1) Кожен вузол може знаходитись в станах S_0­, S_R­. Якщо вузол перейшов в стан S₀, тоді свій номер рівний 0. Якщо в стан S_R­, тоді номер вибирається випадково в межах [1,N].

2) Алгоритм виконується циклами по N-тактів. В кожному такті вузол передає свій номер та ном. Отр. від сус. вузл, далі до іншого сусіднього вузла.

3) Після N-тактів роботи, кожен вузол отримав масив з N-номерів. Якщо в цьому масиві є один номер більший за всі інші номери, тоді вузол під цим номером стає лідером.

4) Якщо таких найбільших номерів є декілька, то всі вузли з цим номером залишаються в стані S_R­, а інші вузли переходять в стан S₀. І цикл алгоритму продовжується для вузлів в стані S_R­.