292
правки
Изменения
→25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
* [[Асинхронные и синхронные распределённые системы]]* [[Проблема византийских генералов - прийти к нетривиальному консенсусу N процессам, если среди них есть f сбойных(могут вести себя как угодно/контролируются злоумышленниками).]]* [[Алгоритм Лампорта(и еще 2 человек):Считаем, что у процессов есть номера. Процесс 1 - "генерал" Шостака- рассылает всем предложение - 0 или 1. И после этого молчит(принимает своё предложение). При f=0 все остальные ("лейтенанты") просто принимают предложение. При 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 выбором варианта, который больше встречается). Если же все процессы равноправные, то в 0 раунде рассылки все считают себя "генералами", а потом делаем консенсус на исходных значениях каждого. Выбор варианта в конечном итоге даст правильный вариант именно потому, что N > 3f.решения проблемы
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
