292
правки
Изменения
→26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
* [[Асинхронные и синхронные распределённые системы]]'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики) * [[Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам? Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.]]*Каждый рассылает каждому свое число;*Каждый рассылает каждому собранные значения;*В полученных векторах каждый проводит голосование. Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен. Доказательство от Елизарова: Пусть каждому процессу подаётся число 0 или 1 на вход(могут быть разными на разных процессах). Задача - прийти к нетривиальному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному работающему процессу. (Сильный консенсус) [[Файл:byzantine.png|frame|rightНевозможность византийского консенсуса]] Предположим обратное. Пусть существует алгоритм консенсуса. Тогда расставим 4 ноды с этим алгоритмом, подадим верхним на вход 0, и нижним = 1. Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1. И если мы считаем рабочими 2 правых, а 2 левых - одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - то верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - к консенсусу на 1 с воображаемым нижним соседом. Fail. Поэтому такого алгоритма нет, и консенсус при N=3 и , f=1 невозможен.
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
