===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
'''Задача двух Проблема византийских генералов''' — мысленный эксперимент- придти к нетривиальному консенсусу N процессам, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. если среди них есть f сбойных([https:могут вести себя как угодно//ruконтролируются злоумышленниками).wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B4%D0%B2%D1%83%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2 Википедия])
Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]]Алгоритм Лампорта(и еще 2 человек):Считаем, что у процессов есть номера. Процесс 1 - "генерал" - рассылает всем предложение - 0 или 1. И после этого молчит(принимает своё предложение).
Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least При f=0 все остальные (presumably the receiver"лейтенанты") would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been deliveredпросто принимают предложение.
Для недетерминнированного При f=1 все "лейтенанты" рассылают всем "лейтенантам" сообщение "генерал сказал X". Теперь у каждого процесса есть N- аналогично. Посмотрим на 1 сообщение вида "успешнуюA сказал, что генерал сказал X" последовательность, включая своё(Я сказал, что генерал сказал X).И отменим успешность последнего сообщенияВыбираем вариант, который встречается больше раз, или 0 если одинаково. Для Если сбойный процесс - генерал, то все остальные процессы получат одинаковое количество 0 и 1в сообщениях и выберут одинаковый вариант. Если сбойный процесс -ого лейтенант, все окостальные процессы получат больше верных сообщений, чем неверных и выберут вариант, посланный генералом. При f=2+ делаем всего f раундов рассылки сообщений между лейтенантами (при f=2 посылаются сообщения "B сказал, что A сказал, что генерал сказал X"), и f раундов выбора большинства внутри каждого процесса (т.е. для f=2процесс имеет N-ого все испортилось1 сообщение "B сказал, что А сказал ..." и решает, что именно сказал A выбором варианта, который больше встречается).
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
