7
правок
Изменения
→24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
Пусть в системе имеется ''n'' узлов, каждому задано начальное число.Пусть из них максимум ''f'' могут в любой момент упасть(crash).Тогда можно решить задачу консенсуса за ''f+1'' раундов: *Каждый Делаем в каждом узле вектор из ''n'' значений (своё записываем, остальные пока неизвестны)*В каждом раунде каждый узел посылает каждому свое число;все свои числа (или только те, которые не посылал ранее - без разницы)*Процессы запоминают записывают пришедшие числа;в свой вектор*Новые для себя После ''f+1'' - го раунда выбираем минимум из известных чисел. Почему это работает?Допустим, что процессы a и b выбрали разные минимумы. Значит, есть значение v, которое есть у одного из процессов и нет у другого(пусть есть у b). Но если у нас был раунд без сбоев, то все процессы узнают все имеющиеся в данный момент числа процессы рассылают дальше;*Каждый процесс выбирает минимально известное ему число- потому что все сообщения дошли. А сбоев было не больше f - противоречие.
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
