Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

И. В. АШАРИНА, Kyaw Kyaw Khine

Московский государственный институт электронной техники
(технический университет), Зеленоград, Москва

АЛГОРИТМЫ ПОЛУЧЕНИЯ СОГЛАСОВАННЫХ ЗНАЧЕНИЙ В ДВУХКОМПЛЕКСНОЙ СИСТЕМЕ

Данная работа посвящена разработке алгоритмов согласования значений в двухкомплексных системах.

Задача получения согласованного значения является одной из важнейших при построении многомашинных вычислительных систем (МВС), в которых единственным средством взаимодействия между ЦВМ служит обмен сообщениями [1]. Существует ряд решений этой проблемы [1, 3], основанных на многораундовых обменах сообщениями между ЦВМ с последующим анализом полученных сообщений и вычислением согласованных значений в каждой ЦВМ. Однако, разработанные методы применяются для однокомплексных систем.

Комплексом называется группа ЦВМ, выполняющих копии одной и той же задачи. Многокомплексная МВС (МКС) – это отказоустойчивая МВС, в которой разными комплексами одновременно выполняются несколько прикладных задач [2]. Назовем комплексом согласования группу ЦВМ, образующую граф, полносвязный или гомеоморфный полносвязному, и выполняющую задачу согласования. Под МКС будем подразумевать МВС, каждый комплекс согласования которой выполняет внутрикомплексное согласование, обменивается полученными результатами с другими комплексами согласования данной системы и вычисляет согласованное значение МВС.

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

НЕ нашли? Не то? Что вы ищете?

Предварительное условие получения согласованных значений в МКС: все исправные ЦВМ комплекса-источника в количестве, не меньшем, чем n =3m+1, передают одинаковое значение, которое назовем значением комплекса-источника. Условия достижения ВИС:

У1) при межкомплексном обмене все исправные ЦВМ комплекса-источника информации передают одинаковые согласованные значения всех исправных ЦВМ комплекса-источника информации;

У2) согласованное значение в комплексе-приемнике должно быть равно согласованному значению в комплексе-источнике.

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

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

Выполняется алгоритм согласования в полносвязном комплексе-приемнике для согласования значений, полученных в результате МКО от комплекса-источника.

Для получения согласованного значения в комплексе-приемнике возможно использование одного из алгоритмов (сценариев):

А1: Мажорирование полученных в результате МКО согласованных значений комплекса-источника в каждой ЦВМ комплекса-приемника.

А2: МКО; обмен сообщениями внутри одного комплекса (внутри-комплексный обмен, ВКО), полученных в результате МКО согласованных значений комплекса-источника; мажорирование результатов ВКО в каждой ЦВМ комплекса-приемника.

А3: МКО; мажорирование полученных в результате МКО согласованных значений; ВКО; мажорирование полученных в результате ВКО согласуемых значений.

А4: МКО; каждая ЦВМ комплекса-приемника формирует вектор значений, полученных от ЦВМ комплекса-источника; ВКО; мажорирование полученных в результате ВКО согласуемых значений; сравнение результатов мажорирования с каждым из полученных элементов; при получении несовпадающих значений результатов мажорирования со значениями вектора формируется область подозреваемых неисправных ЦВМ; удаляем из рассмотрения значения, связанные с ЦВМ, принадлежащим области подозреваемых неисправных ЦВМ.

Список литературы

1. Pease M., Shostak R. Lamport L. Reaching agreement in presence of faults// J. ACM. 1980, V.27, № 2, p.228-234.

2. , , Соболев локализации "дружественных" неисправностей // АиТ. 1992, № 5, с. 126-138.

3. , , Трахтенгерц методы обеспечения взаимной информационной согласованности в распределенных вычислительных системах // АиТ. 1989, № 5, с. 3-18.