Алгоритм вибору лідера

У розподілених обчисленнях, вибір лідера є процесом позначення одного процесу як організатора деякого завдання, розподіленого між декількома комп'ютерами (вузлами). Перш ніж розпочати завдання, всі вузли мережі або не знають, який вузол буде виконувати роль «лідера» (або координатора) завдання, або ці вузли не можуть спілкуватися з поточним координатором. Проте після запуску алгоритму вибору лідера кожен вузол у мережі визначає один особливий, унікальний вузол і сприймає його як лідера завдання.

Вузли мережі спілкуються між собою, щоб вирішити, який з них отримає статус «лідеру». Для цього вони використовують певний метод (алгоритм), щоб розірвати симетрію серед них (назначити одному з них особливий статус). Наприклад, якщо кожен вузол має унікальні та порівнянні ідентичності, то вузли можуть порівнювати свої ідентичності і вирішувати, що вузол з найвищою ідентичністю є лідером.

Формулювання цієї проблеми часто приписується ЛеЛану (англ. LeLann), який сформулював її як метод створення нового маркера в мережі маркерів кільця, в якому маркер був втрачений.

Алгоритми виборів лідерів розроблені так, щоб бути максимально ефективними з точки зору загальної кількості переданих байтів і часу прийняття рішення. Алгоритм, запропонований Галлагером, Хумблетом і Спірою для загальних неорієнтованих графів, справив сильний вплив на розробку розподілених алгоритмів загалом, і отримав премію Дейкстри за значний внесок в розподілені обчислення.

Багато інших алгоритмів були запропоновані для різних типів мережевих графів, таких як неорієнтовані кільця, односпрямовані кільця, повні графи, сітки, напрямлені графи Ейлера та інші. Загальний метод, який відокремлює проблему з сімейства графів від проектування алгоритму виборів лідера, був запропонований Корахом, Куттеном і Мораном.

Визначення

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

1. У процесорів є два стани відносно лідерства «обраний лідером» або «не обраний лідером». Після того, як процесор стає обраним він ним і залишається (аналогічним чином, якщо він не був обраним).
2. При кожному виконанні алгоритму обирається тільки один процесор, як лідер, решта процесорів визначають, що вони не були обрані.

Дійсний алгоритм вибору лідера повинен відповідати наступним умовам:

1. Скінченність: алгоритм повинен закінчитися протягом обмеженого часу після вибору лідера. У підходах, що базуються на випадковості ця умова іноді заміняється певною іншою умовою (наприклад, вимагає припинення з ймовірністю 1).
2. Унікальність: є лише один процесор, який вважає себе лідером.
3. Узгодженість: всі інші процесори знають, хто є лідером.

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

• Механізм зв'язку: процесори можуть бути або синхронізовані (процесори синхронізуються тактовим сигналом), або асинхронними, де процесори мають різну тактову частоту.
• Імена процесів: процеси можуть мати унікальну ідентичність або не відрізнятися один від одного (в такому випадку вони називаються анонімними).
• Топологія мережі: наприклад, кільце, ациклічний граф або повний граф.
• Розмір мережі: алгоритм може використовувати або може не використовувати знання про кількість процесорів у системі.

Алгоритми

Вибір лідера в кільцях

Топологія кільцевої мережі

Кільцева мережа являє собою топологію зв'язаного графа, в якій кожен вузол точно з'єднаний з двома іншими вузлами, тобто для графа з n вузлами є рівно n ребер, що з'єднують вузли. Кільце може бути односпрямованим, тобто процесори здійснюють зв'язок лише в одному напрямку (вузол може надсилати повідомлення лише ліворуч або надсилати повідомлення лише праворуч), або двонаправлений, тобто процесори можуть передавати та отримувати повідомлення в обох напрямках (кожен вузол може передавати та отримувати повідомлення в обох напрямках, надсилати повідомлення ліворуч і праворуч).

Анонімні кільця

Анонімним є те кільце в якому кожен процесор ідентичний. Більш формально, система має один і той же автомат для кожного процесора. Не існує детермінованого алгоритму для вибору лідера в анонімних кільцях, навіть якщо розмір мережі відомий процесорам. Це пов'язано з тим, що не існує можливості порушення симетрії в анонімному кільці, якщо всі процесори працюють з однаковою швидкістю. Стан процесорів після деяких кроків залежить тільки від початкового стану сусідніх вузлів. Тому, оскільки їхні стани ідентичні і виконують ті ж самі процедури, на кожному кроці кожен процесор посилає ті самі повідомлення. Таким чином, кожний стан процесора також змінюється тотожним чином, і в результаті, якщо один процесор обраний лідером, то всі інші також мають бути обрані лідером.

Для простоти доведемо це твердження в анонімних синхронних кільцях. Доведення протиріччям. Розглянемо анонімне кільце R з розміром n>1. Припустимо, що існує алгоритм «А» для вирішення виборів лідера в цьому анонімному кільці R.

Лема: після $k$ проходів виконання алгоритму A в R, всі процеси мають однакові стани.

Доказ. проводиться за допомогою індукції по $k$.

База індукції: $k=0$: всі процесори знаходяться в початковому стані, тому всі процесори однакові.

Індукційний перехід: припустимо, що лема виконується для $k-1$ раундів.

Індуктивний крок: на кроці $k$, кожен процесор посилає одне і те ж повідомлення $m_{r}$ праворуч і посилає те саме повідомлення $m_{l}$ ліворуч. Оскільки всі процесори знаходяться в одному і тому ж стані після кроку $k-1$, в раунді $k$, кожен процесор отримає повідомлення $m_{r}$ з лівого краю, і отримає повідомлення $m_{l}$ з правого краю. Оскільки всі процесори отримують одне і те ж повідомлення на кроці $k$, вони знаходяться в одному і тому ж стані після кроку $k$.

Лема, наведена вище, суперечить тому, що після деякого кінцевого числа раундів у виконанні А один процесор отримав би стан «обраний лідером», а інші процесори отримали б стан «не обраний».

Увипадковлені алгоритми вибору лідера

Загальним підходом до вирішення проблеми виборів лідера в анонімних кільцях є використання увипадковлених алгоритмів. У таких підходах, як правило, процесори беруть на себе деякі ідентичності на основі ймовірнісної функції і передають їх іншим мережам. Наприкінці, за допомогою застосування алгоритму, вибирається лідер (з високою ймовірністю).

Асинхронне кільце

O(nlogn) алгоритм для асинхронних кілець

Оскільки не існує алгоритму для анонімних кілець (доведено вище), асинхронні кільця будуть розглядатися як асинхронні не анонімні кільця. У не анонімних кільцях кожен процесор має унікальний ідентифікатор, і вони не знають розмір кільця до початку роботи алгоритму. Вибір лідера в асинхронних кільцях може бути вирішений за допомогою певного алгоритму з використанням $O(n^{2})$ повідомлень або $O(n\log n)$ повідомлень.

У алгоритмі $O(n^{2})$ кожен процесор надсилає повідомлення зі своїм ідентифікатором до лівого краю. Потім чекає, поки з'явиться повідомлення з правого краю. Якщо ідентифікатор в повідомленні більше, ніж його власний ідентифікатор, то він пересилає це повідомлення знову до лівого краю; інакше він ігнорує повідомлення, і нічого не робить. Якщо ідентифікатор в повідомленні дорівнює його власному ідентифікатору, то він відправляє повідомлення ліворуч, яке оголошує цей вузол обраним. Інші процесори передають оголошення ліворуч і перетворюються на не обраних. Зрозуміло, що для цього алгоритму верхня межа є $O(n^{2})$.

У алгоритмі $O(n\log n)$ алгоритм працює по фазах. На $k$-й фазі, процесор визначатиме, чи є він переможцем серед сусідів з лівої $2^{k}$ і з правої $2^{k}$ сторони. Якщо це переможець, то процесор може перейти до наступного етапу. У фазі $0$ кожен процесор $P$ повинен визначити себе як переможця чи ні, відправивши повідомлення з його ідентифікатором до лівого і правого сусідів (сусіди не пересилали це повідомлення). Сусід відповідає $ACK$ тільки, якщо ідентифікатор в повідомленні більше, ніж ідентифікатор сусіда, інакше відповідає $ACK_{fault}$. Якщо $P$ отримує два $ACK$-и, один з лівого, один з правого, то $P$ є переможцем у фазі $0$. На етапі $k$, переможцям фази $k-1$ необхідно надіслати повідомлення з його ідентифікатором $2^{k}$ лівим і $2^{k}$ правим сусідам. Якщо сусіди на шляху отримують ідентифікатор в повідомленні, більший, ніж їхній ідентифікатор, то вони пересилають повідомлення наступному сусіду, інакше повертають відповідь $ACK_{fault}$. Якщо $2^{k}$-й сусід отримує ідентифікатор більший, ніж його ідентифікатор, то відправляє назад $ACK$, інакше відправляє відповідь $ACK_{fault}$. Якщо процесор отримує два $ACK$-и, то він є переможцем на $k$ етапі. На останньому етапі остаточний переможець отримає свій ідентифікатор у повідомленні, а потім припинить виконання алгоритму та надішле повідомлення про закінчення іншим процесорам. У найгіршому випадку кожна фаза має не більше ${\frac {n}{2^{k}+1}}$ переможців, де $k$ — номер фази. У загальній складності знаходяться фази $\lceil \log(n-1)\rceil$. Кожен переможець надсилає в порядку $2^{k}$ повідомлень на кожній фазі. Отже, складність повідомлень є $O(n\log n)$.

Синхронізовані кільця

У книзі «Розподілені обчислення» Аттія та Уельч описали неоднорідний алгоритм, який використовує повідомлення $O(n)$ в синхронному кільці з відомим розміром кільця $n$. Алгоритм працює по фазах, кожна фаза має вигляд $n$ кроків, кожен крок є одиницею часу. У фазі $0$, якщо є процес з $id=0$, то процес $0$ посилає повідомлення завершення інших процесорів (вартість відправлення повідомлення завершення $n$ кроків). Інакше, переходимо до наступного етапу. Алгоритм перевірить, чи є номер фази, що дорівнює ідентифікатору процесору, потім робить ті ж кроки, що і фаза $0$. Наприкінці виконання мінімальний ідентифікатор буде обраний лідером. Він використав точно $n$ повідомлень та $n(minimum\_id+1)$ кроків.

Ітай та Роде ввели алгоритм односпрямованого кільця з синхронізованими процесорами. Вони припускають, що розміри кільця (кількість вузлів) відомі процесорам. Для кільця розміром n активні a≤n процесори. Кожен процесор вирішує з імовірністю a⁻¹, чи стане він кандидатом. В кінці кожної фази кожен процесор обчислює кількість кандидатів c, і якщо він дорівнює 1, цей процесор стає лідером. Щоб визначити значення c, кожен кандидат посилає маркер (англ. pebble) на початку фази, який передається навколо кільця, повертаючи через рівно n одиниць часу своєму відправнику. Кожен процесор визначає c шляхом підрахунку кількості маркерів, які пройшли через нього. Цей алгоритм досягає виборів керівника з очікуваною складністю повідомлення $O(n\log n)$. Аналогічний підхід також використовується, коли механізм тайм-ауту використовується для виявлення тупиків у системі. Існують також алгоритми для кілець спеціальних розмірів, таких як розміри простого числа і непарні розміри.

Однорідний алгоритм

У типових підходах до виборів лідера розмір кільця вважається відомим процесорам. У випадку анонімних кілець, без використання зовнішньої сутності, неможливо обрати лідера. Навіть якщо алгоритм існує, лідер не може визначити розмір кільця. Тобто в будь-якому анонімному кільці існує висока ймовірність того, що алгоритм обчислить неправильний розмір кільця. Щоб подолати цю проблему, Фішер і Цзян використовували так званого лідера-оракула Ω?, що кожен процесор може запитати, чи існує у кільці унікальний лідер. Вони показують, що з певної точки вгору гарантовано повертається однакова відповідь на всі процесори.

Кільця з унікальними ідентифікаторами

В одній з ранніх робіт Чанг і Робертс запропонували єдиний алгоритм, в якому процесор з найвищим ідентифікатором обирається в якості лідера. Кожен процесор посилає свій ідентифікатор за годинниковою стрілкою. Кожен процесор приймає повідомлення і порівнює його з власним. Якщо він більший, він посилає його далі, інакше він проігнорує повідомлення. Вони показують, що цей алгоритм використовує не більше O(n²) повідомлень і $O(n\log n)$ в середньому випадку. Хіршберг і Сінклер удосконалили цей алгоритм з $O(n\log n)$ складністю повідомлень, ввівши 2-канальну схему передачі повідомлень, що дозволило процесорам надсилати повідомлення в обох напрямках.

Вибір лідера в решітці

Топологія решітчатої мережі. Червоні вузли означають кути, сині — границі і сірі — внутрішні вузли.

Решітка є ще однією з популярних форм топології мереж, особливо в паралельних системах, резервних системах пам'яті та мережах взаємоз'єднань. У сітчастої структурі вузли — це кути (що мають тільки двох сусідів), межа (мають тільки по три сусіди) або внутрішність (середні вузли, що мають по чотири сусіди). Кількість ребер в сітці розміром a x b дорівнює m=2ab-a-b.

Неорієнтована сітка

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

1. Процес пробудження: k вузлів ініціюють процес вибору. Кожен ініціатор посилає повідомлення пробудження всім сусіднім вузлам. Якщо вузол не є ініціатором, він просто пересилає повідомлення на інші вузли. На цьому етапі відправляються не більше 3n+k повідомлень.
2. Процес виборів: вибори у зовнішньому кільці здійснюються не більше як в два етапи з 6(a+b)-16 повідомлень.
3. Припинення: лідер відправляє повідомлення завершення до всіх вузлів. Це вимагає не більше 2n повідомлень.

Складність повідомлення не більше 6(a + b) - 16, і якщо сітка квадратної форми, $O({\sqrt {(}}n))$.

Орієнтована сітка

Орієнтована сітка — це особливий випадок, коли номери портів — це компас, тобто північ, південь, схід і захід. Вибір лідеру в орієнтованій сітці тривіальний. Нам потрібно лише призначити кут, наприклад, «Північ» і «схід» і переконайтеся, що вузол знає, що він став лідером.

Роздута решітка

Структура роздутої решітки.

Особливим випадком сітчастої архітектури є тор (англ. torus), який є сіткою з «обгортаннями». У цій структурі кожен вузол має рівно по 4 з'єднувальні ребра. Один з підходів до обрання лідера в такій структурі називається етапами виборів. Подібно до процедур у кільцевих структурах, цей метод на кожному етапі виключає потенційних кандидатів доки не залишиться один з кандидатів. Цей вузол стає лідером, а потім повідомляє всім іншим процесорам про припинення. Цей підхід може бути використаний для досягнення складності O(n). Існують також більш практичні підходи, що застосовуються для боротьби з наявністю несправних ланок у мережі.

Вибір в гіперкубі

Топологія H_4 гіперкубової мережі.

Гіперкуб H_k — це мережа, що складається з n=2^k вузлів, кожен зі ступенем k та $O(n\log n)$ ребер. Для вирішення проблеми обрання лідера в даному випадку можна застосовувати раніше розглянуті алгоритми. На кожному етапі змагаються два вузли (які називаються дуелянтами), а переможець переходить до наступного етапу. Це означає, що на кожному етапі тільки половина дуелянтів виходить на наступний етап. Ця процедура триває, поки не залишиться лише один дуелянт, і він стає лідером. Після вибору він повідомляє про це всі інші процесори. Цей алгоритм вимагає O(n) повідомлень. У випадку неорієнтованого гіперкуба можна використовувати аналогічний підхід, але з більш високою складністю повідомлення $O(n\log \log n)$.

Вибір в повних мережах

Структура повної мережі.

Повні мережі є структурами, в яких всі процесори з'єднані один з одним, тобто ступінь кожного вузла n-1, де n — це розмір мережі. Оптимальне рішення досягається з O(n) повідомленням та відомою просторовою складністю. У цьому алгоритмі процесори мають наступні стани:

1. Манекен: вузли, які не беруть участі в алгоритмі вибору лідера.
2. Пасивний: початковий стан процесів перед запуском.
3. Кандидат: статус вузлів після пробудження. Здатними стати лідером будуть вважатися кандидатські вузли.

Для вибору лідера в мережі розглядається віртуальне кільце. Всі процесори спочатку ініціюються пасивним станом, поки вони не прокинуться. Як тільки вузли прокинулися, вони є кандидатами, щоб стати лідером. На основі схеми пріоритету вузли-кандидати співпрацюють у віртуальному кільці. У певний момент кандидати дізнаються про ідентичність кандидатів, які передують їм в кільці. Кандидати з вищим пріоритетом запитують нижчих про своїх попередників. Кандидати з більш низьким пріоритетом стають манекенами після того, як вони відповіли кандидатам з вищим пріоритетом. Виходячи з цієї схеми, кандидат з найвищим пріоритетом в кінцевому підсумку знає, що всі вузли в системі — це манекени, крім себе, і в цей момент він дізнається, що він став лідером.

Універсальні методи вибору лідера

Як випливає з назви, ці алгоритми призначені для використання в будь-якій формі технологічних мереж без будь-яких попередніх знань топології мережі або її властивостей, таких, наприклад, як її розмір.

Крик

Крик (англ. Shout) (протокол) створює кістякове дерево на загальному графі і обирає свій корінь як лідера. Алгоритм має лінійну загальну вартість по краях потужності.

Над-злиття

Ця методика Над-злиття по суті схожа на пошук мінімального кістякового дерева, в якому корінь дерева стає лідером. Основна ідея цього методу полягає в тому, що окремі вузли зливаються один з одним для формування великих структур. Результатом цього алгоритму є дерево (граф без циклу), корінь якого є лідером всієї системи. Вартість методу над-злиття є $O(m+n\log n)$ де m — число ребер і n — кількість вузлів.

Йо-йо

Приклад роботи алгоритму Йо-Йо. a) Мережа, b) Орієнтована мережа після фази налаштування, c) Йо- фаза в якій значення джерел проходять, d)-Йо фаза надсилає відповіді від стоків, e) оновлена структура після фази -Йо.

Йо-йо (алгоритм) є мінімальним алгоритмом пошуку, що складається з двох частин: фази попередньої обробки і послідовних ітерацій. На першій фазі або установці кожен вузол обмінюється своїм ідентифікатором з усіма своїми сусідами і засновується на значенні своїх орієнтованих ребер. Наприклад, якщо вузол x має менший ідентифікатор, ніж y, x орієнтується на y. Якщо вузол має менший ідентифікатор, ніж всі його сусіди, він стає джерелом. Навпаки, вузол з усіма внутрішніми ребрами (тобто з ідентифікатором більшим, ніж усі його сусіди) є стоком. Всі інші вузли є внутрішніми вузлами. Після того, як всі ребра орієнтовані, починається фаза ітерації. Кожна ітерація є виборчим етапом, коли деякі кандидати будуть видалені. Кожна ітерація має дві фази: Йо- і -йо. У цій фазі джерела починають процес розповсюдження до кожного стоку найменших значень джерел, з'єднаних зі стоком.

Йо-

1. Джерело (місцевий мінімуми) передає своє значення усім своїм сусідам
2. Внутрішній вузол чекає на отримання значення від усіх своїх сусідів. Він обчислює мінімум і відправляє його до сусіда.
3. Стік (вузол без вихідного ребра) отримує всі значення і обчислює їх мінімум.

-йо

1. Стік посилає ТАК до сусідів, з від яких вона отримала найменше значення, а НІ — іншим
2. Внутрішній вузол відправляє ТАК всім сусідам, з від яких він отримав найменше значення, і НІ — іншим. Якщо він отримує тільки один НІ, він посилає НІ всім.
3. Джерело чекає, поки не отримає всі голоси. Якщо всі голоси — ТАК, цей вузол залишається, і якщо наявні голоси НІ, то цей вузол вже не є кандидатом.
4. Коли вузол x посилає НІ до сусіда y, логічний напрямок цього ребра змінюється на протилежний.
5. Коли вузол y отримує НІ від зовнішнього сусіда, він перевертає напрямок цього посилання.

Після завершального етапу будь-яке джерело, що отримує НІ, більше не є джерелом і стає стоком. Додаткова стадія, обрізка, також вводиться для видалення непридатних вузлів, тобто їх існування не впливає на наступні ітерації.

1. Якщо стік є листом, то він не має сенсу і тому відкидається.
2. Якщо в Йо-фазі вузол отримав одне і те ж значення від більш ніж одного сусіда, він запитає всіх, крім одного, видалити зв'язки з ним.

Цей метод має загальну вартість повідомлень $O(m\log n)$. Його реальна складність повідомлення, включаючи обрізку, є відкритою проблемою дослідження і залишається невідомою.

Застосування

Радіо мережі

У протоколах радіомережі вибори лідера часто використовуються як перший крок для підходу до більш просунутих примітивів зв'язку, таких як збір повідомлень або трансляція. Сама природа бездротових мереж індукує зіткнення, коли суміжні вузли передаються одночасно; обрання лідера дозволяє краще координувати цей процес. Хоча відстань D мережі є природною нижньою межею часу, необхідного для вибору лідера, верхня і нижня межі проблеми вибору лідера залежать від конкретної досліджуваної моделі радіозв'язку.

Моделі та середовище виконання

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

Відомі режими роботи для однохопних мереж варіюються від постійної (очікуваної з виявленням зіткнення) до O(n log n) кроків (детермінований і без виявлення зіткнень). У багатохопних мережах відомі періоди виконання відрізняються від грубо O((D+ log n)(log² log n)) кроків (з високою ймовірністю в моделі звукового сигналу), O(D log n) (детермінований в звуковій моделі), O(n) (детермінований з виявленням зіткнення) до O(n log^3/2 n (log log n)^0.5) кроків (детермінований і без виявлення зіткнень).

Див. також

• Розподілені обчислення
• Алгоритм хулігана
• Виборча система