Консенсус (комп'ютерні науки)
Консенсус в загальному випадку трактується як процес прийняття групою осіб єдиного рішення, досягнення згоди з якого-небудь питання. При цьому як такого голосування не проводиться — рішення приймається на основі відсутності заперечень у більшості учасників. Варто зазначити що консенсусом називають не тільки сам процес прийняття рішення, але саме прийняте в результаті такої процедури рішення, тобто результат.
Опис проблеми ред.
Роль консенсусних алгоритмів полягає в досягненні рівня надійності мережі, побудованої на серії вузлів (пристроїв, з'єднаних з іншими пристроями як частина комп'ютерної мережі). Це означає, що, якщо здійснена транзакція, то алгоритм почне працювати — обмінюватись інформацією в мережі, щоб перевірити, чи може дана дія мати місце.
Той же процес також застосовується для створення нових вузлів даних в блокчейн або при синхронізації мережевого обладнання, щоб забезпечити узгодженість всього консенсусу.
Алгоритм автоматично припустить, що деякі процеси і системи будуть недоступні і що в результаті цього деякі комунікації будуть втрачені. Щоб протистояти цьому, консенсусний алгоритм повинен бути відмовостійким і працювати для досягнення певного консенсусу чи схвалення, принаймні, від більшості машин в мережі.[1]
Протокол консенсусу повинен відповідати таким вимогам:
- Завершеність
- Зрештою, кожен процес повинен обирати якесь значення.
- Цілісність
- Якщо всі процеси запропонували одне й те ж значення ʋ, то будь-який процес повинен вирішити чи завершитися ʋ саме цим значенням.
- Узгодженість
- Кожний процес повинен погоджувати чи «домовлятися» з усіма процесами про одне й те ж значення.
Протокол, який може правильно гарантувати консенсус серед n процесів, з яких не більше t зазнає невдачі, називається t-стійким.
При оцінці продуктивності узгоджених протоколів інтерес представляють два фактори: час виконання і складність повідомлення. Час виконання вказується в позначенні Big O в кількості раундів обміну повідомленнями в залежності від деяких вхідних параметрів (зазвичай від числа процесів і / або розміру вхідного домену). Складність повідомлення відноситься до обсягу трафіку повідомлень, який генерується протоколом. Інші фактори можуть включати використання пам'яті і розмір повідомлень.
Моделі обчислення ред.
Різні моделі обчислень можуть визначати «проблему консенсусу». Деякі моделі можуть мати справу з повністю зв'язними графами, в той час як інші можуть мати справу з кільцями і деревами. У деяких моделях дозволена аутентифікація повідомлень, тоді як в інших процесах повністю анонімно. Моделі із загальною пам'яттю, в яких процеси взаємодіють за допомогою доступу до об'єктів, також є важливою областю досліджень.
Аутентифіковані канали зв'язку ред.
У більшості моделей протоколу консенсусу учасники спілкуються по аутентифікованих каналах. Це означає, що повідомлення не є анонімними, і одержувачі знають джерело кожного повідомлення, яке вони отримали. Деякі моделі передбачають більш сувору форму аутентифікації, коли кожне повідомлення підписується відправником, так що одержувач знає не тільки безпосереднє джерело кожного повідомлення, але і учасника, який написав повідомлення. Цей більш строгий тип аутентифікації досягається цифровими підписами, а при наявності такої форми аутентифікації протоколи можуть допускати більше помилок.[2]
Дві різні моделі аутентифікації часто називають усною та письмовою моделями спілкування. В усній моделі спілкування відоме безпосереднє джерело інформації, а у письмових моделях спілкування кожен крок на шляху до одержувача вивчає не тільки безпосереднє джерело повідомлення, але і історію спілкування.[3]
Задача візантійських генералів ред.
Існує два типи збоїв, які можуть виникнути в процесі: збій або візантійська невдача. Крах відбувається, коли процес раптово зупиняється і не може бути оновленим. Візантійська помилка — це невдачі, при яких абсолютно ніяких умов не нав'язується. Наприклад, вони можуть виникнути в результаті зловмисних дій супротивника.
Розглянемо детально задачу візантійських генералів.
Візантійський консенсус — загальне визначення завдання взаємодії кількох учасників мережі між собою, розташованих віддалено і отримують завдання з єдиного центру. Причому частина учасників мережі, включаючи сам центр, можуть виявитися зловмисниками. Іншими словами, алгоритм візантійського протоколу повинен забезпечити комунікацію між віддаленими учасниками мережі, виключивши обманні операції, тобто безпеку транзакцій.
Ідея візантійського консенсусу з'явилася в 80-х роках минулого століття. Його суть полягає в наступному. Візантія напередодні битви. Армія візантійців складається, наприклад, з 4 легіонів, які знаходяться один від одного на відстані. У певний час кожен з генералів легіонів отримує від керівного центру наказ йти в атаку або відступати. Розвиток подій наступне:
- якщо все легіони атакують — вони перемагають;
- якщо все легіони відступають — вони зберігають людей (теж вдалий результат);
- якщо частина атакує, частина відступає — армія зазнає поразки.
Завдання зрозуміле, але де гарантія, що серед генералів немає зрадників, які виконають наказ навпаки? І де гарантія, що сам головнокомандувач не опиниться зрадником, відправивши різні накази різним генералам? Висновок: генерали повинні обмінятися один з одним інформацією, виключивши помилкові дані. Точніше, вони повинні обмінятися інформацією про чисельність легіонів, вірних Візантії, і зробити висновки про чисельність легіону зрадників. Завдання передбачає, що при N кількості генералів зрадниками можуть виявитися N-1.
Принцип згоди полягає в тому, щоб усі вірні генерали в результаті обміну інформацією прийшли до однакового вирішення, проігнорувавши дані від генерала-зрадника. Повернемося до прикладу. Принцип обміну інформацією полягає в наступному:
- кожен генерал відправляє інформацію про чисельність свого легіону трьом іншим генералам. Причому зрадник для дезінформації відправляє кожному іншому генералу різні цифри про чисельність (у криптовалюті це аналог спаму, DDoS-атак, фіктивних транзакцій);
- кожен генерал формує блок, в якому вказує всі отримані чотири цифри із зазначенням, від кого саме вони були отримані, і цей готовий блок посилає іншим генералам;
- в результаті кожен генерал має на руках 4 блоки з цифрами про чисельність легіону кожного.
І логічно, що за трьома генералам цифри будуть однаковими в усіх трьох блоках і тільки по одному будуть розбіжності.
Таким чином, вірні генерали приходять до угоди, виключаючи думку зрадника. Приклад спрощений, але наочно показує, як учасники мережі приходять до єдиного рішення, виключаючи помилкові.
Асинхронні і синхронні системи ред.
Проблема консенсусу може бути розглянута в асинхронних або синхронних системах. Хоча зв'язок в реальному світі часто по своїй суті асинхронний, моделювання синхронних систем більш практичне і часто простіше, з огляду на, що асинхронні системи природним чином пов'язані з великою кількістю проблем, ніж синхронні.
У синхронних системах передбачається, що всі комунікації відбуваються у рамках сесії. За одну сесію процес може відправити всі необхідні йому повідомлення, отримуючи при цьому всі повідомлення від інших процесів. Таким чином, жодне повідомлення з одної сесії не може впливати на повідомлення, відправлені в тій ж сесії.
У повністю асинхронній системі не існує єдиного рішення, яке може допустити одну або більше помилок, навіть якщо вимагається лише властивість нетривіальності. Цей результат іноді називають доказом неможливості FLP, названим на честь авторів Майкла Дж. Фішера[en], Ненсі Лінч та Майка Патерсона[en], котрі отримали премію Дейкстри за цю значну роботу. Результат FLP не говорить про те, що консенсусу ніколи не можна досягти: лише те, що за припущеннями моделі жоден алгоритм не може завжди досягти консенсусу в обмежений час.
Еквівалентність проблем консенсусу ред.
Проблеми консенсусу, що представляють цікавість, полягають у наступному.
Завершення коректної трансляції ред.
Колекція процесів n, пронумерованих від 0 до n-1, відправляє повідомлення один одному. Процес 0 повинен передати значення всім процесам так, щоб:
- якщо процес 0 правильний, то кожний правильний процес отримує певне значення.
- для будь-яких двох правильних процесів кожен процес отримує одне і те ж значення.
Консенсус ред.
Формальні вимоги для узгодженого протоколу можуть включати:
- Узгодженість
- Всі процеси повинні узгоджувати одне і те ж значення.
- Слабка достовірність
- Для кожного правильного процесу його вихідні дані повинні бути вхідними даними якогось правильного процесу.
- Сильна достовірність
- Якщо всі процеси отримують одне й те ж значення, то всі вони повинні вивести це значення.
- Завершеність
- Всі процеси повинні прийняти рішення про вихідне значення.
Слабка інтерактивна узгодженість ред.
Для n процесів в частково синхронній системі (система чергує хороші і погані періоди синхронізації), кожен процес вибирає приватне значення. Процеси обмінюються даними один з одним в сесії, щоб визначити загальнодоступну цінність і створити узгоджений вектор з наступними вимогами:[4]
- якщо правильний процес відправляє ʋ(значення), то всі правильні процеси отримують або ʋ(значення), або нічого (властивість цілісності);
- всі повідомлення, відправлені в циклі правильним процесом, будуть отримані в одній сесії, усіма правильними процесами (властивість узгодженості).
Деякі протоколи консенсусу ред.
Інші протоколи, якими можуть користуватися криптовалюти, включають доказ важливості, доказ розташування, доказ активності, доказ минулого часу. Всі вони розглядаються як альтернатива доказу роботи, знову ж таки через велику кількість обчислювальної енергії, необхідної останньому.
Багато стратегічних ігор в режимі реального часу використовують модифікований протокол Lockstep[en] як протокол консенсусу для управління станом гри між гравцями. У результаті кожної ігрової дії дельта-стан ігрової трансляції передається всім іншим гравцям, а також хеш загального стану гри. Кожен гравець підтверджує зміну, застосовуючи дельту до власного ігрового стану та порівнюючи хеші ігрового стану. Якщо хеші не погоджуються, тоді відбувається голосування, а тих гравців, чий ігровий стан знаходиться в меншості, відключають та вилучають з гри (відома як десинхронізація).
Інший відомий підхід називається алгоритмами типу MSR, які широко використовуються від інформатики до теорії управління.
| Назва | Принцип | Продуктивність | Завершеність |
|---|---|---|---|
| Proof-of-Work (PoW — Доказ роботи) | Важко знайти рішення, але легко перевірити результат. | низька | імовірнісна |
| Proof-of-Stake (PoS — Доказ частки) | Мережа довіряє валідатору, який ставить свої власні ресурси в заставу за можливість створювати блоки: чим більше частка, тим вище ймовірність, що мережа дозволить створення блоку. | висока | імовірнісна |
| Delegated Proof-of-Stake (DPoS) (Делегований доказ частки) | Учасники делегують виробництво нових блоків невеликої і фіксованої кількості обраних валідаторів. Висока конкуренція, але дуже вигідна. | висока | імовірнісна |
| Proof-of-Activity (PoA) (Доказ активності) | Гібрид PoW і PoS. | низька | імовірнісна |
| Proof-of-Location (PoL) (Доказ розташування) | Використовуються маячки, щоб помітити вузол в синхронному стані, а потім відзначити тимчасовим штампом її присутність. | середня | негайна |
| Proof-of-Importance (PoI) (Доказ важливості) | Як і PoS, але з додатковими властивостями, які впливають на ваш рейтинг. | висока | імовірнісна |
| Proof-of-Elapsed-Time (PoET) (Доказ минулого часу) | Блоки створюються в середовищі з рівними періодами. | середня | імовірнісна |
У системах спільної пам'яті ред.
Для вирішення проблеми консенсусу в системах спільної пам'яті необхідно ввести одночасно об'єкти.
Супутній об'єкт або спільний об'єкт — це структура даних, яка допомагає одночасним процесам спілкуватися для досягнення згоди.
Існують два основні методи проектування такого об'єкта. Традиційно для вирішення цієї проблеми дизайнери використовують критичну секцію, а це означає, що лише один процес може відвідувати об'єкт, а інші повинні зачекати, поки цей процес не вийде з критичного розділу. Цей метод прямолінійний і простий у здійсненні. Однак системи з критичними ділянками стикаються з ризиком виходу з ладу, якщо якийсь процес гине всередині критичної секції або спить нестерпно тривалий час. А другий метод проектування називається реалізацією без очікування (неблокуючий алгоритм), який може гарантувати консенсус за обмежену кількість кроків.
Чи достатньо потужний даний об'єкт для вирішення проблем консенсусу? Моріс Херліхій дав «Ієрархію неможливості та універсальності».[5]
| Консенсусне число (кількість процесів) | Об'єкти |
|---|---|
| 1 | Регістри читання / запису |
| 2 | Тест-набори, змінити, отримати та додати, черга, стек |
| …… | …… |
| 2n — 2 | N-реєстрація призначень |
| …… | …… |
| ∞ | Переміщення та обмін пам'яті на пам'ять, збільшена черга, порівняння та розміщення, липкий байт |
Консенсусне число в ієрархії означає максимальну кількість процесів у системі, які можуть досягти консенсусу за даним об'єктом. Об'єкти з вищим числом консенсусу не можуть бути реалізовані об'єктами з меншим консенсусним числом.
Відповідно до ієрархії, регістри читання / запису не можуть вирішити консенсус навіть у системі з 2 процесами. Структура даних, як стек, черга тощо, може вирішити лише консенсус між двома процесами.
Однак деякі паралельні об'єкти є універсальними, а це означає, що вони можуть вирішити консенсус серед будь-якої кількості процесів, і вони можуть імітувати будь-які інші об'єкти. Спосіб моделювання інших об'єктів за допомогою універсальних об'єктів — це побудова послідовності операцій з цим одночасним об'єктом.[5]
Див. також ред.
Примітки ред.
- ↑ Coulouris, George F.; Kindberg, Tim. (2001). Distributed systems : concepts and design (вид. 3rd ed). Harlow, England: Addison-Wesley. ISBN 0-201-61918-0. OCLC 44953513.
- ↑ Dolev, D.; Strong, H. R. (1983-11). Authenticated Algorithms for Byzantine Agreement. SIAM Journal on Computing (англ.). Т. 12, № 4. с. 656—666. doi:10.1137/0212045. ISSN 0097-5397. Архів оригіналу за 2 грудня 2019. Процитовано 3 грудня 2019.
- ↑ Kailar, Rajashekar; Gligor, Virgil D.; Gong, Li (1995). On the Security Effectiveness of Cryptographic Protocols. Dependable Computing and Fault-Tolerant Systems. Vienna: Springer Vienna. с. 139—157. ISBN 978-3-7091-9398-3.
- ↑ Abdelzaher, Tarek.; Raynal, M. (Michel); Santoro, N. (Nicola), 1951- (2009). Principles of distributed systems : 13th international conference, OPODIS 2009, Nîmes, France, December 15-18, 2009 : proceedings. Berlin: Springer. ISBN 978-3-642-10877-8. OCLC 505433328. Архів оригіналу за 7 червня 2020. Процитовано 3 грудня 2019.
- ↑ а б Wait-Free Synchronization, 1991; Herlihy. SpringerReference. Springer-Verlag. Процитовано 3 грудня 2019.