Разработка методов и алгоритмов построения отказоустойчивых распределенных систем хранения данных на основе модулярной арифметики тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Назаров Антон Сергеевич

• Назаров Антон Сергеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Назаров Антон Сергеевич

Введение

Глава 1 Аналитический обзор, классификация распределенных систем хранения данных

1.1 Анализ причин сбоев в распределенных системах хранения данных

1.2 Надежность вычислительных систем, распределенных систем хранения и ее количественные показатели

1.3 Алгебраические коды с обнаружением и исправлением ошибок

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

1.5 Краткая характеристика методов обнаружения, поиска и исправления ошибок

1.6 Постановка задачи исследования

1.7 Выводы по первой главе

Глава 2 Разработка распределенной системы хранения данных с повышенной отказоустойчивостью на основе системы остаточных классов

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

2.2 Разработка численного метода выбора параметров избыточной системы остаточных классов для распределенного хранения данных

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

2.4 Разработка численного метода расчета расстояния Хэмминга на основе приближенного метода и ранга числа для модификации метода проекций с максимальным правдоподобием

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

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

2.5.2 Разработка базовой структуры распределенной системы хранения данных на основе избыточной системы остаточных классов

2.6 Выводы по второй главе

Глава 3 Разработка математических моделей и синтез базовых отказоустойчивых структур распределенных систем хранения данных

3.1 Разработка алгоритма и структурной схемы прямого преобразования данных в распределенных системах хранения

3.2 Разработка алгоритма и структурной схемы обратного преобразования данных в распределенных системах хранения

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

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

3.3 Выводы по третьей главе

Глава 4 Экспериментальное исследование методов обеспечения отказоустойчивости, основанных на системе остаточных классов на базе программируемых логических интегральных схем архитектуры FPGA

4.1 Моделирование базовых вычислительных структур системы остаточных классов

4.2 Моделирование методов локализации ошибок и восстановления корректных данных на основе избыточной системы остаточных классов

4.3 Сравнительный анализ моделей распределенных систем хранения данных

4.4 Выводы по четвертой главе

Заключение

Обозначения и сокращения

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

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

255

Введение диссертации (часть автореферата) на тему «Разработка методов и алгоритмов построения отказоустойчивых распределенных систем хранения данных на основе модулярной арифметики»

Введение

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

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

- возможность работы с различными типами устройств:

- с различными поставщиками устройств;

- с различными операционными системами;

- с различными аппаратными платформами.

- возможность простого расширения и масштабирования;

- перманентная (постоянная) доступность ресурсов (даже если некоторые элементы системы некоторое время могут находиться вне доступа);

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

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

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

- прозрачное местоположение ресурсов - место физического расположения требуемого ресурса должно быть несущественно для пользователя;

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

- параллельный доступ - возможность совместного (одновременного) использования одного и того же ресурса различными пользователями независимо друг от друга, при этом факт совместного использования ресурса должен оставаться скрытым от пользователя;

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

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

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

Объемы информации растут настолько стремительно, что единичные носители информации уже давно не справляются с нагрузкой. Каждую неделю Facebook требует дополнительных 60 терабайт (240 байт) памяти только для новых фотографий [40]. Пользователи YouTube загружают более 400 часов видео каждую минуту, и каждый день требуется 1 петабайт (250 байт) нового дополнительного дискового пространства [39, 77]. К 2025 году, по прогнозам аналитиков компании IDC (International Data Corporation), человечество сформирует 175 зеттабайтов (270 байт) информации.

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

Развитие СХД является актуальным вопросом в современной технике, связанным с тем фактом, что объемы хранимой и обрабатываемой информации постоянно возрастают, что приводит к увеличению потребности и стоимости хранения информации. Организации и ученые по всему миру стремятся не только развивать инфраструктуру хранения данных, но и исследовать возможности повышения эффективности СХД [35]: снижения энергопотребления, расходов на сервис, общей стоимости владения и закупки систем резервного копирования и хранения с одной стороны и повышения отказоустойчивости, масштабируемости и производительности таких систем с другой. Группа компаний ТИМ в 2008 году провела опрос среди клиентов с целью выяснить, какие характеристики наиболее важны для них при выборе СХД [35], который показал, что надежность, производительность и стоимость СХД являются ключевыми факторами при выборе таких систем.

Типовое устройство СХД предполагает следующие подсистемы и компоненты:

- устройства хранения (чаще всего дисковые массивы);

- инфраструктуру доступа к устройствам хранения;

- подсистему резервного копирования и архивирования данных;

- программное обеспечение управления хранением;

- систему управления и мониторинга.

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

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

Несмотря на значительные усилия, как в промышленности, так и науке, высокая отказоустойчивость остается серьезной проблемой в управлении крупномасштабными 1Т-системами, а предотвращение катастроф и стоимость устранения текущих поломок составляют значительную часть общей стоимости эксплуатации. Из-за увеличения количества серверов в кластерах сохранение высоких уровней отказоустойчивости и доступности является растущей проблемой для многих сайтов, высокопроизводительных вычислительных систем и провайдеров интернет-услуг. Отказоустойчивость систем хранения особенно важна по нескольким причинам. Во-первых, отказ хранилища может не только привести к временной недоступности данных, но в худшем случае это может привести к потере данных. Во-вторых, технологические тенденции и увеличение объема рынка могут в совокупности привести к тому, что сбои системы хранения в будущем будут происходить чаще [84]. Наконец, размер современных систем хранения, крупномасштабных 1Т-установок вырос до беспрецедентного масштаба с тысячами устройств хранения данных, что приводит к тому, что сбои компонентов становятся нормой, а не исключением [65].

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

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

Избыточная СОК (ИСОК) формируется путем добавления избыточных модулей в существующий набор оснований. ИСОК обладает возможностями обнаружения и исправления ошибок, сохраняя допустимый диапазон для регулярной обработки информации [1]. Ошибка по некоторым остаткам обнаруживается путем проверки того, попадает ли соответствующая величина принятого представления остатков в допустимый диапазон. В отличие от двоичных систем счисления, методы обнаружения и исправления ошибок, основанные на ИСОК, способны исправлять арифметические ошибки обработки, вызванные шумом устройства, производственными дефектами, изменениями процесса функционирования устройств или даже преднамеренным введением неисправностей в дополнение к ошибкам передачи и хранения данных [94]. Эти свойства вызвали широкий интерес к СОК со стороны инженеров, занимающихся проектированием отказоустойчивых систем. К ним можно отнести системы передачи данных [90, 101], методы отказоустойчивого распределенного хранения данных в условиях неопределенности [95], перспективные вычислительные устройства с высокой производительностью и надежностью [25].

Значительный научный вклад в теорию и практику распределенных и параллельных вычислений внесли отечественные и зарубежные исследователи: И.Я. Акушский, Д.И. Юдицкий, В.М. Амербаев, В.В. Воеводин, Вл.В. Воеводин, Н.И. Червяков, И.А. Калмыков, О.А. Финько, G. Alonso, R. Buyya, Ji. Chen, A. Chervenak, C. Gentry, B. Parhami, A. Omondi, A. Premkumar, P. Paillier, A. Tchernykh, L. Yang, D. Zhang и другие.

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

модулей возрастает с увеличением количества исправляемых остаточных ошибок, для обнаружения и исправления множественных ошибок необходимо большое количество итерационных вычислений, в результате чего их прямая аппаратная реализация будет столь же сложной, как и реализация нескольких межмодульных операций в СОК [94].

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

Объект исследования - распределенные системы хранения данных.

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

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

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

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

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

3. Модификация метода проекций с максимальным правдоподобием на основе численного метода расчета расстояния Хэмминга.

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

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

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

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

Научная новизна результатов исследования:

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

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

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

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

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

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

6. Разработаны математические методы моделирования и комплекс программ на языке VHDL для FPGA в среде Xilinx Vivado для экспериментального исследования основных функциональных блоков структурно-функциональной организации распределенных систем хранения данных на базе избыточной системы остаточных классов.

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

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

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

На защиту выносятся следующие научные положения:

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

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

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

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

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

6. Комплекс программ и математических методов моделирования основных функциональных блоков, используемых в распределенных системах хранения данных на основе избыточной системы остаточных классов в базисе ПЛИС.

Внедрение. Результаты диссертационного исследования используются в учебном процессе в СКФУ на кафедре прикладной математики и математического моделирования в дисциплинах «Обработка информации в системе остаточных

классов», «Математические и компьютерные методы обработки информации», «Математические модели и методы синтеза в сверхбольших интегральных схемах», «Основы цифровой схемотехники» и «Основы модулярной арифметики», что подтверждено Актом об использовании результатов работы в учебном процессе № 4332-07/09 от 18.09.2019. Основные научные результаты использованы в ООО «Медицина ИТ» (Акт № 154 от 12.08.2019). Кроме того, ряд результатов работы был использован при выполнении научно-исследовательских работ в базовой части государственного задания СКФУ №2.6035.2017/БЧ «Разработка математических моделей и методов снижения энергопотребления в системах мобильной связи на основе системы остаточных классов», грант РНФ №19-71-10033 «Эффективная, безопасная и отказоустойчивая система распределенного хранения и обработки конфиденциальных данных с регулируемой избыточностью для проектирования мобильных облаков на маломощных вычислительных устройствах», грант Президента Российской Федерации №МК-6294.2018.9 «Разработка и исследование методов обеспечения безопасности в мобильных неиерархических сетях на основе пороговых структур доступа», грант РФФИ №18-07-00109 «Разработка новых отказоустойчивых мобильных систем связи с низким энергопотреблением на основе интеграции параллельной математики и искусственных нейронных сетей», грант РФФИ №1907-00130 «Экономичные средства интеллектуального анализа визуальной информации на основе сверточных нейронных сетей», стипендии Президента Российской Федерации СП-1685.2019.5 «Разработка методов и алгоритмов обеспечения надежности в распределенных сетях хранения данных с использованием модулярной арифметики».

Апробация работы. Основные результаты работы были представлены на XIII Всероссийской конференции Высокопроизводительные параллельные вычисления на кластерных системах (г. Нижний Новгород, Россия, 2013 г.), VIII Международной научно-практической конференции молодых ученых «Морально-этические аспекты и темпорально-экологические императивы инвенционного процесса генерации новых научно-технических знаний» (г. Ставрополь, Россия,

2014 г.), 8-й Международной конференции «Application of Information and Communication Technologies» (г. Астана, Казахстан, 2014 г.), I-ой Международной научной конференции «Параллельная компьютерная алгебра и ее приложения в новых инфокоммуникационных системах» (г. Ставрополь, Россия, 2014 г.), Международной научно-практической конференции «Поиск моделей социально-экономического развития Юга России в новом геополитическом формате» (г. Ставрополь, Россия, 2015 г.), Международной IEEE-Сибирской конференции по управлению и связи SIBCON-2015 (г. Омск, Россия, 2015 г.), Международной конференции «Инжиниринг & Телекоммуникации - En&T 2015» (г. Долгопрудный, Россия, 2015 г.), Конференции молодых исследователей в области электротехники и электроники «2016 IEEE North West Russia Section Young Researchers in Electrical and Electronic Engineering Conference» (г. Санкт-Петербург, Россия, 2016 г.), Международной конференции «Инжиниринг & Телекоммуникации - En&T 2016» (г. Долгопрудный, Россия, 2016 г.), 8-й Международной суперкомпьютерной конференции в Мексике ISUM-2017 (г. Гвадалахара, Мексика, 2017 г.), Международной конференции по мягким вычислениям и измерениям - 2018 (г. Санкт-Петербург, Россия, 2018 г.), конкурсе «У.М.Н.И.К. Российской Федерации» с проектом «Разработка распределенной сети хранения данных на основе системы остаточных классов» (статус -победитель, г. Ставрополь, 2017 г.), конкурсе «Остроградский 2018» с проектом «Using Redundant Residue Number System to build Fault-Tolerant Storage Area Networks» (статус - победитель, г. Нанси, Франция, 2018 г.).

Публикации по теме диссертации. Основные результаты исследования опубликованы в 28 работах, среди который имеются 3 статьи в научных изданиях, входящих в перечень ВАК Министерства образования и науки, а также 10, входящих в системы индексирования научных работ Scopus и 11 -Web Of Science.

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

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

Структура диссертации. Диссертационная работа состоит из введения, 4-х глав, заключения, списка сокращений и обозначений, списка использованной литературы, содержащего 103 наименования. Основная часть работы содержит 207 страниц машинописного текста. Работа содержит 44 рисунка, 14 таблиц и 7 приложений. В диссертации принята двойная нумерация формул, рисунков и таблиц: первая цифра указывает номер главы, вторая - порядковый номер рисунка, таблицы или формулы внутри данной главы.

Краткое содержание работы.

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Назаров Антон Сергеевич, 2019 год

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

1. Акушский, И.Я. Алгоритмы деления с использованием ядерной характеристики / И.Я. Акушский, В.М. Бурцев, И.Т. Пак // Теория кодирования и оптимизации сложных систем. - Алма-Ата: Наука, 1977. - С. 26-33.

2. Акушский, И.Я. Машинная арифметика в остаточных классах / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.

3. Бабенко, М.Г. Сравнительный анализ криптосистем Рабина и Мейера -Мюллера на точках эллиптической кривой / М.Г. Бабенко, А.С. Назаров, Н.Н. Нагорнов // Морально-этические аспекты и темпорально-экологические императивы инвенционного процесса генерации новых научно-технических знаний: материалы VIII Международной научно-практической конференции молодых ученых (школьников, студентов, аспирантов). - Ставрополь: Изд-во «РИО ИДНК», 2014. - С. 500-501.

4. Дерябин, М.А. Использование модулярной арифметики для ускорения выполнения операций с числами большой разрядности / М.А. Дерябин, А.А. Зайцев // Вестник УГАТУ. - 2013. - Т. 17. - № 5 (58). - С. 245-251.

5. Исупов, К.С. Метод выполнения немодульных операций в системе остаточных классов на основе интервальных позиционных характеристик / К.С. Исупов // Фундаментальные исследования. - 2013. - № 4-3. - С. 566-570.

6. Калмыков, И.А. Математические модели нейросетевых отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов / И.А. Калмыков. - М.: Физматлит, 2005. - 276 с.

7. Корытчинко, Т.И. Применение методов повышения живучести для обеспечения защищенности в распределенных телекоммуникационных системах / Т.И. Корытчинко // Iнформацiйно-керуючi системи на залiзничному транспорт^ -2015. - № 2. - С. 52-56.

8. Кульбида, В.А. Способы помехоустойчивого кодирования и декодирования для построения систем связи с адаптацией этих способов к состоянию канала / В.А. Кульбида // Техника радиосвязи. - 2006. - № 11. - С. 4051.

9. Назаров, А.С. Обзор методов выполнения арифметических операций над числами большой разрядности на примере операции деления / А.С. Назаров // Высокопроизводительные параллельные вычисления на кластерных системах: материалы XIII Всероссийской конференции. - Н. Новгород: Изд-во Нижегородского госуниверситета, 2013. - С. 187-190.

10. Оцоков, Ш.А. Способ организации высокоточных вычислений в модулярной арифметике / Ш.А. Оцоков // Параллельная компьютерная алгебра и ее приложения в новых инфокоммуникационных системах: сб. науч. трудов I Международной конференции. - Ставрополь: Изд-во «Фабула», 2014. - С. 270277.

11. Радченко, Г.И. Распределенные вычислительные системы / Г.И. Радченко. - Челябинск: Фотохудожник, 2012. - 184 с.

12. Ронжин, П. Надежность, отказоустойчивость, доступность. Синонимы или? [Электронный ресурс] / П. Ронжин, В. Казаков // Журнал ИКС Медиа. -2015. - № 1-2 - Режим доступа: http://www.iksmedia.ru/articles/5185683-Nadezhnost-otkazoustojchivost-dostu.html#ixzz5s3kw9UUw - (Дата обращения: 15.06.2019).

13. Теслер, Г.С. Концепция создания вычислительных средств с высоким уровнем отказоустойчивости / Г.С. Теслер // Математические машины и системы. - 2002. - № 2. - С. 176-183.

14. Финько, О.А. Модулярная арифметика параллельных вычислений: монография / О.А. Финько; под ред. В.Д. Малюгина. - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2003. - 224 с.

15. Червяков, Н.И. Оптимизация процесса коррекции ошибок в системе остаточных классов за счет применения Китайской теоремы об остатках с

дробными числами / Н.И. Червяков, П.А. Ляхов, А.С. Назаров [и др.] // Инфокоммуникационные технологии. - 2018. - Том 16. - № 2. - С. 157-168.

16. Червяков, Н.И. Эффективная реализация операции вычисления остатка от деления многоразрядных чисел на FPGA / Н.И. Червяков, А.С. Назаров, Ю.В. Черногорова [и др.] // Современная наука и инновации. - 2018. - № 1 (21). -С. 15-21.

17. Червяков, Н.И. Анализ эффективности применения метода Шуфа для нахождения порядка группы точек эллиптической кривой / Н.И. Червяков, М.А. Дерябин, А.С. Назаров [и др.] // Параллельная компьютерная алгебра и её приложения в новых инфокоммуникационных системах: сб. науч. трудов I Международной конференции. - Ставрополь: Изд-во «Фабула», 2014. - С. 169176.

18. Червяков, Н.И. Безопасная и надежная передача данных в MANET на основе принципов вычислительно стойкого разделения секрета / Н.И. Червяков, М.А. Дерябин, А.С. Назаров [и др.] // Труды ИСП РАН. - 2019. - Том 31. - № 2. -С. 153-170.

19. Червяков, Н.И. Использование системы остаточных классов в сетях передачи данных на основе технологии CDMA / Н.И. Червяков, А.С. Назаров, М.А. Дерябин // Морально-этические аспекты и темпорально-экологические императивы инвенционного процесса генерации новых научно-технических знаний: материалы VIII Международной научно-практической конференции молодых ученых (школьников, студентов, аспирантов). - Ставрополь: Изд-во «РИО ИДНК», 2014. - С. 485-487.

20. Червяков, Н.И. Критерии оценки качества работы нейронных сетей, применяемых для решения задач классификации / Н.И. Червяков, А.С. Назаров, Е.С. Карнаухова // Морально-этические аспекты и темпорально-экологические императивы инвенционного процесса генерации новых научно-технических знаний: материалы VIII Международной научно-практической конференции молодых ученых (школьников, студентов, аспирантов). - Ставрополь: Изд-во «РИО ИДНК», 2014. - С. 502-504.

21. Червяков, Н.И. Метод анализа корректирующих способностей кода системы остаточных классов / Н.И. Червяков, В.В. Бережной, А.С. Назаров [и др.] // Сборник тезисов Международной конференции по мягким вычислениям и измерениям. - С.-Петербург: Изд-во Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина), 2018. -С. 372-375.

22. Червяков, Н.И. Аналитический обзор реализации проблемных операций в системе остаточных классов / Н.И. Червяков, А.С. Назаров, А.А. Индербаева // Поиск моделей социально-экономического развития Юга России в новом геополитическом формате: сборник материалов Международной научно-практической конференции. - Ставрополь: Изд-во «РИО ИДНК», 2015. -С. 722-727.

23. Червяков, Н.И. Методы, алгоритмы и техническая реализация основных проблемных операций, выполняемых в системе остаточных классов / Н.И. Червяков // Инфокоммуникационные технологии. - 2011. - № 4. - С. 4-12.

24. Червяков, Н.И. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Н.И. Червяков, А.В. Шапошников, С.А. Ряднов. -М.: Физматлит, 2002. - 288 с.

25. Червяков, Н.И. Нейрокомпьютеры в остаточных классах / Н.И. Червяков, П.А. Сахнюк, А.В. Шапошников [и др.]. - М.: Радиотехника, 2003. - 272 с.

26. Червяков, Н.И. Приближенный метод выполнения немодульных операций в системе остаточных классов / Н.И. Червяков, В.М. Авербух, М.Г. Бабенко [и др.] // Фундаментальные исследования. - 2012. - № 6-1. - С. 189193.

27. Червяков, Н.И. Применение искусственных нейронных сетей и системы остаточных классов в криптографии / Н.И. Червяков, А.А. Евдокимов, А.И. Галушкин [и др.]. - М.: Физматлит, 2012. - 280 с.

28. Червяков, Н.И. Программа для определения корректирующих свойств избыточной системы остаточных классов / Н.И. Червяков, В.В. Бережной, А.С.

Назаров [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2018666425, РФ. Зарегистрировано в Реестре программ для ЭВМ 17.12.2018 г.

29. Червяков, Н.И. Программа управления устройством коррекции однократных ошибок на основе Китайской теоремы об остатках / Н.И. Червяков, А.С. Назаров, М.А. Дерябин // Свидетельство о государственной регистрации программы для ЭВМ № 2018665971, РФ. Зарегистрировано в Реестре программ для ЭВМ 11.12.2018 г.

30. Червяков, Н.И. Программа управления устройством перевода чисел из системы остаточных классов в позиционную систему счисления на основе Китайской теоремы об остатках / Н.И. Червяков, И.А. Калмыков, А.С. Назаров [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2016618400, РФ. Зарегистрировано в Реестре программ для ЭВМ 28.07.2016 г.

31. Червяков, Н.И. Программа управления устройством перевода чисел из системы остаточных классов в позиционную систему счисления на основе Китайской теоремы об остатках с дробными числами / Н.И. Червяков, М.Г. Бабенко, А.С. Назаров [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2016618315, РФ. Зарегистрировано в Реестре программ для ЭВМ 26.07.2016 г.

32. Червяков, Н.И. Программа управления устройством перевода чисел из системы остаточных классов в позиционную систему счисления на основе перевода в обобщенную позиционную систему счисления / Н.И. Червяков, М.Г. Бабенко, А.С. Назаров [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2016618312, РФ. Зарегистрировано в Реестре программ для ЭВМ 26.07.2016 г.

33. Червяков, Н.И. Ускоренный метод вычисления остатка от деления с использованием распределенной арифметики / Н.И. Червяков, М.Г. Бабенко, А.С. Назаров [и др.] // Свидетельство о государственной регистрации программы для ЭВМ № 2016612432, РФ. Зарегистрировано в Реестре программ для ЭВМ 26.02.2016 г.

34. Червяков, Н.И. Эффективные методы обработки данных при множественном их представлении в модулярных нейрокомпьютерах / Н.И. Червяков, И.В. Дьяченко, И.Н. Лавриненко [и др.] // Нейрокомпьютеры. - 2005. -№ 7. - С. 51-63.

35. Система хранения данных [Электронный ресурс] // TAdviser - Режим доступа: http ://www.tadviser.ru/ index.php/Статья : Система_хранения_данных (Дата обращения: 15.07.2019).

36. ГОСТ 27.002-2015. Надежность в технике. Термины и определения. -М: Стандартинформ, 2018. - 25 с.

37. Abu-Libdeh, H. RACS: A case for cloud storage diversity / H. Abu-Libdeh, L. Princehouse, H. Weatherspoon // Cloud Computing: Proceedings of the 1st ACM Symposium, SoCC'10. - Indianapolis, Indiana, USA: ACM Press, 2010. - P. 229-239.

38. Asmuth, C.A. Modular Approach to Key Safeguarding / C.A. Asmuth, J.A. Bloom // IEEE Transactions on Information Theory. - 1983 - Vol. 29. - No. 2. - P. 208-210.

39. Baesens, B. Analytics in a Big Data World: The Essential Guide to Data Science and its Applications / B. Baesens. - New York City, New York, USA: John Wiley & Sons, 2014. - 256 p.

40. Beaver, D. Finding a Needle in Haystack: Facebook's Photo Storage / D. Beaver, S. Kumar, H. Li [et al.] // Operating Systems Design and Implementation (OSDI): Proceedings of USENIX Symposium. - Vancouver, British Columbia, Canada: ACM Press, 2010. - Vol. 10. - No. 2010. - P. 1-8.

41. Bessani, A. DepSky: dependable and secure storage in a cloud-of-clouds / A. Bessani, M. Correia, B. Quaresma [et al.] // ACM Transactions on Storage. - 2013. -Vol. 9, No. 4. - P. 12:1-12:33.

42. Blahut, R.E. Theory and practice of error control codes / R.E. Blahut. -Reading, Massachusetts, USA: Addison-Wesley, 1983. - 500 p.

43. Braband, J. Probability of failure on demand - The why and the how / J. Braband, R. VomHovel, H. Schâbe // Computer Safety, Reliability, and Security:

Proceedings of International Conference. - Berlin, Germany: Springer, 2009. - P. 4654.

44. Brewer, E. Disks for Data Centers / E. Brewer, L. Ying, L. Greenfield [et al.] // Write Paper from Google. - 2016. - P. 1-16.

45. Chen, C.P. Data-intensive applications, challenges, techniques and technologies: A survey on Big Data / C.P. Chen, C.Y. Zhang // Information Sciences. -2014. - Vol. 275. - P. 314-347.

46. Chervyakov, N. AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security / N. Chervyakov, M. Babenko, A. Tchernykh [et al.] // Future Generation Computer Systems. - 2019. - Vol. 92. -P. 1080-1092.

47. Chervyakov, N. Towards reliable low cost distributed storage in multi-clouds / N. Chervyakov, M. Babenko, A. Tchenykh [et al.] // Control and Communications: Proceedings of the 2017 International Siberian Conference, SIBCON 2017. - Astana, Kazakhstan: IEEE, 2017. - P. 1-5.

48. Chervyakov, N.I. A High-Speed Division Algorithm for Modular Numbers Based on the Chinese Remainder Theorem with Fractions and Its Hardware Implementation / N.I. Chervyakov, P.A. Lyakhov, A.S. Nazarov [et al.] // Electronics. -2019. - Vol. 8. - No. 3. - P. 261.

49. Chervyakov, N.I. A new model to optimize the architecture of a fault-tolerant modular neurocomputer / N.I. Chervyakov, P.A. Lyakhov, A.S. Nazarov [et al.] // Neurocomputing. - 2018. - Vol. 303. - P. 37-46.

50. Chervyakov, N.I. Computation of positional characteristics of numbers in RNS based on approximate method / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Electrical and Electronic Engineering Conference: Proceedings of IEEE NW Russia Young Researchers Conference (EIConRusNW). - St. Petersburg: IEEE, 2016. -P. 177-179.

51. Chervyakov, N.I. Cryptanalysis of secret sharing schemes based on spherical spaces / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Application of

Information and Communication Technologies: Proceedings of the 2014 IEEE 8th International Conference. - Astana, Kazakhstan: IEEE, 2014. - P. 11-15.

52. Chervyakov, N.I. Development of the protected data transfer protocol for the MANET networks on the basis of residue number system / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Control and Communications: Proceedings of the 2015 IEEE International Siberian Conference, SIBCON 2015. - Omsk: IEEE, 2015.

- P. 1-5.

53. Chervyakov, N.I. Realization Problems of Cryptographic Transformations by Transfer of Modular Data In Security Systems / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Control and Communications: Proceedings of the 2015 IEEE International Siberian Conference, SIBCON 2015. - Omsk: IEEE, 2015. - P. 1-5.

54. Chervyakov, N.I. Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem / N.I. Chervyakov, A.S. Molahosseini, P.A. Lyakhov [et al.] // International Journal of Computer Mathematics. - 2017. - Vol. 94. - No. 9. - P. 1833-1849.

55. Chervyakov, N.I. The architecture of a fault-tolerant modular neurocomputer based on modular number projections / N.I. Chervyakov, P.A. Lyakhov, A.S.Nazarov [et al.] // Neurocomputing. - 2018. - Vol. 272. - P. 96-107.

56. Chervyakov, N.I. The Development of Probabilistic Algorithm Of Monitoring A Result Correctness for Cloud Computing in Residue Number System / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Engineering & Telecommunication - En&T-2015: Proceedings of International Conference. -Moscow, Russia: IEEE, 2015. - P. 196-198.

57. Chervyakov, N.I. The Fast Algorithm for Number Comparing in Three-Modular RNS / N.I. Chervyakov, M.G. Babenko, A.S. Nazarov [et al.] // Engineering and Telecommunication - En&T-2016: Proceedings of the III International Conference.

- Moscow, Russia: IEEE, 2016. - P. 26-28.

58. Chervyakov, N.I. An Approximate Method for Comparing Modular Numbers and its Application to the Division of Numbers in Residue Number Systems /

N.I. Chervyakov, M.G. Babenko, P.A. Lyakhov [et al.] // Cybernetics and Systems Analysis. - 2014. - Vol. 50. - No. 6. - P. 977-984.

59. Chervyakov, N.I. An efficient method of error correction in fault-tolerant modular neurocomputers / N.I. Chervyakov, P.A. Lyakhov, M.G. Babenko [et al.] // Neurocomputing. - 2016. - Vol. 205. - P. 32-44.

60. Deryabin, M. Comparative Performance Analysis of Information Dispersal Methods / M. Deryabin, N. Chervyakov, A. Nazarov [et al.] // FRUCT: Proceedings of the 24th Conference of Open Innovations Association. - Moscow, Russia: IEEE, 2019.

- P. 67-74.

61. Deryabin, M. Secure verifiable secret short sharing scheme for multi-cloud storage / M. Deryabin, N. Chervyakov, A. Tchernykh [et al.] // High Performance Computing and Simulation (HPCS): Proceedings of the 2018 International Conference.

- Orleans, France: IEEE, 2018. - P. 700-706.

62. Diamauro, G. A New Technique for Fast Number Comparison in the Residue Number System / G. Diamauro, S. Impedovo, G. Pirlo // IEEE Transactions on Computers. - 1993. - Vol. 42. - No. 5. - P. 608-612.

63. Ding, C. Chinese remainder theorem: applications in computing, coding, cryptography / C. Ding, D. Pei, A. Salomaa. - Singapore: World Scientific, 1996. -214 p.

64. Ford, D. Availability in Globally Distributed Storage Systems / D. Ford, F. Labelle, F.I. Popovici [et al.] // Operating Systems Design and Implementation (OSDI): Proceedings of the 9th USENIX Conference. - Vancouver, British Columbia, Canada: ACM Press, 2010. - P. 61-74.

65. Ghemawat, S. The Google file system / S. Ghemawat, H. Gobioff, S.-T. Leung // Operating Systems Principles: Proceedings of the 19th ACM Symposium, SOSP'03. - Bolton Landing, New York, USA: ACM Press, 2003. - Vol. 37. - No. 5. -P. 29-43.

66. Goh, V.T. Multiple error detection and correction based on redundant residue number systems / V.T. Goh, M.U. Siddiqi // IEEE Transactions on Communications. - 2008. - Vol. 56. - No. 3. - P. 325-330.

67. Gunawi, H.S. Data Reliability in Highly Fault-tolerant Cloud Systems [Электронный ресурс] / H.S. Gunawi, T. Do, P. Joshi [et al.] // Hot Dep. Usenix - The Advanced Computing System Association. - 2010. - Режим доступа: http://www.usenix.org/events/hotdep10/tech/full_papers/Gunawi.pdf -(Датаобращения: 15.06.2019).

68. Haron, N.Z. Redundant residue number system code for fault-tolerant hybrid memories / N.Z. Haron, S. Hamdioui // ACM Journal on Emerging Technologies in Computing Systems. - 2011. - Vol. 7. - No. 1. - P. 1-19.

69. Huang, C. Erasure coding in windows azure storage / C. Huang, H. Simitci, Y. Xu [et al.] // Annual Technical Conference: Proceedings of USENIX Conference. -Boston, Massachusetts, USA: USENIX Association, 2012. - P. 15-26.

70. Hughes, G.F. Improved Disk-Drive Failure Warnings / G.F. Hughes, J.F. Murray, K. Kreutz-Delgado [et al.] // IEEE Transactions on Reliability. - 2002. -Vol. 51. - No. 3. - P. 350-357.

71. Hwang, K. Computer arithmetic principles, architecture, and design / K. Hwang. - New York City, New York, USA: John Wiley & Sons, 1979. - 423 p.

72. Li, J. Erasure coding for cloud storage systems: a survey / J. Li, B. Li // Tsinghua Science and Technology. - 2013. - Vol. 18. - No. 3. - P. 259-272.

73. Li, W. A Novel Cost-Effective Dynamic Data Replication Strategy for Reliability in Cloud Data Centres / W. Li, Y. Yang, D. Yuan // Dependable, Autonomic and Secure Computing: Proceedings of the 2011 IEEE Ninth International Conference. - Sydney, Australia: IEEE, 2011. - P. 496-502.

74. Mesnier, M. Storage area networking - Object-based storage / M. Mesnier, G.R. Ganger, E. Riedel // IEEE Communications Magazine. IEEE Press. - 2003. -Vol. 41. - No. 8. - P. 84-90.

75. Mignotte, M. How to Share a Secret / M. Mignotte // Workshop on Cryptography. - 1982. - P. 371-375.

76. Muralidhar, S. f4: Facebook's Warm BLOB Storage System / S. Muralidhar, W. Lloyd, S. Roy [et al.] // Operating Systems Design and Implementation (OSDI):

Proceedings of the 11th USENIX Symposium. - Broomfield, Colorado, USA: ACM Press, 2014. - P. 383-398.

77. Nachiappan, R. Cloud storage reliability for Big Data applications: A state of the art survey / R. Nachiappan, B. Javadi, R.N. Calheiros [et al.] // Journal of Network and Computer Applications. - 2017. - Vol. 97. - P. 35-47.

78. Nazarov, A. Reliability Improvement of Information Systems by Residue Number System Code / A. Nazarov, N. Chervyakov, A. Tchernykh [et al.] // International Journal of Combinatorial Optimization Problems and Informatics. - 2010. - Vol. 9. - No. 1. - P. 81-84.

79. Nelson, V.P. Fault-tolerant computing: fundamental concepts / V.P. Nelson // Computer. - 1990. - Vol. 23. - No. 7. - P. 19-25.

80. Omondi, A. Residue Number Systems. Theory and Implementation / A. Omondi, B. Premkumar. - London, England: Imperial College Press, 2007. - 296 p.

81. Orton, G.A. New fault tolerant techniques for residue number systems / G.A. Orton, L.E. Peppard, S.E. Tavares // IEEE Transactions on Computers. - 1992. - Vol. 41. - No. 11. - P. 1453-1464.

82. Pinheiro, E. Failure trends in a large disk drive population / E. Pinheiro, W. Weber, L. Barroso // File and Storage Technologies: Proceedings of the 5th USENIX Conference, FAST 2007. - San Jose, California, USA: ACM Press, 2007. -P. 17-28.

83. Plank, J.S. Erasure codes for storage systems: A brief primer / J.S. Plank // USENIX Magazine. - 2013. - Vol. 38. - P. 44-51.

84. Prabhakaran, V. IRON file systems / V. Prabhakaran, L.N. Bairavasundaram, N. Agrawal [et al.] // Operating systems principles: Proceedings of the 20th ACM symposium, SOSP'05. - New York City, New York, USA: ACM Press, 2005. - Vol. 39. - No. 5. - P. 206-220.

85. Rabin, M.O. Efficient dispersal of information for security, load balancing, and fault tolerance / M.O. Rabin // Journal of the ACM. - 1989. - Vol. 36. - No. 2. -P. 335-348.

86. Rajasekharan, A. Data Reliability in Highly Fault-tolerant Cloud Systems [Электронный ресурс] / A. Rajasekharan // Seagate Point of View. - 2014. - Режим доступа: https://www.seagate.com/files/www-content/_shared/_masters/category-info/data-reliability-fault-tolerant-cloud-pv0031-1-1410-us.pdf. - (Дата обращения: 15.06.2019).

87. Sathiamoorthy, M. XORing elephants: novel erasure codes for big data / M. Sathiamoorthy, M. Asteris, D. Papailiopoulos [et al.] // Proceedings of the VLDB Endowment. - 2013. - Vol. 6. - No. 5. - P. 325-336.

88. Schroeder, B. Understanding disk failure rates: What does an MTTF of 1,000,000 hours mean to you? / B. Schroeder, G.A. Gibson // ACM Transactions on Storage (TOS). - 2007. - Vol. 3. - No. 3. - P. 8.

89. Shvachko, K. The Hadoop distributed file system / K. Shvachko, H. Kuang, S. Radia [et al.] // Mass Storage Systems and Technologies: Proceedings of the 2010 IEEE 26th Symposium, MSST 2010. - Incline Village, Nevada, USA: IEEE, 2010. -P. 1-10.

90. Singh, T. Residue number system for fault detection in communication networks / T. Singh // Medical Imaging, m-Health and Emerging Communication Systems: Proceedings of the 2014 International Conference (MedCom). - Greater Noida, India: IEEE, 2014. - P. 157-161.

91. Singleton, R. Maximum distance g-nary codes / R. Singleton // IEEE Transactions on Information Theory. - 1964. - Vol. 10. - No. 2. - P. 116-118.

92. Szabados, D. Diving into "MTBF" and "AFR": Storage Reliability Specs Explained [Электронный ресурс] / D. Szabados // Inside IT Storage. Seagate Enterprise - 2010. - Режим доступа: https://web.archive.org/web/20100501151901/http:/enterprise.media.seagate.com/2010/ 04/inside-it-storage/diving-into-mtbf-and-afr-storage-reliability-specs-explained/ -(Дата обращения: 15.06.2019).

93. Szabo, N.S. Residue Arithmetic and Its Application to Computer Technology / N.S. Szabo, R.I. Tanaka. - New York City, New York, USA: McGraw-Hill, 1967. - 236 p.

94. Tay, T.F. Fault-tolerant computing in redundant residue number system / T.F. Tay, C.H. Chang // Embedded Systems Design with Special Arithmetic and Number Systems. - Cham, Switzerland: Springer, 2017. - P. 65-88.

95. Tchernykh, A. Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability [In Press] / A. Tchernykh, U. Schwiegelsohn, E. Talbi [et al.] // Journal of Computational Science. - 2016. - P. 9.

96. Tchernykh, A.N. An Approach for Mitigating Cloud Computing Uncertainty by Modular Data Encryption / A.N. Tchernykh, N.I. Chervyakov, A.S. Nazarov [et al.] // Engineering and Telecommunication - En&T-2016: Proceedings of the III International Conference. - Moscow, Russia: MIPT, 2016. - P. 62-64.

97. Vishwanath, K.V. Characterizing cloud computing hardware reliability / K.V. Vishwanath, N. Nagappan // Cloud computing: Proceedings of the 1st ACM symposium. - Indianapolis, Indiana, USA: ACM Press, 2010. - P. 193-204.

98. Vu, T.V. Efficient implementations of the Chinese Remainder Theorem for sign detection and residue decoding / T.V. Vu // IEEE Transactions on Computers. -1985. - Vol. C-34. - No. 7. - P. 646-651.

99. Wicker, S.B. Error control systems for digital communication and storage / S.B. Wicker. - Englewood Cliffs, New Jersey, USA: Prentice Hall, 1995. - 512 p.

100. Wicker, S.B. Reed-Solomon codes and their applications / S.B. Wicker, V.K. Bhargava. - New York City, New York, USA: IEEE Communications Society. IEEE Information Theory Society. IEEE Press, 1994. - 322 p.

101. Yang, L.-L. Performance of residue number system based DS-CDMA over multipath fading channels using orthogonal sequences / L.-L. Yang, L. Hanzo // European Transactions on Telecommunications. - 1998. - Vol. 9. - No. 6. - P. 525536.

102. Zaharia, M. Spark: Cluster computing with working sets / M. Zaharia, M. Chowdhury, M.J. Franklin [et al.] // Hot topics in cloud computing: Proceedings of the 2nd USENIX Conference, Hot Cloud'10. - Boston, Massachusetts, USA: ACM Press, 2010. - P. 10-10.

103. Zeng, W. Research on cloud storage architecture and key technologies / W. Zeng, Y. Zhao, K. Ou [et al.] // Interaction Sciences Information Technology, Culture and Human: Proceedings of the 2nd International Conference, ICIS'09. Seoul, Korea: ACM Press, 2009. - P. 1044-1048.

ПРИЛОЖЕНИЕ 1

Алгоритм выбора оснований избыточной СОК

b

Шаг 1. p^ = 2k

2

Шаг 2. i = 1.

Шаг 3. Ptemp = pk 1" 1

Шаг 4. Пока i <

k 2

и pte^„ > 1 выполняем Шаг 4.1.

temp

Шаг 4.1.

Если НОК

= Рг

Р

-i+1

Р

-i+1

х... х p

.., p х ... х p

+i-1

■ ptemp

+i-1

х pe

emp'

то выполнить Шаги 4.1.1 - 4.1.5,

иначе ptemp = ptemp " 1, выполнить Шаг 4.

Шаг 4.1.1. p

pe

emp•

Шаг 4.1.2. ptemp = prk 1 +1.

+i-1

Шаг 4.1.3.

Пока НОК

p

г k ' p -i г k ' ,...,p г k '

2 2 2

+i-1

p

emp

Ф

Ф p г k ' х... х p г k ' х ... х p " k'

2 -i 2 2

+i-1

х pe

emp

или

p г k ' х ... х p " k' х ... х p " k'

2 -i 2 2

+i-1

b(2i+1)

X ptemp < 2 k =

выполнить ptemp = ptemp + 1.

Шаг 4.1.4. p

+i

= pe

emp•

Шаг 415. ptemp = p

- 1.

<

<

i = i + 1, переходим к Шагу 4. Шаг 5. Для j = 1..2i -1 выполнить pj = p

j+

Шаг 6. Для j = 2i..n выполнить Шаги 6.1 -6.3.

ШаГ 61 Ptemp = P2i-1 +1

<Пока НОК (p1,..., Pj-1, Ptemp P X ... X P, , X

Шаг 6.2.

* P1 X ...X Pj-1 X Ptemp, bj

или P1 X ...X Pj-1 X Ptemp < 2 k ,

выполнить Ptemp = Ptemp + 1.

Шаг 63 Pj = Ptemp •

Шаг 7. bp} = Llog2 (Pn )J +1, i = 1..n.

Шаг 8. p* = }-1.

Шаг 9.

Если

■ b 2 k

mod 2 = 1, то p

k-1

2 k

иначе p Шаг 10. i = 1.

k-1 2

' b' 2 k

+1.

Шаг 11. Ptemp = Pfk-1"- 2.

Шаг 12. Пока i <

2

k - 1 2

и ptemp > 1 выполняем Шаг 12.1.

Шаг 12.1.

Если НОК

= P

P

" k -1" ,...,P " k -1" ,...,P " k-1"

-i+1

2 2 2

+i-1

>p

temp

" k -1" X ... X p -i+1 " k -1" X ... X p " k-1" +i

2 2 2

X p,

temp''

то выполнить Шаги 12.1.1 -12.1.5,

иначе ptemp = ptemp - 2, выполнить Шаг 12.

Шаг 12.1.1. p

k-1

"2"

Ptemp.

Шаг 1212 Ptemp = P

k-1

+ 2.

+i-1

<

*

2

*

*

*

*

*

*

*

*

-i

*

Шаг 12.1.3.

/

Пока НОК

*

* Р

Р

" k-1" p " k -1" p " к -1"

2 -i 2 2

+z-1

, Ре

emp

*

" к-1" X ...X p -i " к-1" X ...X p " к-1" X ptemp +i-1

2 2 2

< или

p " к-1" X ... X p " к-1" X ... X p " к-1"

2 -i 2 2

+z-1

b(2i+1)

X Ptemp < 2 ^ S

выполнить Ptemp = Ptemp + 2

Шаг 12.1.4. p

к-l

p,

temp•

Шаг 12.1.5. ptemp = p

к-l 2

- 2.

i = i + 1, переходим к Шагу 12.

Шаг 13. Для j = 1..2i-1 выполнить p* = p

j+

к-l

Шаг 14. Для j = 2i..n-1 выполнить Шаги 14.1 -14.3.

Шаг 141 ptemp = p*i-1 + 2.

Пока НОК(p*,..., pj-1, p^p )*

Шаг 14.2.

j-1,ptemp! ' p1 X ... X pj-1 X ptemp, bj

p* X ... X pj-1 X ptemp < 2 k

или

выполнить ptemp , temp

temp ptemp + 2.

Шаг 143 pj = ptemp.

Шаг 15. Отсортировать по возрастанию {pj}, j = 0..n-1 и перенумеровать начиная с 1.

+1, i = 1..n.

к

Шаг 16. b{pj } = LlQg2 (pj 1-

Если b{pj} = b{pt} и J^pj > 2, то {pj},

Шаг 17.

i=1

иначе {pi}, i = 1..n.

*

*

*

*

*

2

*

-z

-z

2

*

V

Пример выбора оснований избыточной СОК

Подберем систему оснований для (2, 4) избыточной СОК (к = 2, п = 4), обеспечивающую 4-битный диапазон (Ь = 4). Шаг 1. рх = 4. Шаг 2. I = 1.

Шаг 3. р^р = р -1 = 4-1 = 3.

Шаг 4. 1 < 1 и 3 > 1, условие не выполняется, переходим к Шагу 5. Шаг 5. р1 = р1 = 4.

Шаг 6. Для у = 2..4 выполнить Шаги 6.1 — 6.3. ] = 2:

Шаг 6.1. р1етр = р +1 = 4 +1 = 5.

42

Шаг 6.2. (НОК(4,5) = 20) = (4 х 5 = 20), (4 х 5 = 20) > (2Т = 16). Шаг 6.3. р2 = 5.

] = 3:

Шаг 6.1. р(етр = р2 + 1 = 5 + 1 = 6.

Шаг 6.2. (НОК(4,5,6) = 30) * (4х 5 х 6 = 120),

43

(4 х 5 х 6 = 120) > (2Т = 64),

ргетр = 6 + 1 = 7

(НОК(4,5,7) = 140) = (4 х 5 х 7 = 140),

43

(4 х 5 х 7 = 140) > (2Т = 64). Шаг 6.3. р3 = 7.

] = 4:

Шаг 6.1. р^р = р3 +1 = 7 +1 = 8.

Шаг 6.2. (НОК(4,5,7,8) = 280) * (4 х 5 х 7х 8 = 1120),

44

(4 х 5 х 7 х 8 = 1120) > (2Т = 256), ретр = 8 + 1 = 9.

(НОК(4,5,7,9) = 1260) = (4 х 5 х 7 х 9 = 1260),

44

(4 х 5 х 7 х 9 = 1260) > (2Т = 256). Шаг 6.3. р4 = 9. Шаг 7. Ьр} = [1оё2 (р4 )] +1 = |_1®&2 (9)|+1 = 4.

Шаг 8. p* = 8.

Шаг 9. pj

4 22

+1 = 5.

Шаг 10. i = 1.

Шаг 11. рт = р*- 2 = 5 -2 = 3.

Шаг 12. 1 < 1 и 3 > 1, условие не выполняется, переходим к Шагу 13.

_ _ * *

Шаг 13. р1 = р1 = 5.

Шаг 14. Для у = 2..3 выполнить Шаги 14.1 -14.3. ] = 2:

Шаг 14.1. рт = р* + 2 = 5 + 2 = 7.

42 2

j = 3:

Шаг 14.2. (НОК(5,7) = 35) = (5 х 7 = 35), (5 х 7 = 35) > (2 2 = 16). Шаг 14.3. р* = 7.

Шаг 14.1. рт = р* + 2 = 7 + 2 = 9.

Шаг 14.2. (НОК(5,7,9) = 315) = (5 х7 х9 = 315),

43

(5 х 7 х 9 = 315) > (2Т = 64).

Шаг 14.3. р3* = 9.

^ ^ ^ ^

Шаг 15. р1 = 5, р2 = 7, р3 = 8, р* = 9. Шаг 16. Ьр) = |_1о§2(р4)]+1 = [1оЕ2(9)] +1 = 4.

Шаг 17. 4 = 4,(5 х 7 = 35) > (24 = 16), используем набор оснований со степенью двойки

Л = 5 р2 = 7 р3 = 8, р4 = 9.

Программный комплекс для выбора оснований избыточной СОК

> restart;

> #Разрядность чисел переводимых в СОК b:=32;

Ъ :=32

> #Требуемое количество рабочих оснований k:=20;

#Общее количество оснований n:=23;

m:=array(1..n): m_2:=array(1..n):

k\= 20 n~ 23

> #Набор без степени двойки

> m_mid:=evalf(2A(b/k)): m[ceil(k/2)]:=ceil(m_mid): M_temp:=m[ceil(k/2)]: i:=1:

m_temp:=m[ceil(k/2)]-1:

while i<ceil(k/2) and m_temp>1 do

if lcm(M_temp,m_temp)=M_temp*m_temp then m[ceil(k/2)-i]:=m_temp: M_temp:=M_temp*m[ceil(k/2)-i]: m_temp:=m[ceil(k/2)+i-1]+1:

while lcm(M_temp,m_temp)<>M_temp*m_temp or M_temp*m_temp<m_midA(2*i+1) do m_temp:=m_temp+1: end do:

m[ceil(k/2)+i]:=m_temp: M_temp:=M_temp*m[ceil(k/2)+i]: m_temp:=m[ceil(k/2)-i]-1: i:=i+1: else m_temp:=m_temp-1: end if: end do:

for j from 1 to 2*i-1 do m[j]:=m[j+ceil(k/2)-i]: end do:

for j from 2*i to n do m_temp:=m[2*i-1]+1:

while lcm(M_temp,m_temp)<>M_temp*m_temp do

m_temp:=m_temp+1: end do: m[j]:=m_temp: M_temp:=M_temp*m[j]: end do: #Проверка M_din:=1:

for i from 1 to k do M_din:=M_din*m[i]: end do:

if M_din<2Ab then print("Ошибка!!!") end if:

b_m:=trunc(log[2](m[n]))+1;

print(m);

b m := 7

[345711 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 ]

> #Набор со степенью двойки

> m_0:=2A(b_m-1):

m_mid:=evalf(2A((b-b_m+1)/(k-1))): if ceil(m_mid) mod 2 = 1 then

m_2[ceil((k-1)/2)]:=ceil(m_mid): else m_2[ceil((k-1)/2)]:=ceil(m_mid)+1: end if:

M_temp:=m_2[ceil((k-1)/2)]: i:=1:

m_temp:=m_2[ceil((k-1)/2)]-2:

while i<ceil((k-1)/2) and m_temp>1 do

if lcm(M_temp,m_temp)=M_temp*m_temp then m_2[ceil((k-1)/2)-i]:=m_temp: M_temp:=M_temp*m_2[ceil((k-1)/2)-i]: m_temp:=m_2[ceil((k-1)/2)+i-1]+2: while lcm(M_temp,m_temp)<>M_temp*m_temp or M_temp*m_temp<m_midA(2*i+1) do m_temp:=m_temp+2: end do:

m_2[ceil((k-1)/2)+i]:=m_temp: M_temp:=M_temp*m_2[ceil((k-1)/2)+i]: m_temp:=m_2[ceil((k-1)/2)-i]-2: i:=i+1:

else m_temp:=m_temp-2: print(m_temp); end if: end do:

for j from 1 to 2*i-1 do

m_2[j]:=m_2[j+ceil((k-1)/2)-i]: end do:

for j from 2*i to n-1 do m_temp:=m_2[2*i-1]+2:

while lcm(M_temp,m_temp)<>M_temp*m_temp do

m_temp:=m_temp+2: end do:

m_2[j]:=m_temp: M_temp:=M_temp*m_2[j]: end do:

#Сортировка набора оснований со степенью двойки в порядке возрастания

for i from 1 while (m_0>m_2[i] and i<n) do end do:

for j from n by -1 to i+1 do

m_2[j]:=m_2[j-1]: end do: m 2[i]:=m 0:

#Проверка

M_2_din:=1:

for i from 1 to k do