автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Алгоритмы голосования для мультиверсионных информационно-управляющих систем

На правах рукописи

003055Т8Э

Морозов Владимир Андреевич

АЛГОРИТМЫ ГОЛОСОВАНИЯ ДЛЯ МУЛЬТИВЕРСИОННЫХ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

05.13.01 - Системный анализ, управление и обработка информации

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2007

003055789

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», г. Красноярск

Научный руководитель: доктор технических наук, профессор

Антамошкин Александр Николаевич Официальные оппоненты: доктор технических наук, профессор

Терсков Виталий Анатольевич

кандидат технических наук, доцент Зеленков Павел Викторович

Ведущая организация: Государственный научно-исследовательский

институт информационных технологий и телекоммуникаций «Информика», г. Москва

Защита состоится 20 апреля 2007 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете им. академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, просп. им. газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в научной библиотеке Сибирского государственного аэрокосмического университета.

Автореферат разослан «_ » марта 2007 г.

Ученый секретарь диссертационного совета

И.В. Ковалев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Предмет диссертационного исследования - принятие решений при мультиверсионном исполнении ИУС с использованием алгоритмов голосования.

Целью диссертационной работы является повышение достоверности принятия решений при мультиверсионном исполнении ИУС с использованием алгоритмов голосования.

Для достижения поставленной цели решались следующие задачи:

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

• Сравнительный анализ применяемых в настоящее время алгоритмов голосования.

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

• Анализ специфики применения алгоритмов голосования в мультиверсионном программном обеспечении ИУС.

• Повышение достоверности принятия решений при мультиверсионном исполнении ИУС путём модификации алгоритмов голосования и разработки методики комплексного применения алгоритмов.

• Реализация результатов исследования в программной среде исполнения мультиверсионных систем.

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

Научная новизна работы.

1. Впервые предложена классификация наиболее распространённых и универсальных алгоритмов голосования в мультиверсионном программном обеспечении и определены условия успешного применения алгоритмов.

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

3. Предложены методы оценки достоверности голосования в зависимости от значения А.-сечения и в зависимости от алгоритма голосования; методы основаны на введении дополнительных критериев, таких, как: разброс в выбранных выходах, относительное количество согласных версий.

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

5. Разработана методика комплексного применения алгоритмов голосования с возможностью формализованного выбора окончательного результата из множества результатов применённых алгоритмов.

Реализация результатов работы.

Были разработаны четыре программные системы по исследуемой проблематике. Основные разработки описаны в четвёртом разделе диссертации. Программные системы прошли экспертизу и зарегистрированы в Отраслевом фонде алгоритмов и программ (ОФАП), что делает их доступными широкому кругу специалистов по системному анализу и проектировщиков программного обеспечения систем управления и обработки информации. Перечень зарегистрированных программных разработок приведен в конце автореферата.

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

• X Международная научная конференция «Решетневские чтения» (Красноярск, 2006);

• V Международная научно-практическая конференция «Информационные технологии и математическое моделирование» (Томск, 2006);

• Международная научная конференция с международным участием «Проблемы передачи и обработки информации» (Дубай, ОАЭ, 2006);

• Международная научно-практическая конференция «Фундаментальные и прикладные исследования высшей школы» (Сингапур, 2007);

• Державинские чтения (Тамбов, 2007).

Диссертационная работа в целом обсуждалась на научных семинарах Сибирского государственного аэрокосмического университета, а также НИИ Систем управления, волновых процессов и технологий (2005-2007 гг.).

На защиту выносятся:

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

2. Методы оценки достоверности голосования в зависимости от значения Х-сечения и в зависимости от алгоритма голосования.

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

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

Публикации. По теме диссертационной работы опубликовано 12 печатных работ. Перечень публикаций представлен в конце автореферата.

Структура и объём работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка использованной литературы из 120 наименований и двух приложений. Объем диссертационной работы 124 страницы, приложений - 10 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рисунок 1 - Модель мультиверсионной программной системы

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

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

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

1) алгоритм голосования абсолютным большинством (N-version programming with majority voting, NVP-MV);

2) алгоритм голосования согласованным большинством (N-version programming with consensus voting, NVP-CV);

3) нечёткий алгоритм голосования абсолютным большинством (Fuzzy majority voting);

4) нечёткий алгоритм голосования абсолютным большинством (Fuzzy consensus voting);

5) алгоритм голосования абсолютным большинством с минимизацией (minMV);

6) алгоритм голосования согласованным большинством с минимизацией (minCV);

7) формализованный алгоритм голосования абсолютным большинством (Formalized majority voting, FMV);

8) формализованный алгоритм голосования согласованным большинством (Formalized consensus voting, FCV);

9) «максимально вероятное» голосование (Maximum likelihood voting);

10) усреднённое голосование.

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

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

Неформализованные алгоритмы голосования можно разделить на три группы:

1 группа. Классические.

2 группа. Нечёткие

3 группа. С минимизацией.

Рисунок 2 - Классификация алгоритмов голосования

(1)

Алгоритмы первой группы отличаются следующими свойствами: Свойство 1. В основе принятия решения лежит построение матрицы согласования (agreement matrix). Матрица согласования представляет собой булеву матрицу размерностью NxN (где N - число версий). Матрица согласования отражает эквивалентность каждого выхода к другим выходам. Элементы матрицы согласования вычисляются по следующему принципу:

jl, при — Xj| < S,

,J [о, при |х,-xJ>E.

Здесь гц — элемент матрицы согласования в i-той строке и j-том столбце, х, и Xj -выходы, проверяемые на эквивалентность, s - допустимое отклонение.

Свойство 2. К матрице согласования R предъявляется следующее дополнительное требование: на R должно быть выполнено отношение эквивалентности (2.а),(2.б),(2.в).

(рефлексивность) r„ = 1 Vi, (2.а)

(симметричность) ry = г,, Vi*j, (2.6)

(транзитивность) если r,k=l и rkj=l, то гц=1 Vij. (2.в)

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

R'=R°R; r', = e(r4®ij, (3)

Гц - элементы матрицы согласования R;

г',, - элементы матрицы R', полученной из R одним шагом булевых композиций; © - функция логического «или»; ® - функция логического «и»; N - число версий.

Если после первой булевой композиции отношение эквивалентности не выполнено необходимо выполнить вторую R" = RuR', и так далее пока отношение (2.а),(2.б),(2.в) не будет выполнено. Доказано, что не более чем за N-1 композиций отношение будет выполнено.

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

Свойство 1. В основе принятия решения лежит построение отношения подобия {similarity relation) и матрицы согласования. Отношение подобия представляет собой матрицу размерностью NxN (где N-число версий). Отношение подобия описывает похожесть каждого выхода на остальные. То есть элементами отношения подобия являются значения мер подобия (similarity measure). Значение меры подобия двух выходов всегда лежит в диапазоне от нуля до единицы включительно (0 < s(x„xj) < 1). Элементы отношения подобия вычисляются следующим образом:

х,-х I |

1--при X — X, <8,

s(x„Xj) = е Р I 1 J! (4)

О, при jx^xjse.

Здесь s(x!,xj) - элемент отношения подобия в i-той строке и j-том столбце (значение меры подобия выходов х, и х,), £ - допустимое отклонение. На основе отношения подобия должна быть построена матрица согласования. Матрица согласования представляет собой булеву матрицу размерностью NxN. Матрица согласования должна быть получена из отношения подобия посредствам применения операции ^.-сечения (X-cut operation). Операция ^-сечения преобразует отношение подобия S в булеву матрицу согласования R, элементы которой равны 0 или 1. Если дано отношение подобия S и его элементы 8(х„х,), то элементы матрицы согласования Гу могут быть найдены по следующему принципу:

r fl, при s (х„ха)<^,

J [0, при s(x1,xl)>X.

Здесь X - значение ^-сечения. Выбор значения X является очень важным, поскольку от него зависит результат голосования.

Свойство 2. К отношению подобия Б предъявляется следующее дополнительное требование: на 8 должно быть выполнено отношение эквивалентности:

Свойство 3. В случае если отношение эквивалентности (б.а), (6.6), (б.в) не выполнено, к отношению подобия S должны быть применены нечеткие композиции (fuzzy compositions). Выполнение нечётких композиций осуществляется до тех пор, пока отношение эквивалентности не будет удовлетворено. Первая нечёткая композиция выполняется по формуле

где б(х;,Х]) - элементы отношения подобия Б (значения мер подобия);

¿(х,^) - элементы матрицы Б', полученной из Б одним шагом нечётких

композиций;

N - число версий.

Если после первой нечёткой композиции отношение эквивалентности не выполнено необходимо выполнить вторую нечёткую композицию 8" = 8о8', и так далее, пока отношение (б.а), (6.6), (б.в) не будет выполнено. Доказано, что не более чем за N -1 композиций отношение будет выполнено.

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

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

• результат работы алгоритмов не зависит от того, насколько выходы версий «схожи»,

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

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

В разделе показано, что специфика применения алгоритмов определяет условия их успешного применения.

(рефлексивность) s(x,, х,) = 1, Vi, (симметричность) s(x,,xj) = s(xj,xi), Vi*j,

(б.а) (6.6)

(транзитивность)

S'=S°S; s' =max[min(s(x,,xl),s(x1[,xi))], k = l,...,N, (7)

J k 1

Предлагаются модификации алгоритмов голосования согласованным большинством, методика комплексного применения алгоритмов и алгоритм выбора значения А,-сечения.

Целью модификации алгоритмов голосования согласованным большинством является обеспечение однозначности принятия решения. Голосование согласованным большинством предполагает принятие решения на основе матрицы согласования (или эквивалентных подмножеств). Согласно алгоритмам «корректными» признаются те версии, которым соответствует строка с максимальным числом единиц (или подмножество с максимальным числом элементов). И, в случаях, когда имеется две и более различных строк с максимальным числом единиц (подмножеств с максимальным числом элементов), корректный ответ выбирается случайно, что снижает вероятность принятия правильного решения. Модификация позволяет отказаться от случайного выбора. Предлагается учитывать надёжности наборов согласных версий, то есть вероятность того, что все версии набора сработали корректно. Модификация затрагивает только последние шаги алгоритмов. Модификация предполагает выбор не «строки (подмножества) с максимальным числом единиц (элементов)», а выбор «строки (подмножества) с максимальным числом единиц (элементов) и с максимальной надёжностью набора версий, который соответствует строке (подмножеству)».

Предложены методы оценки достоверности голосования в зависимости от значения л-сечения и в зависимости от алгоритма голосования.

Методы основаны на введении следующих критериев оценки достоверности голосования.

У

Критерий 1. Относительное число согласных версий У'= . Критерий 2. Разброс в значениях выбранных выходов

1, если шах[ХС0Г ] - тт[Х,хт ] < 2е,

2е

А =

если тах[Хсог] - тт[Хсог] > 2е,

тах[Хсог]-пнп[Хсог] О, если Хсог = 0;

Критерий 3. Надёжность подсистемы выбранных версий Кь , = 1 - ]~[ (1- г).

1=к

у

Критерий 4. Относительное количество согласных алгоритмов У0 = —---.

О

Критерий 5. Весовая характеристика набора согласных алгоритмов

+... + "№„

ш = —-

У

Здесь:

У^ - число версий, выдавших одинаковый результат для какого-то .¡-го исхода голосования;

N - число версий в мультиверсионной системе;

Хсог = {хь -. .л} - множество ответов, признанных корректными;

к,...,1 - номера версий, которые признаны корректными;

е - допустимое отклонение;

г, - надёжность 1-той версии;

УГг - количество алгоритмов голосования, которые выдали одинаковый результат;

N0 - количество алгоритмов голосования, которые были применены.

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

К-ОО ' У

N

= У'хДхУ'^^!^ ,

Ж, +... +

х(д)>

N.

У, +...+ N1

1-Па-О =

(8)

1-ПО-г,) ;

> для случая, когда надёжности версий не известны

К(У) = У'хДхУ'0х^ =

N

:(Д)>

N

;(д)>

N.

N.

Ж, + ... + "№„

(9)

Значения величин ЩУГ) и К(У) лежат в диапазоне от нуля до единицы.

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

Кроме того, применение формул (8) и (9) даёт следующие преимущества:

-возможность оценки исхода голосования в условиях, когда надёжности

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

Предложен формализованный метод выбора значения ^-сечения в нечётких алгоритмах голосования. Суть алгоритма выбора значения X заключается в следующем: сначала определяем все возможные значения X, затем для каждого значения X определяем достоверность принятия решения и, в итоге, в качестве X выбираем то значение, для которого достоверность максимальна. Оценивать достоверность принятия решения в зависимости от X предложено по критериям номер один, два и три. Итоговая достоверность определяется как произведение этих трёх критериев и характеризуется величиной в диапазоне от нуля до единицы. При этом, чем ближе величина к единице, тем «удачнее» значение X. Таким образом, зависимость достоверности принятия решений в нечётких алгоритмах от значения X характеризуется следующими формулами: • для алгоритма Fuzzy CV

Y')x(A)xil-ri(l_r,)l (Ю)

Rcv(X) = Y'xAxRk

N

> для алгоритма Fuzzy MY

г/

RmvO-):

Ъ.

N

0,

(д)х 1-па-о 1 при

при

Y <

N + 1 2

N + 1

(И)

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

Фаза 1. Выбор допустимого отклонения z. Построение отношения подобия S с использованием формулы (4).

Фаза 2. Поверка выполнения на S отношения эквивалентности (6.а), (6.6), (б.в). В случае если отношение эквивалентности не удовлетворено, выполнение необходимого количества нечётких композиций (7).

Фаза 3. Выбор значения Х-сечения.

Фаза 4. Построение матрицы согласования R по формуле (5).

Фаза 5. Принятие решения на базе полученной матрицы согласования. По Fuzzy CV выбираются ответы, которым соответствует строка R с максимальным числом единиц. По Fuzzy MV выбираются ответы, которым соответствует строка R с большинством единиц.

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

Шаг 1. Заносим все значения мер подобия s(x„xj) cSb множество U однократно.

Шаг 2. Принимаем в качестве значения X каждый элемент из U поочерёдно, и для каждого ukeU:

• строим соответствующую матрицу согласования r, [l, при s(xt, Xj) ^ uk,

J [О - иначе;

• вычисляем величины Rcv(uk) и/или Rmv(uic) формуле (10) и/или (11), к =1,...,ш, m = [и|.

Шаг 3. В качестве значения X для алгоритма Fuzzy CV выбираем такой ueU, для которого Rcv(uk) максимально. В качестве значения X для алгоритма Fuzzy MV выбираем такой ueU, для которого Rmv(uO максимально (если max[RMv(uk)]=0, то принять решение с использованием Fuzzy MV не возможно).

Предлагаемый подход к выбору X даёт следующие преимущества: -перебираются все возможные варианты исхода голосования (для произвольного набора выходов имеется m возможных матриц согласования и соответственно m исходов голосования); -выбор X осуществляется с ориентацией на максимизацию числа согласных выходов и надёжности набора «корректных» версий и минимизацию разброса в значениях «корректных» выходов (минимизация разброса позволяет устранить (или свести к минимуму) эффект «склеивания» в нечётких алгоритмах);

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

В четвертом разделе рассмотрена программная реализация основных результатов работы. Основные результаты реализованы в двух программных системах: среда исполнения мультиверсионной системы NVX и модель, иллюстрирующая работу алгоритмов голосования в мультиверсионном ПО NVX-m.

Программа NVX.

Программа NVX представляет собой упрощённый вариант реализации среды исполнения для мультиверсионных систем. Программа реализует параллельное исполнение версий мультиверсионной системы и контроль их работы. К основным функциям программы относятся:

• создание процессов версий и управление ими (задача приоритета процесса, останов процесса, перезапуск);

• взаимодействие с процессами версий:

- сбор статусов работы всех версий;

- реагирование на сигналы версий (реализация алгоритмов голосования и коррекция данных в контрольных точках и по завершении работы версий);

- посылка управляющих сигналов версиям;

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

Программа NVX разработана с ориентацией на универсальность решаемых задач. То есть программа создаёт среду для исполняемых версий. Сами же версии разрабатываются независимо и могут быть направлены на решение любых вычислительных задач.

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

В качестве источников данных могут выступать текстовые файлы либо таблицы базы данных СУБД MySQL (то есть версии должны сохранять результаты вычислений либо в текстовые файлы, либо в базу данных MySQL). При условии, что версии модуля сохраняют информацию в базу данных MySQL, для работы программы необходимо наличие драйвера mysql-connector-odbc-3.51.12. Драйвер можно бесплатно загрузить с сайта разработчиков СУБД MySQL (www.mysql.org).

Сама программа NVX является законченным продуктом. Это означает, что нет необходимости менять исходный код NVX в зависимости от состава и функций версий. Однако, к разработке версий предъявляется ряд дополнительных требований.

Программа NVX-m.

Программа NVX-m представляет собой модель, иллюстрирующую работу алгоритмов голосования' в мультиверсионном программном обеспечении. Программа использует в качестве исходных данных числовые значения выходов версий. Число версий не ограничено и задаётся в начале работы программы. Однако, выход каждой версии должен быть скаляром, то есть предполагается, что каждая версия имеет единственный выход — число.

В программе реализованы все 14 алгоритмов голосования, рассмотренные в данной работе, в том числе 4 алгоритма, разработанные автором.

Кроме того, в программе реализована возможность расчета достоверности голосования в зависимости от сечения в нечётких алгоритмах. Расчёт производится с использованием формул (10) и (11).

При работе с NVX-m сначала необходимо указать исходные данные для голосования: число версий, допустимое отклонение, значение ^.-сечения, выход каждой версии, надёжность каждой версии. Значение А.-сечения следует устанавливать только в случае, когда предполагается использование нечётких алгоритмов голосования. Если не предполагается использование алгоритмов, использующих надёжности версий, надёжности версий могут не указываться. После того, как исходные данные установлены, можно смотреть результат по интересующему алгоритму голосования. Программа также выводит данные, на основе которых принято решение (матрицы согласования, отношения подобия, разбиения и другие).

Программа имеет интуитивно понятный интерфейс и некоторые подсказки. МУХ не предъявляет существенных требований к платформе и может использоваться на базе любой XV\ г)с!о\уы-систсмы. На рисунке 3 представлен фрагмент выполнения программы ЫУХ-т.

Еергий| шад.^г^да, рщ^ } ■ ' М1Л< 1 И!! . ИГ.' (■Вш^ч^пИ

В

МАТРИЦА оцчсбиссг ТГ ■

1 еда щ» ш (да Ч Щ<> а ,а 1 '0 *

о.ом 1 шм 0.0« о.ом о.™ ; 1 О |0 0 .0 0 0 1 : 0.3443 ¡а

ОЙ 0.004 к 0.155 с.оя 0.437 0 ¡0 '1 ¡0 0 0 0 0 1 0я®1

одз мм ■0.155 1 0.АЭ 0.155 0 0 0 1 0 0 0 ¡0 1 07091

0,582 0.004 0.09 ат 1 0.03 1 и и 0 1 Ю 1 1 13 О.ЗИЗЙЗ:

0.03 ода 0.45? 0.1 к ода 1 ¡0 0 0 0 » ¡1 0 3 0.365М50.

о.ин ■Ш ш» 0.316 - Т о ;0 (0 13 аэмздаз-

0,5®? 0.004 о.оэ 009 0,625 0.09 ' V. 1 ;0 0 :0 1 В 1 1 V 13

й*: Яг 53 > ■<■ ... >

: з . <»

(К;

Ш

Ц Щ ■ ^ -Т \ л- ■' '■• I г; =■ 1 [; Ш «у ||.:.

V} ■ количество единиц в стрема Я» - надёжность набора "соглеси&и" Крсий

" егтвет-ы

..'••.и

Оерсип 1

Версия?, о.цге

ЗКРИЯ 7 0.14202

& ол зав 0.14534

ЗерСня-З

Ш ' 0.1 <507 0.14631

Овр^ия 12 '

Руюунок 3 - Вывод результата голосовании >1 вычислений в программе КУХ-т

Программна? система МУХ-т применялась к различным исходным данным. Исходные данные были взяты из открытых источников (статей, материалов грантов ио надёжности программного обеспечения и др.). Некоторые исходные дачные соответствовали реальным системам, другие -носили чисто академический характер. Результаты работы программной системы были корректны и соответствовали результатам вычислений в источниках. Кроме того, для одного из случаев было покачано, что использование методики комплексного применения алгоритмов позволяет принять более удачное решение, чем применение используемого в системе метода принятия решений.

Все разработанные программы и компоненты необходимые для их работы распространяются свободно.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

• Разработана программная модель процесса голосования в мультиверсионных системах. Программная система применялась к различным исходным данным, взятым из открытых источников. В результате был сделан ряд выводов о специфике применения алгоритмов голосования.

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

• Разработан ряд методик по применению алгоритмов голосования и модификаций алгоритмов, направленных на повышение достоверности принятия решений:

- модифицированы алгоритмы голосования согласованным большинством;

- предложены методы оценки достоверности голосования в зависимости от значения Х-сечения, и в зависимости от алгоритма голосования;

- разработан алгоритм выбора значения Х-сечения в алгоритмах голосования с использованием нечёткой логики;

- предложена методика комплексного применения алгоритмов голосования в мультиверсионном программном обеспечении.

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

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

Основные положения и результаты диссертационной работы представлены в следующих работах автора (знаком * обозначены работы, опубликованные в издании, включенном в список изданий, рекомендованных ВАК для опубликования результатов диссертационных исследований):

1. * Морозов, В. А. Выбор порогового значения для операции л-вырезки в нечетких алгоритмах голосования мультиверсионного программного обеспечения систем [Текст] / В. А. Морозов, М. Ю. Царев, В. А. Волков // Системы управления и информационные технологии. - 2007. - № 2(28). -С. 62-67.

2. * Морозов, В.А. Голосование согласованным большинством в мультиверсионном ПО [Текст] / В. А. Морозов // Вестник ТГУ. - 2007. -№ 1.-С. 136-137.

3. * Морозов, В. А. Модификация алгоритма голосования МУР-СУ для одного вида матриц согласования [Текст] / В. А. Морозов // Вестник СибГАУ. - 2007. - № 1. - С. 81-87.

4. * Морозов, В. А. Программно-алгоритмическое обеспечение методов оценки надежности распределенных компьютерных систем [Текст] / И. В. Ковалев, В. А. Морозов, Р. Ю. Царев // Системы управления и информационные технологии. - 2006. - № 4(26). - С. 26-30.

5. Морозов, В. А. К вопросу об использовании двух версий в мультиверсионном программном обеспечении [Текст] / В. А. Морозов, Р. Ю. Царев // Материалы X Междунар. науч. конф. «Решетневские чтения». -2006.-С. 312-313.

6. Морозов, В. А. Изоляция модулей мультиверсионного программного обеспечения на этапах разработки [Текст] / В.А. Морозов П Фундаментальные исследования. - 2007. - №2. - С. 34-36.

7. Морозов, В. А. Распределенные информационно-управляющие системы: кластерная архитектура и мультиверсионное программное обеспечение: Монография [Текст] / Е. А. Энгель, В. А. Морозов, Р. Ю. Царев // Красноярск: ИПЦ КГТУ. - 2006. - 160 С.

8. Морозов, В. А. Мультиверсионное программное обеспечение информационно-управляющих систем [Текст] / А. В. Аниконов, В. А. Морозов, Р. Ю. Царев // Фундаментальные исследования. - 2006. - №11. -С. 65.

9. Морозов, В. А. Компонентный подход при оценке надежности сложных программных систем [Текст] / В. А. Морозов // Вестник университетского комплекса: Сб. научн. трудов. НИИ СУВПТ. - 2005. - №5(19). - С. 164167.

Ю.Морозов, В. А. Поддержка принятия решений при создании мультиверсионной структуры программного обеспечения [Текст] / В.А. Волков, В.А. Морозов, М.Ю. Царев // Вестник университетского комплекса: Сб. научн. трудов НИИ СУВПТ. - 2005. - №5(19). - С. 212-217.

П.Морозов, В. А. Моделирование мультиверсионной программной системы [Текст] / В.А. Морозов, М.Ю. Царев, Р.Ю. Царев // «Информационные

технологии и математическое моделирование» Сб. тр. V Международной науч.-практ. конф. - Томск: Изд-во ТГУ. - 2006. - С. 76-78.

12.Морозов, В. А. Принятие решений при формировании мультиверсионного программного обеспечения [Текст] / В.А. Волков, В.А. Морозов, М.Ю. Царев. // «Информационные технологии и математическое моделирование» Сб. тр. V Международной науч.-практ. конф. - 2006. - С. 82-85.

Разработки, зарегистрироваппые в Отраслевом фонде алгоритмов и программ:

13.Ковалев И.В., Амбросенко Н.Д., Морозов В.А., Богданова О.В. Система надежностного анализа клиент-серверной архитектуры распределенного программного обеспечения . (программная система «CSR-Analysis ver. 1.0»), М.: ВНТИЦ, 2006. № 50200601667. Per. номер ОФАП 6908.

14.Царев Р.Ю. Царев М.Ю., Морозов В.А., Волков В.А. Система моделирования мультиверсионного программного обеспечения (программная система «MVSW Modeling ver.1.0»), М.: ВНТИЦ, 2006. № 50200602086. Per. номер ОФАП 7283.

15.Морозов В.А. Программная реализация среды исполнения мультиверсионного программного обеспечения (Программная система «NVX»). М.: ВНТИЦ, 2007. № 50200700112. Per. номер ОФАП 7481.

16.Морозов В.А. Модель иллюстрации алгоритмов голосования в мультиверсионном программном обеспечении. М.: ВНТИЦ, 2007. № 50200700113. Per. номер ОФАП 7482.

Морозов Владимир Андреевич Алгоритмы голосования для мультиверсионных информационно-управляющих систем

Автореферат

Подписано к печати /¿.£¿2007. Формат 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ № Р6

Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г. Красноярск, просп. им. газеты «Красноярский рабочий», 31

Введение.

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

1.1. Программный компонент систем управления и обработки информации.

1.2. Надежность функционирования программного обеспечения.

1.2.1. Надежностная характеристика программного модуля.

1.2.2. Обеспечение надежности программ с помощью введения избыточности.

1.3. Мультиверсионное программирование как методология проектирования отказоустойчивого программного обеспечения систем управления и обработки информации.

Выводы.

2. Алгоритмы голосования в мультиверсионном программном обеспечении.

2.1. Алгоритмы голосования, основанные на сравнении выходных данных.

2.1.1. Неформализованные алгоритмы голосования.

2.1.2. Формализованные алгоритмы голосования.

2.2. Алгоритмы с принятием решения вне зависимости от схожести выходных данных.

2.2.1. «Максимально вероятное» голосование (МЬУ).

2.2.2. Усреднённое голосование.

Выводы.

3. Специфика применения алгоритмов голосования в мультиверсионном программном обеспечении информационно-управляющих систем.

3.1. Неоднозначность принятия решения в алгоритмах голосования согласованным большинством.

3.2. «Склеивание» подмножеств выходных данных.

3.3. Оценка результатов голосования.

3.4. Несовместность разбиений в алгоритмах с минимизацией.

3.5. Выбор значения Х-сечения в нечётких алгоритмах.

3.6. Комплексное применение алгоритмов голосования в мультиверсионном программном обеспечении.

Выводы.

4. Программная реализация результатов работы.

4.1. Программа ИУХ.

4.1.1. Особенности программы.

4.1.2. Взаимодействие с исполняемыми версиями.

4.1.3. Общая схема работы программы.

4.1.4. Обобщенная схема работы версии.

4.1.5. Требования к разработке версий.

4.2. Программа NVX-m.

Выводы.

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

На сегодняшний день существует ряд методов повышения надёжности программного обеспечения (ПО) информационно-управляющих систем (ИУС). Достаточно эффективным методом обеспечения надёжности ПО, положительно зарекомендовавшим себя на практике, является концепция мультиверсий [1, 5, 13-19, 25, 29-40, 47, 50-52, 57-68, 70, 72-75, 77-78, 80, 82-92, 96-99, 101-102, 105108,110-113, 115, 119].

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

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

Подчеркнём, что результат работы алгоритма голосования определяет итог работы всей мультиверсионной системы. Поэтому ошибка в процессе голосования может привести к отказу всей системы, и, соответственно к значительным потерям. Таким образом, процесс голосования в мультиверсионном ПО очень важен, что и определяет актуальность исследований в данной области.

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

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

• Сравнительный анализ применяемых в настоящее время алгоритмов голосования.

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

• Анализ специфики применения алгоритмов голосования в мультиверсионном программном обеспечении ИУС.

• Повышение достоверности принятия решений в мультиверсионном ПО путём модификации алгоритмов голосования и разработки методики комплексного применения алгоритмов.

• Реализация результатов исследования в программной среде исполнения мультиверсионных систем.

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

Научная новизна работы:

1. Впервые предложена классификация наиболее распространённых и универсальных алгоритмов голосования в мультиверсионном программном обеспечении и определены условия успешного применения алгоритмов.

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

3. Предложены методы оценки достоверности голосования в зависимости от значения А,-сечения, и в зависимости от алгоритма голосования; методы основаны на введении дополнительных критериев, таких как разброс в выбранных выходах и относительное количество согласных версий.

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

5. Разработана методика комплексного применения алгоритмов голосования с возможностью формализованного выбора окончательного результата из множества результатов применённых алгоритмов.

Значение для теории. Материалы работы могут послужить базой для проведения исследований в области принятия решений в мультиверсионном

ПО. Реализованная в рамках работы программная модель ЫУХ-гп даёт следующие преимущества для исследователей:

- возможность наглядно изучать процесс голосования для произвольных исходных данных,

- возможность анализировать результаты применения различных алгоритмов голосования,

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

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

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

Основные защищаемые положения

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

2. Разработанные методы оценки достоверности голосования, основанные на введении дополнительных критериев, позволяют адекватно вычислять достоверность в зависимости от значения А,-сечения, и в зависимости от алгоритма голосования.

3. Разработанный алгоритм выбора значения ^-сечения в нечётких алгоритмах, позволяет учесть все возможные исходы голосования, и достичь максимальной достоверности по предложенным критериям.

4. Предложенная методика комплексного применения алгоритмов голосования позволяет эффективно принимать решение по выбору корректных ответов за счёт учёта специфики алгоритмов и возможности формализованного выбора окончательного результата из множества результатов применённых алгоритмов.

5. Разработанные программные продукты дают базу для проведения исследований в области принятия решений в мультиверсионном ПО, и позволяют успешно реализовывать параллельные вычислительные задачи.

Публикации. По теме диссертационной работы опубликовано 12 печатных работ. Перечень публикаций представлен в конце автореферата.

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

• X Международная научная конференция «Решетневские чтения» (Красноярск, 2006);

• V Международная научно-практическая конференция «Информационные технологии и математическое моделирование» (Томск, 2006);

• Международная научная конференция с международным участием «Проблемы передачи и обработки информации» (Дубай, ОАЭ, 2006);

• Международная научно-практическая конференция «Фундаментальные и прикладные исследования высшей школы» (Сингапур, 2007);

• Державинские чтения (Тамбов, 2007).

Диссертационная работа в целом обсуждалась на научных семинарах Сибирского государственного аэрокосмического университета, а также НИИ Систем управления, волновых процессов и технологий (2005-2007 гг.).

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы из 120 наименований и двух приложений. Объем диссертационной работы 124 страницы, приложений - 11 страниц.

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

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

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

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

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

Разработанный алгоритм выбора значения А,-сечения позволяет выбрать значение X оптимальное с точки зрения надёжности версий, числа согласных версий, разброса в ответах из всех возможных значений X.

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

Заключение

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

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

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

• Разработана программная модель процесса голосования в мультиверсионных системах. Программная система применялась к различным исходным данным, взятым из открытых источников (статей, материалов грантов по надёжности программного обеспечения и др). В результате был сделан ряд выводов о специфике применения алгоритмов голосования, в том числе определены условия возникновения эффекта «склеивания» и влияние А,-сечения на эффект. в Проведён анализ специфики применения алгоритмов голосования в мультиверсионном программном обеспечении информационно-управляющих систем. Выявлены основные факторы, определяющие специфику применения алгоритмов голосования: неоднозначность принятия решения в алгоритмах голосования согласованным большинством, «склеивание» подмножеств выходов, необходимость оценки результатов голосования, несовместность разбиений и проблема выбора значения А,-сечения. В соответствии со спецификой определены условия успешного применения алгоритмов голосования.

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

- модифицированы алгоритмы голосования согласованным большинством,

- предложены методы оценки достоверности голосования в зависимости от значения Х-сечения, и в зависимости от алгоритма голосования,

- разработан алгоритм выбора значения А,-сечения в алгоритмах голосования с использованием нечёткой логики,

- предложена методика комплексного применения алгоритмов голосования в мультиверсионном программном обеспечении.

1. Движение, А.Н. Гарантоспособные вычисления: от идей до реализации в проектах Текст. / А.Н. Авиженис, Ж.-К. Лапри // ТИЮР. 1986. - Т. 74. №5.-С. 8-21.

2. Акимов, О. Дискретная математика: логика, группы, графы, фракталы Текст. / О. Акимов. М.: Издательство Акимова. - 2005. - 656 С.

3. Андерсон, Д. Дискретная математика и комбинаторика Текст. / Д. Андерсон. М.: Вильяме. - 2003. - 960 С.

4. Антамошкин, А. Н. Системный анализ: Проектирование, оптимизация и приложения Текст. / А. Н. Антамошкина. -Красноярск : CAA. 1996. -206 С.

5. Антамошкина, О. И. Программно-информационные технологии формирования критичных по надежности систем управления: монография Текст. / О. И. Антамошкина, Р. Ю. Царев, С. А. Шабалин. СПб: Инфо-Да.- 2005. - 175 С.

6. Аткинсон, JL MySQL. Библиотека профессионала Текст. / JI. Аткинсон. -М. : Вильяме. 2002. - 624 С.

7. Бочаров, П. Теория вероятностей и математическая статистика Текст. / П. Бочаров, А. Печинкин. М.: Физматлит. - 2005. - 296 С.

8. Боэм, Б.У. Инженерное проектирование программного обеспечения Текст. / Б.У. Боэм. М.: Радио и связь. - 1985. - 512 С.

9. Вентцель, Е. Теория вероятностей Текст. / Е. Вентцель. М. : Academia. -2005.-576 С.

10. Гмурман, В. Е. Теория вероятностей и математическая статистика Текст. / В. Е. Гмурман. М.: Высшая школа. - 2004. - 480 С.

11. Дюбуа, П. MySQL. Второе издание Текст. / П. Дюбуа. М. : Вильяме. -2004,- 1056 С.

12. Ерусалимский, Я. Дискретная математика: Теория, задачи, приложения Текст. / Я. Ерусалимский. М.: Вузовская книга. - 2005. - 268 С.

13. Ковалев И. В. Оптимальное проектирование мультиверсионных систем управления Текст. / И. В. Ковалев, A.A. Попов, A.C. Привалов // Информационные технологии в инновационных проектах: труды международной научно-технической конференции. 2000. - С. 14-16.

14. Ковалев, И. В. Параллельные процессы в информационно-управляющих системах. Формирование и оптимизация: монография Текст. / И. В. Ковалев, Р. Ю. Царев, 10. Г. Шиповалов. Красноярск : НИИ СУВПТ. -2001.- 143 С.

15. Ковалев, И. В. Методология оценки и повышения надежности программно-информационных технологий и структур: монография Текст. / И. В. Ковалев, Т. И. Семенько, Р. Ю. Царев. Красноярск : ИПЦ КГТУ. -2005.- 160 С.

16. Ковалев, И. В. Комбинированный метод формирования мультиверсионного программного обеспечения управления космическими аппаратами Текст. / И. В. Ковалев, Р. Ю. Царев // Авиакосмическое приборостроение. 2006. -№9.-С. 8-14.

17. Ковалев, И. В. Итеративный метод многоатрибутивного формирования оптимального состава информационно-управляющих систем Текст. / И. В.

18. Ковалев, А. В. Аниконов, М. Ю. Слободин, Р. Ю. Царев // Системы управления и информационные технологии. 2006. - № 2(24). - С. 90-95.

19. Колемаев, В.А. Теория вероятностей и математическая статистика Текст. / В.А. Колемаев, В.Н. Калинина. М.: Юнити. - 2003. - 342 С.

20. Кузнецов, О. Дискретная математика для инженера Текст. / О. Кузнецов. -М.: Лань.-2005.-400 С.

21. Кузнецов, А. С. Теория вычислительных процессов: учеб. пособие Текст. / А. С. Кузнецов, Р. Ю. Царев. Красноярск : ИПЦ КГТУ.- 2007. - 192 С.

22. Кузнецов, М. В. MySQL 5 Текст. / М. В. Кузнецов. Спб. : BHV-Спб. -2006. -560 С.

23. Кэнту, М. Delphi 7 для профессионалов Текст. / М. Кэнту // Питер. -2004.-708 С.

24. Лебедев, В. А. Параллельные процессы обработки информации в управляющих системах: монография Текст. / В.А. Лебедев, Н. Н. Трохов, Р. Ю. Царев. Красноярск : НИИ СУВПТ. - 2001. - 137 С.

25. Липаев, В. В. Проектирование программных средств Текст. / В. В. Липаев. М.: Высшая школа. - 1990. - 303 С.

26. Лонгботтом, Р. Надежность вычислительных систем Текст. /Р. Лонгботтом. М.: Энергоатомиздат. - 1985. - 288 С.

27. Макоха, А. Дискретная математика Текст. / А. Макоха, П. Сахнюк, Н. Червяков. М.: Физматлит. - 2005. - 368 С.

28. Морозов В.А. Голосование согласованным большинством в мультиверсионном ПО Текст. / В. А. Морозов // Вестник ТГУ. 2007. -№ 1.-С. 136-137.

29. Морозов В. А. Модификация алгоритма голосования ЫУР-СУ для одного вида матриц согласования Текст. / В. А. Морозов // Вестник СибГАУ. -2007.-№ 1.-С. 81-87.

30. Морозов, В. А. Программно-алгоритмическое обеспечение методов оценки надежности распределенных компьютерных систем Текст. / И. В. Ковалев,

31. B. А. Морозов, Р. Ю. Царев // Системы управления и информационные технологии. 2006. - № 4 (26). - С. 26-30.

32. Морозов, В. А. К вопросу об использовании двух версий в мультиверсионном программном обеспечении Текст. / В. А. Морозов, Р. Ю. Царев // Материалы X Междунар. науч. конф. «Решетневские чтения». -2006.-С. 312-313.

33. Морозов, В. А. Изоляция модулей мультиверсионного программного обеспечения на этапах разработки Текст. / В.А. Морозов // Фундаментальные исследования. 2007. - № 2. - С. 34-36.

34. Морозов, В. А. Распределенные информационно-управляющие системы: кластерная архитектура и мультиверсионное программное обеспечение: Монография Текст. / Е. А. Энгель, В. А. Морозов, Р. Ю. Царев. -Красноярск : ИПЦ КГТУ. 2006. - 160 С.

35. Морозов, В. А. Мультиверсионное программное обеспечение информационно-управляющих систем Текст. / А. В. Аниконов, В. А. Морозов, Р. Ю. Царев // Фундаментальные исследования. 2006. - №11.1. C. 65.

36. Морозов, В. А. Компонентный подход при оценке надежности сложных программных систем Текст. / В. А. Морозов // Вестник университетского комплекса. Сб. научн. трудов. НИИ СУВПТ. - 2005. - № 5 (19).- С. 164167.

37. Морозов, В. А. Поддержка принятия решений при создании мультиверсионной структуры программного обеспечения Текст. / В.А. Волков, В.А. Морозов, М.Ю. Царев // Вестник университетскогокомплекса: Сб. научн. трудов НИИ СУВПТ. 2005. - № 5 (19). - С. 212217.

38. Морозов, В. А. Моделирование мультиверсионной программной системы Текст. / В.А. Морозов, М.Ю. Царев, Р.Ю. Царев // «Информационные технологии и математическое моделирование» Сб. тр. V Международной науч.-практ. конф. 2006. - С. 76-78.

39. Орлов, С. А. Технологии разработки программного обеспечения: разработка сложных программных средств Текст. / С.А. Орлов. СПб. : Питер.-2002.-464 С.

40. Осипов, Д. Delphi. Профессиональное программирование Текст. / Д. Осипов. М.: Символ-Плюс. - 2006. - 1050 С.

41. Плотников, А. Дискретная математика. Новое знание Текст. / А. Плотников. М.: Физматлит. - 2005. - 288 С.

42. Павлов, С. Теория вероятностей и математическая статистика Текст. / С. Павлов. М.: РИОР. - 2006. - 80 С.

43. Пашеку, X. Программирование в Borland Delphi 2006 для профессионалов Текст. / X. Пашеку. М.: Вильяме. - 2006. - 944 С.

44. Русаков, М. А. Современные методы надежностной оценки сложных программных систем: Монография Текст. / М. А. Русаков, Р. Ю. Царев, С. А. Шаболин. СПб.: Инфо-Да. - 2005. - 203 С.

45. Слободин, М. Ю. Программно-аппаратное обеспечение отказо- и катастрофоустойчивых систем управления и обработки информации: монография Текст. / А. В. Аниконов, М. Ю. Слободин, Р. Ю. Царев . М.: Макс-пресс. - 2006. - 244 С.

46. Соммервилл, И. Инженерия программного обеспечения Текст. / И. Соммервилл. М.: Вильяме. - 2002. - 624 С.

47. Сугак, Е. В. Надёжность технических систем Текст. / Е. В. Сугак, Н. В. Василенко, Г. Г. Назаров, А. Б. Паньшин, А. П. Каркарин. Красноярск : НИИ СУВПТ. - 608 С.

48. Царев, Р. Ю. Компьютерная поддержка многоатрибутивных методов выбора и принятия решения при проектировании корпоративных информационно-управляющих систем: монография Текст. / Р. Ю. Царев, М. Ю. Слободин. СПб.: Инфо-Да. - 2004. - 221 С.

49. Царев, Р. Ю. Многоатрибутивное принятие решений в мультиверсионном проектировании: монография Текст. / Р. Ю. Царев. Красноярск : ИПЦ КГТУ. - 2005. - 156 С.

50. Царев, Р. Ю. Система поддержки принятия решений при формировании мультиверсионного программного обеспечения Текст. / Р. Ю. Царев // Программные продукты и системы. 2007. - № 1. - С. 57-59.

51. Шкрыль, А. Разработка клиент-серверных приложений в Delphi Текст. / А. Шкрыль. М.: BHV. - 2005. - 480 С.

52. Akhil, К. Voting Mechanisms of Distributed Systems Text. / K. Akhil, M. Kavindra // IEEE Transactions on Reliability. 1991. - Vol. 40 (5). - P. 593600.

53. Ammar, M. Performance Characterization of Quorum-Consensus Algorithms for Replicated Data Text. / M. Ahammad, M. Ammar // Proceedings of the 7th Symposium on Reliability in Distributed Software and Database Systems. -1987.-P. 161-167.

54. Athavale, A. M. Performance Evaluation of Hybrid Voting Schemes Text. / A. M. Athavale // M. S. Thesis, North Carolina State University. 1989. - P. 3343.

55. Avizienis, A. On the Implementation of N-Version Programming for Software Fault Tolerance During Program Execution Text. / A. Avizienis, L. Chen // Proc. COMP AC 77. 1997. - P. 149-155.

56. Avizienis, A. On the Performance of Software Fault-Tolerance Strategies Text. / A. Grnarov, J. Alart A. Avizienis // Proc. 10th IEEE Int. Symp. on Fault-Tolerant Computing. 1980. - P. 251-253.

57. Avizienis, A. Fault Tolerance by Design Diversity: Concepts and Experiments Text. / A. Avizienis, J. P. J. Kelly // IEEE Computer. 1984. - Vol. 17 (8). -P. 67-80.

58. Avizienis, A. Dependable Computing: from Concepts to Design Diversity Text. / A. Avizienis, J. -C Laprie // Proc. of the IEEE. Vol. 76 (5). - 1986. - P. 629638.

59. Avizienis, A. The N-Version Approach to Fault-Tolerant Software Text. / A. Avizienis // IEEE Trans. Soft. Eng. 1985. - Vol. SE-11 (12). - P. 1511-1517.

60. Avizienis, A. Toward Systematic Design of Fault-Tolerant Systems Text. / A. Avizienis // Computer. April 1977. - P. 51-58.

61. Avizienis, A. Community Error Recovery in N-Version Software: a Design Study with Experimentations Text. / K. S. Tso, A. Avizienis // In Proc. of the FTCS-17. 1987. - P. 127-133.

62. Avizienis, A. Assuring Design Diversity in N-Version Software: A Design Paradigm for N-Version Programming Text. / M. Lyu, A. Avizienis // In Proc. of the 2nd Dependable Computing for Critical Applications. 1992. - P. 197218.

63. Avreski, D. Fault Tolerant Parallel and Distributed Systems Text. / D. Pradham, D. Avresky // IEEE CS Press. 1995. - P. 226-233.

64. Bastani, F. Towards Dependable Safety-Critical Software Text. / F. Bastani, B. Cucic, V. Hilford A. Jamoussi // Proc. WORDS'96. 1996. - P. 27-38.

65. Belli, F. Fault Tolerant Programs and Their Reliability Text. / F. Belli, P. Jedrzejowicz // IEEE Trans. Rel. 1990. - Vol. 29 (2). - P. 184-192.

66. Bezdeck, J. Fuzzy Partitions and Relations. Axiomatic Basis for Clustering Text. / J. Bezdeck, D. Harris // Fuzzy Sets and Systems. 1978. - № 1. - P. 111-127.

67. Brilliant, S. S. The Consistent Comparison Problem in N-Version Software Text. / S.S. Brilliant, J. C. Knight, N. G. Leveson // IEEE Trans. Soft. Eng. -1989.-Vol. SE-15 (11).-P. 1481-1484.

68. Clir, C. J. Fuzzy Sets and Fuzzy Logic: Theory and Applications Text. / C. J. Clir, B. Yuan. Prentice Hall. - 1995. - 114 P.

69. Di Giandomenico, F. Adjudicators for Diverse Redundant Components Text. / F. Di Giandomenico, L. Strigini // Proc. SRDS-9 Huntsville. 1990. - P. 114123.

70. Eckhardt, D.E. A Theoretical Basis for the Analysis of Multi-version Software Subject to Coincident Errors Text. / D.E. Eckhardt, Jr. and L.D. Lee // IEEE Trans. Rel. Eng. 1985.- Vol SE-U (12).-P. 1511-1517.

71. Fabre, J. -C. A Metaobject Architecture for Fault Tolerant Distributed Systems Text. / J.-C. Fabre, T. Perennou // IEEE TSE. 1997. - P. 177-188.

72. Gray, J. High-Availability Computer Systems Text. / J. Gray and D. P. Siewiorek // IEEE Computer. 1991. - Vol. 24 (9). - P. 39-48.

73. Hsu, H. M. Aggregation of Fuzzy Opinions under Group Decision Making Text. / H. M. Hsu, C. T. Chen // Fuzzy Sets and Systems. 1996. - № 79. - P. 279-285.

74. Jedrzejowicz, P. Comparative Analysis of Concurrent Fault-Tolerance Techniques for Real-Time Applications Text. / F. Belli, P. Jedrzejowicz // Proc. Intl. Symposium on Software Reliability Engineering. 1991. - P. 59-74.

75. Kanoun, K. Definition on Analysis of Hardware and Software Fault-Tolerant Architectures Text. / J. -C. Laprie, J. Arlat, C. Beounes, K. Kanoun // Computer. 1990. - Vol. 23. - P. 39-51.

76. Kim, H. K. Distributed Execution of Recovery Blocks: an Approach to Uniform Treatment of Hardware and Software Faults Text. / H. K. Kim, H. 0 Welch // IEEE TC. 1989. - Vol. C-38 (5). - P. 526-536.

77. Kim, K.H. Major Research Issues in Real-Time Fault-Tolerant Computing Text. / K.H. Kim // In Proc. of the Pacific Rim Int. Symposium on Fault-Tolerance. 1995.-P. 141-143.

78. Kim, K. An Experimental Evaluation of Maximum Likelihood Voting in Failure Correlation Condition Text. / K. Kim, M.A. Vouk, D.F. McAllister // Proc ISSRE 96. 1996.-P. 330-339.

79. Knight, C. J. An experimental evaluation of the assumption of independence in Multiversion programming Text. / C.J. Knight, N.G. Levenson // IEEE Trans. Software Engineering. Vol. SE-12. - 1986. - P. 96-109.

80. Knight, C. J. The practical use of consensus voting and majority voting mechanisms Text. / J. C. Knight // Dependability Modeling and Evaluation of Software Fault-Tolerant Systems. IEEE TC. 1990. - Vol. 39. - P. 391-415.

81. Kovalev, I. V. Multi-version design of fault-tolerant software in control systems Text. / I. V. Kovalev, M. Ju. Slobodin, R. Ju. Tsarev // Engineering & automation problems. 2006. - № 5. - C. 61 -69.

82. Krishnamurthy, B. Software Fault Tolerance. Text. / M. Lyu, B. Krishnamurthy. New York : John Wiley & Son. - 1995. - 192 P.

83. Lam, L. A Theoretical Analysis of the Application of Majority Voting to Pattern Recognition Text. / L. Lam, C. Suen // IEEE Transactions on Reliability. -1992.-Vol. 41 (4).-P. 418-420.

84. Lam, L. Application of Majority Voting to Pattern Recognition: An Analysis of Its Behavior and Performance Text. / L. Lam, C. Suen // IEEE Transaction on Systems, Man. and Cybernetics. 1997. - Vol. 27 (5). - P. 106-121.

85. Laprie, J.-C. Software-Based Critical Systems Text. / J.-C. Laprie // In Proc. Of the 15th int'l Conf. on Computer Safety, Reliability and Security. SAFECOMP'96. 1996. - P. 157-170.

86. Laprie, J. -C. Dependable Computing and Fault Tolerance: Concepts and Terminology Text. / J. -C. Laprie // Proc. 15th IEEE Int. Symp. on Fault-Tolerant Computing. 1985. - P. 2-11.

87. Laprie J.-C. Dependability: A Unifying Concept for Reliable Computing and Fault Tolerance. Dependability of Resilient Computers Text. / J. -C. Laprie. -New York : BSP Professional Books. 1989. - 28 P.

88. Laprie, J. -C. Hardware and Sosftware Fault Tolerance: Definition and Analysis of Architectural Solutions Text. / J. -C. Laprie, J. Arlat, C. Beounes K. Kanoun, C. Hourtolle // Proc. 17th IEEE Int. Symp. on Fault-Tolerant Computing. -1987. P. 116-121.

89. Lee, P. A. Fault Tolerance: Principles and Practice Text. / P. A. Lee, T. Anderson. New York : Springer-Verlag. -1990. - 135 P.

90. Leung, Y. W. Maximum Likelihood Voting for Fault Tolerant Software with Finite Output Space Text. / Y. W. Leung // IEEE Trans. Rel. 1995. - Vol 44 (3).-P. 419-427.

91. Leveson, N. G. The Use of Self Checks and Voting in Software Error Detection: An Empirical Study Text. / N. G. Leveson, S. S. Cha, J. C. Knight, T.J. Shimeall // IEEE Trans. Software Engineering. 1990. - Vol. 16 (4). - P. 432443.

92. Lin, X. Performance Analysis Classifier Combination by Plurality Voting and Their Application in Pattern Recognition Text. / X. Lin, S. Yacoub, J. Burns. -New York : Hewlett-Packard Laboratories, Technical Report. 2002. - № 3. -36 P.

93. Lorczak, P. R. A Theoretical Investigation of Generalized Voters for Redundant Systems Text. / P. R. Lorczak, A.K. Caglayan, D.E. Eckhardt // Proc. 19th FTCS.- 1989.-P. 444-451.

94. Lyu, M. Handbook of Software Reliability Engineering Text. / M. Lyu . New York : McGraw-Hill and IEEE Computer Society Press. - 1996. - 208 P.

95. McAllister, D. F. Reliability of Voting in Fault-Tolerant Software Systems for Small Output Spaces Text. / D.F. McAllister, C. E. Sun, M. A. Vouk // IEEE Trans. Rel. 1990. - Vol. 39 (5). - P. 524-534.

96. McAllister, D. F. The Consensus Recovery Block Text. / K. Scott, J. W. Gault, D. F. McAllister // Proc. of the Total System Reliability Symp. 1983. - P. 7485.

97. McAllister, D. F. Fault-tolerant Software Voters Based on Fuzzy Equivalence Relations Text. / K. Kim, M. A. Vouk, D.F. McAllister // IEEE Aerospace Conference. 1998. - Vol. 4. - P. 5-19.

98. Prahami, B. Design of Reliable Software via General Combination of N-Version Programming and Acceptance Testing Text. / B. Prahami // Proc. 7th Intern. Symposium on Software Reliability Engineering ISSRE'96. 1996. - P. 1-18.

99. Parhami, B. Threshold Voting is Fundamentally Simpler than Plurality Voting Text. / B. Parhami // International Journal on Reliability, Quality, and Safety Engineering. 1994. - Vol. 1 (1). - P. 95-102.

100. Parhami, B. Voting Algorithms. Text. / B. Parhami // Transactions on Reliability. 1994. - Vol. 43. - P. 617-629.

101. Randell, B. System Structure for Software Fault-Tolerance Text. / B. Randell // IEEE Trans. Soft. Eng. 1975. - Vol. SE-1. - P. 220-232.

102. Romanovsky, A. Abstract Object State and Version Recovery in N-Version Programming Text. / A. Romanovsky // Computing Science. Technical Report Series. 1999. - № CS-TR 669. - P. 1 -13.

103. Romanovsky, A. An Exception Handling Framework for N-Version Programming in Object Oriented Systems Text. / A. Romanovsky // Computing Science. Technical Report Series. 1999. - № CS-TR 684. - P. 1-22.

104. Romanovsky, A. On N-Version Programming and Exception Handling Text. / A. Romanovsky // In Proc. of the 10th European Workshop on Dependable Computing (EWDC-10). 1999. - P. 175-179.

105. Ross, T. J. Fuzzy Logic with Engineering Applications Text. / T. J. Ross. -McGrow Hill.-1995.-96 P.

106. Rüssel, J. Resourceful Systems for Fault Tolerance, Reliability, and Safety Text. /J. Russel // ACM Computing Surveys. 1990. - Vol. 22 (1). - P. 35-68.

107. Scott, R. K. Investigating Version Dependence in Fault-Tolerant Software Text. / R. K. Scott, G. W. Gault, D.F. McAllister, J. Wiggs // AGARD 361. 1984. -P. 21.1-21.10.

108. Subramanian, S. Backup Pattern: Designing Redundancy in Object-Oriented Software. Pattern Languages of Program Design Text. / S. Subramanian, W. Tsai. New York : Addison-Wesley. - 1996. - 202 P.

109. Tailor, R. Redundant Programming in Europe Text. / R. Tailor // ACM SIGSOFT Software Engineering Notes. 1981. - Vol. 6 (1). - P. 23-30.

110. Tamura, S. Pattern Classification Based on Fuzzy Relations Text. / S. Tamura, S. Higuchi and K. Tanaka // IEEE Transactions on Systems, Man, and Cybernetics. 1971. - Vol. (1). - P 5-11.

111. Tsai, T. Fault Tolerance via N-Modular Software Redundancy Text. / T. Tsai // Proc. 28th Ann. Intern. Symp. On Fault-Tolerant Computing FTCS-28. 1998. -P. 206-210.

112. Yacoub, S. Analysis of the Behavior and Reliability of Voting Systems Comprising Tri-State Units Text. / S. Yacoub // 21st IEEE Symposium on Reliable Distributed Systems (SRDS). 2002. - P. 73- 89.

113. Yacoub, S. Analysis of the Reliability and Behavior of Majority and Plurality Voting Systems Text. / S. Yacoub, X. Lin, J. Burns. New York : Hewlett-Packard Laboratories, Technical Report. - 2002. - № 8. - 24 P.

114. Yoshimura, S. Project on Diverse Software- An Experiment in Software Reliability Text. / P. Bishop, D. Esp, M. Barnes, P. Humphreys, G. Dahl, J. Lahti, S. Yoshimura // Proceedings IFAC Workshop SAFECOMP'85. 1985. -P. 95-104.

115. Zwick, R. Measures of Similarity Among Fuzzy Concepts: A Comparative Analysis Text. / R. Zwick, E Carlstein, D. V. Budescu // International Journal of Approximate Reasoning. 1987.-№ 13. - P. 221-242.