Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вопрос 15. Задача византийских генералов — в вычислительной технике мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае





Задача византийских генералов — в вычислительной технике мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет.

Определение.

N «синих» генералов возглавляют армии в горах и готовятся атаковать «зелёных» в долине. Для связи атакующие используют надёжную связь (например, телефон). Однако, из n генералов m являются предателями и активно пытаются воспрепятствовать согласию лояльных генералов. Согласие состоит в том, чтобы все лояльные генералы узнали о численности всех лояльных армий.

Формализация.

Каждый из генералов должен получить один и тот же вектор длины n, в котором i-й элемент либо содержит численность i-й армии (если её командир лоялен) либо не определён (если командир — предатель).

Алгоритм решения.

Соответствующий рекурсивный алгоритм был предложен в 1982 г. Лесли Лампортом.

Проиллюстрируем его для случая n =4 и m =1. В этом случае алгоритм осуществляется в 4 шага.

1-ый шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал-1 указал число 1 (одна тысяча воинов), генерал-2 указал число 2, генерал-3 (предатель) указал трем остальным генералам соответственно x, y, z, а генерал-4 указал 4.

2-ой шаг. Каждый формирует свой вектор из имеющейся информации.

Получается:

vect1 (1,2,x,4)

vect2 (1,2,y,4)

vect3 (1,2,3,4)

vect4 (1,2,z,4)

3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опять произвольные значения).

Генералы получают следующие вектора:

g1 g2 g3 g4
(1,2,y,4) (1,2,x,4) (1,2,x,4) (1,2,x,4)
(a,b,c,d) (e,f,g,h) (1,2,y,4) (1,2,y,4)
(1,2,z,4) (1,2,z,4) (1,2,z,4) (i,j,k,l)


4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестен.

Все лояльные генералы получают один вектор (1,2,неизвестен,4) — согласие достигнуто.

Результат исследования.

Лампорт доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).

Другие авторы доказали, что в распределённой системе с асинхронными процессорами и неограниченными коммуникационными задержками согласия невозможно достичь даже при одном неработающем процессоре (даже если он не подаёт признаков жизни).


Вопрос 16.







Дата добавления: 2015-04-19; просмотров: 585. Нарушение авторских прав; Мы поможем в написании вашей работы!




Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Дезинфекция предметов ухода, инструментов однократного и многократного использования   Дезинфекция изделий медицинского назначения проводится с целью уничтожения патогенных и условно-патогенных микроорганизмов - вирусов (в т...

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

Тема 5. Организационная структура управления гостиницей 1. Виды организационно – управленческих структур. 2. Организационно – управленческая структура современного ТГК...

Методы прогнозирования национальной экономики, их особенности, классификация В настоящее время по оценке специалистов насчитывается свыше 150 различных методов прогнозирования, но на практике, в качестве основных используется около 20 методов...

Методы анализа финансово-хозяйственной деятельности предприятия   Содержанием анализа финансово-хозяйственной деятельности предприятия является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих...

Studopedia.info - Студопедия - 2014-2025 год . (0.011 сек.) русская версия | украинская версия