У розподілених обчисленнях, вибір лідера є процесом позначення одного процесу як організатора деякого завдання, розподіленого між декількома комп'ютерами (вузлами). Перш ніж розпочати завдання, всі вузли мережі або не знають, який вузол буде виконувати роль «лідера» (або координатора) завдання, або ці вузли не можуть спілкуватися з поточним координатором. Проте після запуску алгоритму вибору лідера кожен вузол у мережі визначає один особливий, унікальний вузол і сприймає його як лідера завдання.
Вузли мережі спілкуються між собою, щоб вирішити, який з них отримає статус «лідеру». Для цього вони використовують певний метод (алгоритм), щоб розірвати симетрію серед них (назначити одному з них особливий статус). Наприклад, якщо кожен вузол має унікальні та порівнянні ідентичності, то вузли можуть порівнювати свої ідентичності і вирішувати, що вузол з найвищою ідентичністю є лідером.
Формулювання цієї проблеми часто приписується ЛеЛану (), який сформулював її як метод створення нового маркера в мережі маркерів кільця, в якому маркер був втрачений.
Алгоритми виборів лідерів розроблені так, щоб бути максимально ефективними з точки зору загальної кількості переданих байтів і часу прийняття рішення. Алгоритм, запропонований Галлагером, Хумблетом і Спірою для загальних неорієнтованих графів, справив сильний вплив на розробку розподілених алгоритмів загалом, і отримав премію Дейкстри за значний внесок в розподілені обчислення.
Багато інших алгоритмів були запропоновані для різних типів мережевих графів, таких як неорієнтовані кільця, односпрямовані кільця, повні графи, сітки, напрямлені графи Ейлера та інші. Загальний метод, який відокремлює проблему з сімейства графів від проектування алгоритму виборів лідера, був запропонований Корахом, і .
Визначення Задача вибору лідера полягає в тому, щоб кожен процесор на кінець роботи алгоритму вирішив, чи є він лідером, чи ні, за умови, що тільки один процесор вирішує, що він є лідером.H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advance Topics, John Wiley & Sons inc., 2004, chap. 3 Алгоритм здатен вирішити задачу вибору лідера, якщо:
У процесорів є два стани відносно лідерства «обраний лідером» або «не обраний лідером». Після того, як процесор стає обраним він ним і залишається (аналогічним чином, якщо він не був обраним). При кожному виконанні алгоритму обирається тільки один процесор, як лідер, решта процесорів визначають, що вони не були обрані.
Дійсний алгоритм вибору лідера повинен відповідати наступним умовам:I. Gupta, R. van Renesse, and K. P. Birman,2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report , Cornell University
Скінченність: алгоритм повинен закінчитися протягом обмеженого часу після вибору лідера. У підходах, що базуються на випадковості ця умова іноді заміняється певною іншою умовою (наприклад, вимагає припинення з ймовірністю 1). Унікальність: є лише один процесор, який вважає себе лідером. Узгодженість: всі інші процесори знають, хто є лідером.
Алгоритм вибору лідера може змінюватися в наступних аспектах:R. Bakhshi, W. Fokkink, J. pang, and J. Van de Pol, c2008 «Leader Election in Anonymous Rings: Franklin Goes Probabilistic», TCS, Vol. 273, pp. 57-72.
Механізм зв'язку: процесори можуть бути або синхронізовані (процесори синхронізуються тактовим сигналом), або , де процесори мають різну тактову частоту. Імена процесів: процеси можуть мати унікальну ідентичність або не відрізнятися один від одного (в такому випадку вони називаються анонімними). Топологія мережі: наприклад, кільце, ациклічний граф або повний граф. Розмір мережі: алгоритм може використовувати або може не використовувати знання про кількість процесорів у системі.
Алгоритми
Вибір лідера в кільцях
Кільцева мережа являє собою топологію зв'язаного графа, в якій кожен вузол точно з'єднаний з двома іншими вузлами, тобто для графа з n вузлами є рівно n ребер, що з'єднують вузли. Кільце може бути односпрямованим, тобто процесори здійснюють зв'язок лише в одному напрямку (вузол може надсилати повідомлення лише ліворуч або надсилати повідомлення лише праворуч), або двонаправлений, тобто процесори можуть передавати та отримувати повідомлення в обох напрямках (кожен вузол може передавати та отримувати повідомлення в обох напрямках, надсилати повідомлення ліворуч і праворуч).
Анонімні кільця Анонімним є те кільце в якому кожен процесор ідентичний. Більш формально, система має один і той же автомат для кожного процесора.H. Attiya and M. Snir, 1988,"Computing on an anonymous ring",JACM,Vol. 35, issue. 4, pp. 845—875 Не існує детермінованого алгоритму для вибору лідера в анонімних кільцях, навіть якщо розмір мережі відомий процесорам. Це пов'язано з тим, що не існує можливості порушення симетрії в анонімному кільці, якщо всі процесори працюють з однаковою швидкістю. Стан процесорів після деяких кроків залежить тільки від початкового стану сусідніх вузлів. Тому, оскільки їхні стани ідентичні і виконують ті ж самі процедури, на кожному кроці кожен процесор посилає ті самі повідомлення. Таким чином, кожний стан процесора також змінюється тотожним чином, і в результаті, якщо один процесор обраний лідером, то всі інші також мають бути обрані лідером.
Для простоти доведемо це твердження в анонімних синхронних кільцях. Доведення протиріччям. Розглянемо анонімне кільце R з розміром n>1. Припустимо, що існує алгоритм «А» для вирішення виборів лідера в цьому анонімному кільці R.
Лема: після проходів виконання алгоритму A в R, всі процеси мають однакові стани. Доказ. проводиться за допомогою індукції по .
База індукції: : всі процесори знаходяться в початковому стані, тому всі процесори однакові.
Індукційний перехід: припустимо, що лема виконується для раундів.
Індуктивний крок: на кроці , кожен процесор посилає одне і те ж повідомлення праворуч і посилає те саме повідомлення ліворуч. Оскільки всі процесори знаходяться в одному і тому ж стані після кроку , в раунді , кожен процесор отримає повідомлення з лівого краю, і отримає повідомлення з правого краю. Оскільки всі процесори отримують одне і те ж повідомлення на кроці , вони знаходяться в одному і тому ж стані після кроку .
Лема, наведена вище, суперечить тому, що після деякого кінцевого числа раундів у виконанні А один процесор отримав би стан «обраний лідером», а інші процесори отримали б стан «не обраний».
Увипадковлені алгоритми вибору лідера Загальним підходом до вирішення проблеми виборів лідера в анонімних кільцях є використання увипадковлених алгоритмів. У таких підходах, як правило, процесори беруть на себе деякі ідентичності на основі ймовірнісної функції і передають їх іншим мережам. Наприкінці, за допомогою застосування алгоритму, вибирається лідер (з високою ймовірністю).
Асинхронне кільце
Оскільки не існує алгоритму для анонімних кілець (доведено вище), асинхронні кільця будуть розглядатися як асинхронні не анонімні кільця. У не анонімних кільцях кожен процесор має унікальний ідентифікатор, і вони не знають розмір кільця до початку роботи алгоритму. Вибір лідера в асинхронних кільцях може бути вирішений за допомогою певного алгоритму з використанням повідомлень або повідомлень.
У алгоритмі кожен процесор надсилає повідомлення зі своїм ідентифікатором до лівого краю. Потім чекає, поки з'явиться повідомлення з правого краю. Якщо ідентифікатор в повідомленні більше, ніж його власний ідентифікатор, то він пересилає це повідомлення знову до лівого краю; інакше він ігнорує повідомлення, і нічого не робить. Якщо ідентифікатор в повідомленні дорівнює його власному ідентифікатору, то він відправляє повідомлення ліворуч, яке оголошує цей вузол обраним. Інші процесори передають оголошення ліворуч і перетворюються на не обраних. Зрозуміло, що для цього алгоритму верхня межа є .
У алгоритмі алгоритм працює по фазах. На -й фазі, процесор визначатиме, чи є він переможцем серед сусідів з лівої і з правої сторони. Якщо це переможець, то процесор може перейти до наступного етапу. У фазі кожен процесор повинен визначити себе як переможця чи ні, відправивши повідомлення з його ідентифікатором до лівого і правого сусідів (сусіди не пересилали це повідомлення). Сусід відповідає тільки, якщо ідентифікатор в повідомленні більше, ніж ідентифікатор сусіда, інакше відповідає . Якщо отримує два -и, один з лівого, один з правого, то є переможцем у фазі . На етапі , переможцям фази необхідно надіслати повідомлення з його ідентифікатором лівим і правим сусідам. Якщо сусіди на шляху отримують ідентифікатор в повідомленні, більший, ніж їхній ідентифікатор, то вони пересилають повідомлення наступному сусіду, інакше повертають відповідь . Якщо -й сусід отримує ідентифікатор більший, ніж його ідентифікатор, то відправляє назад , інакше відправляє відповідь . Якщо процесор отримує два -и, то він є переможцем на етапі. На останньому етапі остаточний переможець отримає свій ідентифікатор у повідомленні, а потім припинить виконання алгоритму та надішле повідомлення про закінчення іншим процесорам. У найгіршому випадку кожна фаза має не більше переможців, де — номер фази. У загальній складності знаходяться фази . Кожен переможець надсилає в порядку повідомлень на кожній фазі. Отже, складність повідомлень є .
Синхронізовані кільця У книзі «Розподілені обчислення» Аттія та Уельч описали неоднорідний алгоритм, який використовує повідомлення в синхронному кільці з відомим розміром кільця . Алгоритм працює по фазах, кожна фаза має вигляд кроків, кожен крок є одиницею часу. У фазі , якщо є процес з , то процес посилає повідомлення завершення інших процесорів (вартість відправлення повідомлення завершення кроків). Інакше, переходимо до наступного етапу. Алгоритм перевірить, чи є номер фази, що дорівнює ідентифікатору процесору, потім робить ті ж кроки, що і фаза . Наприкінці виконання мінімальний ідентифікатор буде обраний лідером. Він використав точно повідомлень та кроків.
Ітай та РодеA. Itai and M. Rodeh, 1990,"Symmetry breaking in distributed networks", Vol. 88, issue 1, pp. 60-87. ввели алгоритм односпрямованого кільця з синхронізованими процесорами. Вони припускають, що розміри кільця (кількість вузлів) відомі процесорам. Для кільця розміром n активні a≤n процесори. Кожен процесор вирішує з імовірністю a−1, чи стане він кандидатом. В кінці кожної фази кожен процесор обчислює кількість кандидатів c, і якщо він дорівнює 1, цей процесор стає лідером. Щоб визначити значення c, кожен кандидат посилає маркер () на початку фази, який передається навколо кільця, повертаючи через рівно n одиниць часу своєму відправнику. Кожен процесор визначає c шляхом підрахунку кількості маркерів, які пройшли через нього. Цей алгоритм досягає виборів керівника з очікуваною складністю повідомлення . Аналогічний підхід також використовується, коли механізм тайм-ауту використовується для виявлення тупиків у системі.L. Higham and S. Myers, 1998, «Self-Stabilizing Token Circulation on Anonymous Message Passing Rings», Second International Conference On Principles Of DIstributed Systems. Існують також алгоритми для кілець спеціальних розмірів, таких як розміри простого числаG. Itkis, C. Lin, and J. Simon,1995,"Deterministic, constant space, self-stabilizing leader election on uniform rings.", In Proc. 9th Workshop on Distributed Algorithms, Vol. 972, pp. 288—302.J. Burns and J. Pachl,1989,"Uniform self-stabilizing rings",ACM Trans. Program. Lang. Systems, Vol. 11, issue. 2, pp.330-344 і непарні розміри.T. Herman, 1990, «Probabilistic self-stabilization», Inf. Process. Lett., Vol. 35, issue 2, pp.63-67.
Однорідний алгоритм