«Задача о византийских генералах». Протокол «византийского соглашения». Обеспечение безопасности распределенных вычислений

From CryptoWiki
Jump to: navigation, search

Агибалова А.В.

Зеленова А.И.

Назад

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

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

Contents

Задача о византийских генералах

Надежные вычислительные системы должны сохранять работоспособное состояние даже при отказе одного или нескольких узлов. В рамках данной статьи будем подразумевать под признаком неполадок состояние, в котором узел посылает противоречивую информацию по разным направлениям. Образно задача может быть описана следующим образом:

Византия. В ночь перед великим сражением, Византийская армия содержит n легионов. Каждый из них подчиняется своему генералу. У всей византийской армии есть главнокомандующий, руководящий генералами. Империя находится в упадке и среди генералов, включая главнокомандующего, могут быть предатели. В течение всей ночи, каждый из генералов получает от предводителя приказ о действия на утро. Это может быть один из двух вариантов «атаковать» или «отступать». Если все честные генералы атакуют - они одержат победу. Если все отступят - им удастся сохранить армию. Если часть атакуют, а часть отступят - они терпят поражение. Если главнокомандующий предатель, он может дать разным генералам разные приказы, следовательно, его приказы не стоит выполнять беспрекословно. Если же каждый генерал будет действовать независимо от других, результаты битвы также могут быть плачевными. Поэтому генералы нуждаются в обмене информацией друг с другом, чтобы прийти к соглашению.

Определение

Есть n генералов. Связь между ними осуществляется посредством надежной связи (например, телефон). Из n генералов m являются предателями и пытаются воспрепятствовать соглашению между лояльными генералами. Согласие заключается в том, чтобы все лояльные генералы узнали о численности всех лояльных армий и пришли к одинаковым выводам (путь и ложным) относительно состояния предательских армий. (Последнее условие важно, если генералы на основании полученных данных планируют выработать стратегию и необходимо, чтобы все генералы выработали одинаковую стратегию)

Что в итоге?

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

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

Шаг 1: Каждый из генералов посылает остальным сообщение, где указывает численность своей армии. Предатели могут указать различные числа в разных сообщениях, а лояльные указывают истинное количество. Генерал g1 указал 1 (тысяча воинов), генерал g2 - 2, генерал g3 соответственно указал трем остальным генералам x, y, z, генерал g4 - 4. Шаг 2: Каждый из генералов вычисляет свой вектор из информации, полученной от остальных генералов. Получается: vect1 (1,2,x,4), vect2 (1,2,y,4), vect3 (1,2,3,4), vect4(1,2,z,4). Шаг 3: Генералы посылают свои вектора другим. Генерал g3 вновь посылает произвольные значения. Получаются следующие векторы:

Example1.jpg

Шаг 4: Каждый из генералов проверяет каждый элемент в полученных векторах. В том случае, если одно значение совпадает как минимум в двух векторах, оно помещается в результирующий вектор, в противном случае, соответствующий элемент помечается как «неизвестен». В итоге все генералы получат один вектор (1,2, неизвестен, 4). Следовательно, согласие достигнуто. Для n=3 и m=1 согласие достигнуто не будет.

Проблема византийских генералов в системе взаимной проверки знаний

Проблема византийских генералов возникает в системе взаимной проверки знаний, если учащийся дает верный ответ на свое задание, но при проверке других, оценки ставит произвольно. Этот учащийся (далее, вершина) является враждебной. Эта ситуация может привести к неправильной расшифровке синдрома. Основой модели системы взаимных проверок является принцип распределенного ядра. Согласно нему, диагностическое ядро системы неизвестно заранее и определяется основывая на результаты взаимных проверок, куда включаются учащиеся, которые правильно ответили на вопрос и правильно оценили другие ответы (надежные). [АП05]

Продолжение...

Протокол византийского соглашения

При византийских соглашениях или при реализации протокола византийских соглашений для любого начального входа xi, i∈[1,...,n] участника i и некоторого параметра d (соглашения) должны быть выполнены следующие условия:

1. Условие завершения. Все честные участники вычислений в конце протокола принимают значение d.

2. Условие корректности. Если существует значение x такое, что для честных участников xi=x, тогда d=x.

«Задача византийского соглашения» формулируется на основе «задачи о византийских генералах»: для n взаимодействующих генералов нужно предложить такой протокол взаимодействия, чтобы при наличии среди них m «нелояльных» генералов остальные генералы – «лояльные», – имея каждый свое мнение, всегда вырабатывали согласованную общую позицию (например, штурмовать крепость или нет).

Продолжение...

Обеспечение безопасности распределенных вычислений

В настоящее время быстро развиваются сетевые технология, на рынке появляются современные коммуникационные оборудования, ЛВС (локальные вычислительные сети) масштабируются и растут. Конечному пользователю довольно легко приобрести коммуникационное оборудование и завести свою собственную локальную сеть. Активно растут сети предприятий среднего и крупного бизнеса. Быстро развиваются каналы связи компаний Интернет-провайдеров. С увеличением сетей и каналов связи (локальных и глобальных) проблема защиты информации, которая в ней циркулирует и подвергается обработке, становится еще более актуальной. Обеспечение конфиденциальности, аутентификации, целостности, контроля доступа, причастности становится необходимым. Намного активней на коммерческом рынке стали появляться компании, которые предоставляют такие услуги, как разработка, внедрение и сопровождение аппаратных, программных и программно-аппаратных средств ЗИ (защиты информации). Так как часть рынка по разработке, внедрению и сопровождению комплексных концептуальных решений ЗИ, остается пустой, но более востребованной, необходимо рассмотреть подходы к решению данных вопросов.[ДЯ94]

Распределенные вычисления

Распределённые вычисления применимы в распределенных системах управления. Последовательные вычисления в распределённых системах выполняются с учётом одновременного решения многих задач. Особенностью распределенных многопроцессорных вычислительных систем, в отличие от локальных суперкомпьютеров, является возможность неограниченного наращивания производительности за счет масштабирования. Слабосвязанные, гетерогенные вычислительные системы с высокой степенью распределения выделяют в отдельный класс распределенных систем — грид.

Продолжение...

Принципы создания защищенных систем связи в распределенных вычислительных системах

На рисунке 1 показана сетевая топология "Общая шина".

Рисунок 1. Сетевая топология "общая шина"

Можно выделить два способа построения топологии РВС с выделенными каналами.

Первый случай:

Рисунок 2: Сетевая топология "N-объектов - N-каналов"

Каждый из объектов объект связывается с помощью физических линий связи со всеми объектами системы (рис. 2).

Второй случай:

Рисунок 3: Сетевая топология "звезда"

В системе можно использовать сетевой концентратор, посредством которого осуществляется связь между объектами (топология "звезда" - рис. 3).

Преимущества РВС:

- передача сообщений осуществляется между источником и приемником напрямую, обходя остальные объекты системы. Если нет доступа к объектам, которые помогают осуществить передачу сообщений, то программная возможность для анализа сетевого трафика отсутствует;

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

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

Минусы РВС:

- сложно реализовать и большие затраты на создание такой системы;

- число объектов системы ограничено системы (это зависит от количества входов у концентратора);

- сложно внести в систему нового объекта.

Протокол византийского соглашения в распределенных вычислениях

Существует две модели отказов процессора в РВС:

• Модель отказа «Остановка» - процесс просто останавливается без предупреждения.

• Византийская модель отказа - неисправные процессы ведут себя неопределенным образом.

Византийские отказы предназначены для моделирования любого типа неисправностей, в том числе отказов отдельных компонентов процессоров. Термин «Византийский» был впервые использован в знаковом докладе Лампорта, Пиза и Шостака для такого типа сбоев, в котором в терминах византийских генералов формулируется проблема консенсуса.

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


Продолжение...

Связь между проблемами остановки и византийского соглашения

Алгоритм, реализующий византийское соглашение автоматически решает проблему соглашения для отказа остановкой. Это не совсем верно. Разница заключается в том, что в случае остановки требуется, чтобы все решающие процессы, даже отказавшие, должны согласиться. В случае, если условие соглашения для отказа остановкой заменяется аналогичным для византийского отказа, смысл сохраняется. Кроме того, если все рабочие процессы в византийском алгоритме всегда решают одинаково, то алгоритм работает также и для «остановки».

Византийское соглашение с идентификацией

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

Неисправному процессу разрешается отправлять произвольные сообщения и выполнять произвольные переходы между состояниями. Единственное ограничение заключается в том, что он не в состоянии генерировать подписи исправных процессов или источника.

Условия правильности, которые должны удовлетворяться в этой модели являются обычными условиями соглашения и завершения византийского договора Действительность: если все процессы запускаются только с одним начальным значением vϵV, подписанным источником, то v является единственно возможным решением для исправных процессов.

Протоколы византийского соглашения

В этом разделе представляются алгоритмы византийского соглашения, для случая полного графа с n вершинами. Первый из них использует экспоненциальный сбор информации (ЭСИ) алгоритм византийского соглашения с ограниченной коммуникационной сложностью описывается позже. Общее свойство этих алгоритмов заключается в том, что количество процессов, которые они используют, превышает число отказов более чем в три раза, n>3f. Эта связь процессов отражает дополнительные трудности, возникающие в византийской модели отказов. Можно догадаться, что 2f+1-процессов могут противостоять f византийским неисправностям, используя алгоритм голосования большинства. (Существует стандартная отказоустойчивая техника, известная как тройное резервирование, в которой задача утроена и принимаются результат большинства; можно подумать, что этот метод может быть использован для решения византийского соглашения для сбоя одного процесса, но это не так.)

Протокол византийского соглашения с ЭСИ

ЭСИВиз предполагает, что количество процессов больше количества недостатков, в частности, что n>3f. В ЭСИВиз алгоритм для n процессов с f сбоями использует древовидную структуру данных ЭСИ.

Описание алгоритма: Процессы передают значения для f + 1 раундов со следующими исключениями. Если процесс i когда-либо получит сообщение от другого процесса j, имеющее не установленную форму (напр., в нем содержится случайная информация или повторяющиеся значения для одного узла на дереве j), то i "выбрасывает" сообщение, т.е. действует так, как если бы процесс j не отправлял ничего в этом раунде. В конце f + 1 раундов, процесс i регулирует значение val так, что любое null-значение заменяется на значение по умолчанию v0.


Продолжение...

Общее византийское соглашение с использованием двоичного византийского соглашения

В этом подпункте показывается, как использовать алгоритм, решающий проблему византийского соглашения с входными данными {0, 1}, как подпрограмму при решении общего византийского соглашения. Накладные расходы - всего 2 дополнительных раунда, 2n2 дополнительных сообщений, и O(n2b) бит пересылаемой информации. Это может привести к существенной экономии количества пересылаемых битов, которые должны быть сообщены, поскольку это не является необходимым для передачи значений в V. Это улучшение, однако, не достаточно для уменьшения количества бит связи от экспоненциального до полиномиального количества f.

Алгоритм Турпин-Коан

Турпин-Коан - алгоритм, названный в честь его разработчиков. Он допускает, что n>3f. Как и ранее, будем считать, что каждый процесс может посылать сообщения как себе, так и другим процессам.

Каждый процесс имеет локальные переменные x, y, z и голос (решение процесса), где x инициализируется как входное значение процесса, а y, z и голос инициализируются произвольно.

Раунд 1: Процесс i посылает свое значение х всем процессам, включая себя. Если в наборе сообщений, полученных на этом раунде, присутствует ≥ n- f копий значения vϵV, тогда i устанавливает y:=v; иначе y:=null. [L00]

Продолжение...

Глоссарий

Библиографический указатель

Перейти к списку литературы.