Способ принятия единого согласованного решения в распределенной системе ЭВМ Российский патент 2019 года по МПК G06Q99/00 G06N7/00 

Область техники, к которой относится изобретение

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

Глоссарий

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

Хеш - последовательность символов, формируемая с помощью применения математической функции, заключающейся в преобразовании входных данных произвольной длины в (выходную) строку установленной, меньшей длины. При любом изменении входных данных хеш этих данных будет отличаться от хеша неизменных входных данных.

Узел - ЭВМ, имеющая средства связи с другими ЭВМ, на которой исполняется программное обеспечение распределенной системы.

МТР - подтверждение дерева Меркла (Merkle Tree Proof). Деревом Меркла называют полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Подтверждение дерева Меркла - это одна ветка полного дерева Меркла блока, в котором есть информация только об одной транзакции (подтверждение которой и формируется), а все остальные вершины содержат лишь хеши от соседних веток. При предоставлении МТР, в случае верности всех хешей узлов и совпадении корневых хешей МТР и блока можно однозначно утверждать, что МТР является частью блока.

Валидный МТР - блок информации, который содержит МТР цифровые подписи более 50%+1 узлов системы.

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

Византийская задача (задача византийских генералов) - (англ. Byzantine fault tolerance (BFT), Byzantine agreement problem, Byzantine generals problem, Byzantine failure) - в криптологии задача взаимодействия нескольких удаленных абонентов, которые получили приказы из одного центра. Часть абонентов, включая центр, могут быть злоумышленниками. Нужно выработать единую стратегию действий, которая будет выигрышной для абонентов.

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

N,F (50%+1) - упрощенное обозначение соотношения количества неработающих узлов и всех узлов в распределенной системе. N обозначают общее количество узлов в распределенной системе, F - количество неработающих узлов. N=2F+1 и 50%+1 обозначают такую систему, где на F неработающих узлов приходится еще F+1 (50%+1) работающих. Асинхронные системы чаще всего описываются N=3F+1, что означает, что для нормальной работы системы на F неработающих узлов должно приходиться не менее 2F+1 работающих узлов.

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

Предлагаемые подмножества нового значения системы - запрос на изменение значения системы в части некоторого его подмножества. Например, в системах распределенных реестров это транзакция от клиента на изменение в каком-либо балансе.

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

Раунд системы - временной интервал, измеряемый от начала согласования нового значения системой, до окончания согласования нового значения системой.

Уровень техники

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

Большинство современных методов решения данной проблемы основывается на сформулированной задаче и путях ее решения, которые были описаны в статье «The Byzantine Generals Problem» вышедшей в журнале TOPLAS, Vol 4, No 3, в июле 1982 г.

Позже в статье «Practical Byzantine Fault Tolerance», вышедшей в феврале 1999 г.¹ (¹ Practical Byzantine Fault Tolerance, Appears in the Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, Laboratory for Computer Science, Massachusetts Institute of Technology, February 1999, Miguel Castro, Barbara Liskov.), был описан новый, более быстрый, способ, позволяющий находить решения этой задачи. На основе этого способа было создано множество прикладных реализаций методов согласований решений в распределенных системах. Этот способ предполагает временное разделение равноправных узлов системы на Primary (Ведущий узел) и replicas (узлы, хранящие копию состояния системы). Также в способе вводится понятие «View»: состояние системы в котором из всех имеющихся узлов один избран Primary. Очевидно, что Primary узел может выйти из строя, что приводит к созданию нового View с другим Primary. Все взаимодействия между узлами предполагается асинхронным.

Способ, описанный в статье, при условии, что в процессе View не меняется, описывается следующими шагами:

1. Клиент отправляет сообщение узлу Primary.

2. Primary присваивает этому сообщению следующий по очередности номер N и отправляет широковещательное сообщение PRE-PREPARE (предподготовка) всем replicas.

3. Получая сообщение PRE-PREPARE каждый узел из replicas проверяет его на соответствие текущему View и установленному на прошлом этапе N, и в случае успеха проверки отправляет всем узлам сообщение PREPARE (подготовка).

4. Получая сообщения PREPARE узел проверяет его на соответствие текущему View и N и имеющемуся у него сообщению PRE-PREPARE. В случае если узел получает соответствующее PREPARE сообщение от % узлов системы, он управляет всем узлам сообщение COMMIT (фиксация).

5. Получая сообщения COMMIT узел проверяет его на соответствие текущему View и N и имеющемуся у него сообщению PREPARE. В случае если узел получает соответствующее COMMIT сообщение от ²/₃ узлов системы, он выполняет сообщение клиента, меняя состояние системы и результат отправляет клиенту.

6. Клиент ожидает получение результата своего сообщения от узлов системы. Когда он получит от ¹/₃ узлов системы одинаковые сообщения, это и будет окончательный результатом обработки его запроса.

Недостатки данного способа:

1. Разделение узлов системы на обычные узлы и Primary узел привело к необходимости введения дополнительных шагов PRE-PREPARE и PREPARE для того, чтобы гарантировать работоспособность этого узла.

2. Из-за того, что все взаимодействия между узлами осуществляются асинхронно, то неизвестно конечное время получения клиентом результата работы системы, который он получает в пункте 6. Это связано с тем, что на 6 шаге, чтобы получить результат, клиент должен дождаться 1/3 ответов. Но если на этапах по 5 включительно еще можно выставить временные периоды, в которые должен выполниться той или иной этап, то в этап 6 такие периоды выставлять нет необходимости, так как от этого сама система не зависит. Таким образом, перед началом способа невозможно определить, в какое именно время клиент получит данные о том, что его запрос выполнен.

3. Клиенты передают запросы только текущему Primary узлу. Это означает, что в случае отключения данного узла, до назначения нового Primary система не будет работоспособна.

4. Разделение узлов системы на обычных узлов и Primary узел также приводят к возможности Primary узлом выполнять цензурирование запросов от клиентов, принимая от клиентов эти запросы, но не передавая далее.

5. Система может работать, только если в системе не более Уз узлов с Византийским поведением.

6. В системе должна присутствовать дополнительная подсистема, отвечающая за сбор и доставку к Primary на изменение значение системы от клиентов системы, что привносит дополнительные временные затраты.

11 сентября 2017 года вышла статья «Efficient Synchronous Byzantine Consensus»² (² Efficient Synchronous Byzantine Consensus, Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, Ling Ren, 2017.), в которой представлен еще один способ, который можно использовать для решения проблемы согласования решения в распределенных системах.

Способ, описываемый в статье, имеет в основе для каждого раунда взаимодействия четырехстадийный основной протокол:

1. <статус> каждый узел посылает сообщение лидеру этого раунда, в котором содержится текущее значение принятое узлом, номер раунда и подтверждающий сертификат из окончания предыдущего раунда (не менее F+1 <уведомление> или <фиксация> сообщений из прошлого раунда от других узлов системы)

В конце стадии лидер собирает не менее f+1 валидных сообщений <статус>, чтобы сформировать подтверждение состояния.

2. <предложение> Лидер этого раунда далее формирует новое значение, которое основывается на подтвержденном состоянии и рассылает всем узлам системы, в том числе себе.

В конце стадии любой узел при получении предложения нового значения от лидера проверяет его и проверяет подтверждение состояния лидера. Если проверка пройдена, то новое значение предлагается как новое состояние этого узла в этом раунде.

3. <фиксация> В случае если <предложение> лидера успешно прошло проверку в конце стадии 2, узел рассылает всем узлам системы свое решение о принятии предложения по новому значению в этом раунде <фиксация>, сопровождая его копией сообщения <предложение>.

В конце стадии, если узел получает два сообщения валидных <фиксация> но с разными значениями от лидера, значит лидер проявляет двойственное поведение. Если же узел получил f+1 сообщений от других узлов <фиксация> с одинаковым новым значением и при этом не получает информации о двойственном. поведении лидера, то он принимает это значение.

4. <уведомление> После того, как в конце стадии 3 узел принимает новое значение от лидера, он создает и рассылает <уведомление> об этом всем узлам системы.

В конце стадии, если узел получает <уведомление> от другого узла, он формирует сертификат нового значения (не менее f+1 <уведомление> или <фиксация> сообщений из прошлого раунда от других узлов системы). Если узел получает несколько валидных сообщений <уведомление>, он может выбрать для сертификата любое или ни одно из них.

Как видно из описания, этот способ похож на представленный в рамках статьи «Practical Byzantine Fault Tolerance». Однако в этом статье отдельное внимание обращается на то, что все действия, описанные в стадиях способа, происходят синхронно. Это позволяет сократить минимальные требования по количеству работоспособных узлов системы с ²/₃+1 для асинхронной системы (статья «Practical Byzantine Fault Tolerance») до ¹/₃+1 для синхронной системы (статья «Efficient Synchronous Byzantine Consensus»).

Способ, предложенный в статье «Efficient Synchronous Byzantine Consensus», устраняет многие недостатки которые были свойственны способу описанному в статье «Practical Byzantine Fault Tolerance». Для решения проблем с возможным назначением лидера из части поврежденных узлов, предлагается бороться постоянным перебором всех узлов. Таким образом, в среднем любое решение будет приниматься за 2 итерации раунда (8 стадий). Также предложено в случае если лидер выполняет все правила принятые для работы системы (честный лидер) не менять его, тогда 4 и 1 стадию можно исключить, получив 3 стадии на один раунд.

Недостатки этого способа:

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

2. Также в способе предложен еще один вариант оптимизации - при нахождении честного лидера не менять его. Однако в статье не описывается способ нахождения такого лидера, количество раундов на которые предлагается остановить выбор честного лидера (заморозка лидера) и способ смены лидерства. Все эти действия предлагается разработать самостоятельно. Что не позволяет напрямую использовать данную оптимизацию.

3. Выделение лидера, который формирует новое значение системы, и особенно предложенная оптимизация с заморозкой лидера, позволяет ему выполнять цензурирование запросов от клиентов, принимая от клиентов эти запросы, но не передавая далее. Это приводит к тому, что сколько бы отдельный клиент не отправлял запросы, они не выполняются. В то время как для большинства работа идет в нормальном режиме. Такая работа системы является существенным недостатком. Так, например, на практике, если такая система обеспечивает взаимодействие между магазинами и поставщиками, данный недостаток системы может привести к тому, что запросы от магазина А на допоставку редкого товара будут выполнены, а от Магазина Б не будут. В настоящее время данная уязвимость также используется на онлайн-аукционах, работающих по такой системе: одна ставка одного клиента пропускается и клиент выигрывает, а другая ставка другого клиента не пропускается и клиент в принципе не участвует в аукционе, даже если его ставка в действительности выигрышная.

4. В системе должна присутствовать дополнительная подсистема, отвечающая за сбор и доставку к лидеру на изменение значение системы от клиентов системы, что привносит дополнительные временные затраты.

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

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

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

Раскрытие изобретения

Начальные условия одинаковые для всех узлов, необходимые для того, чтобы система, состоящая из этих распределенных узлов, могла использовать данный способ:

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

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

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

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

- Система, состоящая из набора узлов, в зависимости от способа согласования результата, может работать при разном показателе количества вышедших из строя узлов или узлов с византийским поведением. В случае если количество таких узлов менее порога, система не сможет работать. Такой порог для реализации заявленного способа определяется по формуле N>=2F+1.

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

1. Первая стадия<начало раунда>. Каждый узел системы отправляет каждому узлу системы, в том числе и самому себе, по каналу передачи, сообщение о начале раунда. В этом сообщении передается предлагаемые узлом подмножества нового значения системы, номер нового раунда, и валидный МТР с номером предыдущего раунда и значение счетчика повтора раунда, если раунд хотя бы раз не был закончен.

Узлы для обработки на следующей стадии выбирают сообщения с максимальным номером предыдущего раунда. Если существуют варианты сообщения с одинаковым максимальным номером раунда но различным валидным МТР с номером предыдущего раунда, узел выбирает те сообщения, в которых указан максимальное значение счетчика повторов раунда.

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

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

2. Вторая стадия <конец раунда>. Каждый узел, из сообщений, отобранных на прошлой стадии, извлекает подмножества нового значения системы, записанных в них. Затем каждый такой узел сортирует эти подмножества одинаковым способом (способ сортировки не имеет значения, важно только чтобы способ сортировки был одинаковым на всех узлах). После этого узлы проверяют полученную последовательность подмножеств на возможность вычисления нового значения. При проверке подмножеств на возможность вычисления нового значения проверяется, можно ли провести вычисление исходя из заданных начальных условий и заданных операций с ними. Например, если есть начальное условие, что есть переменная равная 5, она должна быть строго больше нуля, а в операции предлагается вычесть 10 (обычная расходная операция, как финансовая, так и любая учетная), следовательно, невозможно вычислить новое значение, - операция не должна быть выполнена. Есть и более простые примеры, например, операция должна быть X/Y, a Y=0, следовательно, вычисление нового значения невозможно. Далее часть подмножеств, которые не могут быть выполнены (повторное подмножество, заведомо ложное подмножество, подмножество которое не может быть вычислено исходя из текущего значения), удаляются из списка подмножеств значения. Затем узел, вычисляет новое значение и рассылает всем узлам, в том числе и себе, сообщение, содержащее хеш нового значения, номер раунда и самое большое значение счетчика повторов раунда из выбранных сообщений и удостоверяющую цифровую подпись этого узла.

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

<провал раунда> Узел получил меньше 50% подписей хешей с одинаковым номером раунда и значением счетчика повторов раунда. Если узел оказался в такой ситуации, он увеличивает значение счетчика повторов раунда и начинает выполнять согласование нового значения раунда с самого начала.

<успех раунда> Узел получил больше 50% подписей хешей с одинаковым номером раунда и значением счетчика повторов раунда, и набралось 50%+1 одинаковых хешей. Согласование раунда считается успешным, и, следовательно, в распределенной системе принимается единое согласованное решение. Узел готов к началу выполнения нового раунда принятия решения в случае необходимости, значение счетчика повторов раунда узла устанавливается равным 0.

<провал раунда, требуется коррекция> Узел получил больше 50% подписей хешей с одинаковым номером раунда и значением счетчика повторов раунда, но не набралось 50%+1 одинаковых хешей. Такая ситуация сигнализирует о том, что появились узлы с византийским поведением, необходимо выявить такие узлы и закончить раунд. Для этого используем дополнительные стадии коррекции, приведенные ниже.

В случае если в системе присутствует хотя бы один узел с византийским поведением, он может на 1-й стадии рассылать остальным сообщения с различные подмножествами нового значения. Это приведет к тому, что ни один узел в системе не наберет 50%+1 одинаковых подписанных хешей нового значения, а значит, пока раунд не закончился согласованным решением по новому значению. Для того чтобы система в таком случае могла выработать согласованное значение, предлагается добавить стадии коррекции:

1. Первая стадия <начало коррекции>. Узел, который не получил 50%+1 одинаковых ответов на стадии <конец раунда> создает сообщение, содержащее номер текущего раунда и сообщения полученные им от других узлов на стадии <начало раунда>, содержащие предлагаемые узлом подмножества нового значения системы, номер нового раунда, и валидный МТР с номером предыдущего раунда. Далее узел отправляет такое сообщение каждому узлу.

2. В случае, если в системе существует один или несколько узлов, которые собрал 50%+1 одинаковых цифровых подписей на стадии <конец раунда>, то такие узлы передают ответное сообщение узлам, которые не получили 50%+1 одинаковых ответов на стадии <конец раунда> и эти узлы начинает синхронизацию с новым значением системы.

3. В том случае, если ни один из узлов системы не собрал 50%+1 одинаковых цифровых подписей на стадии <конец раунда>, то на каждом работающем узле собирается общая матрица сообщений, содержащая информацию обо всех отправленных каждым из узлов каждому из узлов сообщений. Каждый узел, анализируя общую матрицу сообщений, определяет узлы, пославшие сообщения с различными подмножествами значения в этом раунде (узлы с византийским поведением).

4. <конец коррекции> Каждый узел исключает из рассмотрения на этой стадии сообщения <начало раунда> полученных от узлов, определенных как (узлы с византийским поведением) и далее повторяет стадию <конец раунда>.

При использовании заявляемого способа обеспечивается возможность достижения согласования нового значения системы при неработающих 50%+1 узлах за 2 стадии, при наличии в раунде узлов с византийским поведением за 4 стадии. Благодаря тому, что клиент может предложить свое изменение значение системы любому из узлов системы, при этом не ограничивая количеством таких предложения в одном раунде, достигается невозможность цензурирования. Также в связи с этим отсутствует необходимость в создании дополнительной подсистемы для хранения и передачи заявок от клиентов в систему.

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

Аукцион с использованием заявляемого способа происходит следующим образом:

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

Аукцион начинается с того, что один или несколько участников предлагают выставить лот на аукцион. В случае одновременного выставления лотов первым предлагается к аукциону лот с меньшей начальной ценой.

Работа аукциона происходит раундами. Каждый раунд участник может как предложить свое действие для совершения в этом раунде, так и не предложить.

В начале раунда все участники через свои узлы рассылают остальным участникам подписанное сообщение со своим предложением, если предложения нет, посылается сообщение с предложением "нет предложения".

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

1. есть победитель раунда - предложивший на этом раунде лучшую цену

2. никто не предложил лучшую цену и счетчик раунда до выигрыша больше 0

3. никто не предложил лучшую цену и счетчик раунда до выигрыша равен 0

После выяснения результата раунда узел отправляет его в подписанном сообщение всем другим участникам. В случае если узел получил от более 50% участников одинаковый результат, участник считает этот раунд законченным и переходит к работе над следующим раундом.

Что касается логики работы в определении победителя лота, она представлена на чертеже.

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

Кроме этого, данный способ может применяться для создания обычных интернет сервисов повышенной надежности. Например, облачных систем, блокчейн платформ или платформ распределенных реестров.

Изобретение относится к области обработки цифровых данных с помощью электрических устройств, в частности к методам принятия единого согласованного решения в компьютерных системах, автоматически выбирающим оптимальный режим работы для достижения заданного критерия. Способ может применяться в любых распределенных системах, в которых необходимо согласованное совместное действие. Технический результат заключается в оптимизации порядка согласования общего решения между независимыми равноправными автоматическими (компьютеризированными) центрами, необходимого для получения согласованного результата раунда в распределенной сети. Способ принятия единого согласованного решения в распределенной системе ЭВМ заключается в том, что каждый узел отправляет всем узлам сообщение о начале раунда, затем каждый узел вычисляет новое значение и рассылает его всем узлам, а если новое значение не вычислено, то узлы анализируют общую матрицу сообщений и исключают сообщения от выявленных узлов с византийским поведением, после чего вычисляют новое значение и принимают решение. 1 ил.

Способ принятия единого согласованного решения в распределенной системе ЭВМ (узлов), в которой все взаимодействия по передаче и получению информации между узлами устанавливаются как синхронные, при этом каждый узел системы имеет возможность обмениваться информацией по каналам передачи данных с каждым другим узлом системы, каждый узел системы имеет информацию о каждом другом узле системы (адрес в системе связи между узлами, обеспечивающей передачу данных между узлами, публичный ключ для идентификации узла в системе), позволяющую каждому узлу связываться через канал передачи данных с каждым другим узлом, входящим в систему, каждый узел системы имеет информацию о каждом другом узле системы, позволяющую каждому узлу с помощью криптографии однозначно идентифицировать принадлежность цифровой подписи информационного сообщения какому-либо из узлов системы, а пороговый показатель количества вышедших из строя узлов или узлов с византийским поведением, при котором система не сможет принять единое согласованное решение с использованием заявляемого способа, соответствует формуле N>=2F+1, где N обозначают общее количество узлов в распределенной системе, a F обозначает количество неработающих узлов,

отличающийся тем, что содержит:

- этап первой стадии <начало раунда>, на котором каждый узел системы отправляет каждому узлу системы, в том числе и самому себе, по каналу передачи, сообщение о начале раунда, содержащее предлагаемые узлом подмножества нового значения системы, номер нового раунда, валидный МТР с номером предыдущего раунда и значение счетчика повтора раунда, если раунд хотя бы раз не был закончен, при этом узлы для обработки на следующей стадии выбирают сообщения с максимальным номером предыдущего раунда, а если существуют варианты сообщения с одинаковым максимальным номером раунда, но различным валидным МТР с номером предыдущего раунда, узлы выбирают те сообщения, в которых указано максимальное значение счетчика повторов раунда, в результате чего, в случае, если отсутствуют узлы с византийским поведением, каждый работающий узел получает одинаковое количество сообщений о начале раунда с новым номером раунда от других узлов, а в том случае, если в системе присутствуют узлы с византийским поведением, то от такого узла другие узлы получают сообщение с номером раунда, меньшим, чем номер нового раунда у него, при этом в таком случае узел, получивший от другого узла сообщение с номером раунда, меньшим, чем номер нового раунда у него, отправляет в ответ этому узлу валидный МТР с номером предыдущего раунда, сохраненного в базе данных этого узла;

- этап второй стадии <конец раунда>, на котором каждый узел из сообщений, полученных от других узлов и отобранных на прошлой стадии, извлекает подмножества нового значения системы, записанные в них, после чего выбирает из предлагаемых другими узлами подмножеств нового значения системы подмножества с максимальным номером раунда, затем каждый такой узел сортирует эти подмножества одинаковым способом, после чего узлы проверяют полученную последовательность подмножеств на возможность вычисления нового значения, после чего часть подмножеств, которые не могут быть выполнены, удаляются из списка подмножеств значения, а затем каждый узел вычисляет новое значение и рассылает всем узлам, в том числе и себе, сообщение, содержащее хеш нового значения, номер раунда, самое большое значение счетчика повторов раунда из выбранных сообщений и удостоверяющую цифровую подпись этого узла, после чего в результате этой стадии каждый узел накапливает у себя сообщения от всех узлов системы, содержащие хеш нового значения, номер раунда и значение счетчика повторов раунда, после чего в том случае, если любой из узлов получил меньше 50% подписей хешей с одинаковым номером раунда и значением счетчика повтора раунда, то такой узел увеличивает значение счетчика повтора этого раунда на одну единицу и начинает выполнять согласование нового значения раунда с самого начала, в том случае, если любой из узлов получил больше 50% подписей хешей с одинаковым номером раунда и значением счетчика повтора раунда и набралось (50%+1) одинаковых хешей, то согласование раунда считается успешным, и, следовательно, в распределенной системе принимается единое согласованное решение, а в том случае, если любой из узлов получил больше 50% подписей хешей с одинаковым номером раунда и значением счетчика повторов раунда, но не набралось (50%+1) одинаковых хешей, то, следовательно, в системе присутствуют узлы с византийским поведением, и для того, чтобы выявить такие узлы и закончить раунд, переходят к дополнительному этапу первой стадии <начало коррекции>;

- дополнительный этап первой стадии <начало коррекции>, который происходит в том случае, если хотя бы один из узлов не получил (50%+1) одинаковых ответов на стадии <конец раунда>, на котором узел, который не получил (50%+1) одинаковых ответов от других узлов на стадии <конец раунда>, создает сообщение, содержащее номер текущего раунда, и сообщения, полученные им от других узлов на стадии <начало раунда>, содержащие предлагаемые узлом подмножества нового значения системы номер нового раунда и валидный МТР с номером предыдущего раунда, после чего такой узел отправляет такое сообщение каждому узлу, после чего в случае, если в системе существует один или несколько узлов, которые собрали (50%+1) одинаковых цифровых подписей на стадии <конец раунда>, то такие узлы передают ответное сообщение узлам, которые не получили (50%+1) одинаковых ответов на стадии <конец раунда>, и эти узлы начинают синхронизацию с новым значением системы, а в том случае, если ни один из узлов системы не собрал (50%+1) одинаковых цифровых подписей на стадии <конец раунда>, то на каждом работающем узле собирается общая матрица сообщений, содержащая информацию о всех отправленных каждым из узлов каждому из узлов сообщений и каждый узел, анализируя общую матрицу сообщений, определяет узлы с византийским поведением, пославшие другим узлам сообщения с различными подмножествами значения на стадии <начало раунда>;

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