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

• Миногин, Андрей Владимирович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Миногин, Андрей Владимирович

Введение.

Глава 1. Современное состояние предметной области.

1.1. Распределенные вычислительные системы.

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

1.3. Отказоустойчивые системы. Репликация и восстановление.

1.4. Возвратное восстановление.

1.5. Метод фиксации контрольных точек.

1.6. Метод журналирования событий.

1.7. Фатальные сбои и распространяющиеся сбои.

1.8. Прозрачность методик восстановления.

Глава 2. Адаптивная математическая модель восстановления распределенной системы.

2.1. Предпосылки создания адаптивной модели.

2.2. Формальная постановка задачи.

2.3. Построение математической модели.

2.4. Применение адаптивных методов для повышения эффективности модели.

2.5. Построение модели в условиях вероятностного характера сведений об ошибках.

Глава 3. Методика реализации модели на классе многоагентных систем

3.1. Многоагентные системы.

3.2. Спецификации многоагентных систем.

3.3. Недетерминированные события.

3.4. Реализация модели восстановления.

3.5. Дополнительные технические вопросы.

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

Актуальность работы

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

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

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

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

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

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

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

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

1. возможность программных распространяющихся сбоев;

2. невозможность определения истинных причин сбоя;

3. возможность распределенного характера системы мониторинга;

4. максимальная прозрачность системы восстановления для разработчика и конечного пользователя.

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

Для практической реализации построенной модели и исследования особенностей ее поведения был выбран класс многоагентных систем. Направление многоагентных систем является актуальным и быстро развивающимся, так как парадигма агентного программирования предлагает новые возможности для построения распределенных программных комплексов и интернет-ориентированных приложений [44]. Основная идея парадигмы многоагентного программирования - использование автономных мобильных программных объектов, называемых агенты. Агенты взаимодействуют между собой и с внешней средой посредством отправки сообщений. Система взаимодействующих агентов хорошо моделирует систему взаимодействующих конечных автоматов и, следовательно, удобна для реализации модели восстановления распределенной системы.

Цели диссертационной работы

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

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

3. Реализация модели восстановления распределенных систем на классе многоагентных систем с использованием многоагентной платформы JADE. Методы исследования

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

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

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

Практическая значимость работы

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

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

Апробация работы и публикации

По теме диссертации опубликовано 9 работ, в том числе одна [9] — в издании из списка, рекомендованного ВАК РФ.

Результаты работы докладывались на XLVIII научной конференция МФТИ (Долгопрудный-Москва, 2005 г.), международной научной конференции «Технологии Microsoft в теории и практике программирования» (Москва, 2006 г.), XVI международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2007 г.), международной конференции AIS/CAD (Дивноморск, 2007 г.), международной конференции «Компьютерные науки и технологии» (Белгород, 2009 г).

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

Положения, выносимые на защиту

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

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

2. Адаптивная математическая модель восстановления распределенной вычислительной системы в условиях вероятностного характера информации о детектируемых ошибках.

3. Методика реализации адаптивной модели восстановления на классе многоагентных систем.

Структура и объем работы

Диссертация состоит из введения, трех глав, заключения, списка использованных источников и одного приложения. Работа изложена на 108 страницах, список использованных источников содержит 59 наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Миногин, Андрей Владимирович

Заключение

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

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

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

3. Предложенные модели реализованы на классе многоагентных систем в рамках многоагентной платформы JADE.

Список литературы диссертационного исследования кандидат физико-математических наук Миногин, Андрей Владимирович, 2009 год

1. Миногин А.В., Дубовик Г.А. Верифицируемая многоагентная платформа LiveNAP // Технологии Microsoft в теории и практике программирования: Труды Всероссийской конференции студентов, аспирантов и молодых ученых / МГТУ им. Н.Э. Баумана М., 2006. - С. 23-24.

2. Миногин А.В. Методика возвратного восстановления высоко распределенной системы с ненадежными каналами коммуникации // Компьютерные науки и технологии: Труды Международной научно-технической конференции — Белгород: БелГУ, 2009. С. 34-38.

3. Дубовик Г.А., Миногин А.В., Устюжанин А.Е. Устранение аномалий взаимодействия автоматов в системах с перестановкой символов. // Модели и методы обработки информации: Сборник статей. М.: МФТИ, 2009. - С. 223-230.

4. Миногин А.В. Методика определения консистентного состояния в высоко распределенных системах с перестановкой, задержкой и потерей сообщений // Системы управления и информационные технологии Воронеж: Научная книга, 2009. - №2.1 (36) - С. 162-166.

5. David Е. Lowell, Subhachandra Chandra, Peter M. Chen. Exploring failure transparency and the limits of gencric recovery // Proceedings of the 4th USENIX OSDI Symposium 2000 - P. 289-304.

6. M Wiesmann, F. Pedone, A. Schiper, B. Kemme, G. Alonso. Understanding Replication in Databases and Distributed Systems. // 20th IEEE International Conference on Distributed Computing Systems (ICDCS'00) 2000. - P. 264-274.

7. Г. Tannenbaum and M. Litzkow. The Condor Distributed Processing System. // Dr. Dobb's Journal 1995 - P. 40-48.

8. Yi-Min Wang, Yennun Huang, Kiem-Phong Vo, Pi-Yu Chung, and Chandra Kintala. Checkpointing and Its Applications. // Proceedings of the 1995 International Symposium on Fault-Tolerant Computing (FTCS). 1995. - P. 2231.

9. D. E. Lowell and P. M. Chen. Discount Checking: Transparent, Low-Overheadi

10. Recovery for General Applications. University of Michigan CSETR-410-99, 1998.

11. Fred B. Schneider. Byzantine Generals in Action: Implementing Fail-Stop Processors. // ACM Transactions on Computer Systems. 1984 - N 2. - P. 145154.

12. Schlichting R.D., Schneider F.B. Failstop processors: An approach to designing fault-tolerant computing systems. // ACM Transactions on Computing Systems. -1983 -V.1,N3.-P. 222-238.

13. Cao J. Efficient synchronous checkpointing in distributed systems. // Proceedings of the 15th Australia Computer Science Conference. 1992 - P. 165-179.

14. Cao J., Wang K.C. Efficient synchronous checkpointing in distributed systems. // Technical Report 91/6. James Cook University of North Queensland, Department of Computer Science. - 1991.

15. G. Jiang. Infrastructure Web: Distributed monitoring and managing critical infrastructures. // Proc. of. SPIE. 2001 - V.4232.

16. И. Б. Бурдонов, А. С. Косачев, В. H. Пономаренко, В. 3. Шнитман. Обзор подходов к верификации распределенных систем. // Технический отчёт М.: ИСП РАН, 2003.-52 с.

17. D. Brand, P. Zafiropulo. On Communicating Finite-State Machines // Journal of the Association for Computing Machinery. 1983 - V.30, N 2. - P. 323-342.3e.Gerard J. Holzmann. Design and Validation of Computer Protocols. Prentice Hall, 1990.-554 p.

18. F.B. Schneider. Replication Management using the State-Machine Approach. // Distributed Systems. 1993 - P. 169-197.

19. N. Vlassis. A Concise Introduction to Multiagent Systems and Distributed AI. -University of Amsterdam. 2003. 76 p.

20. Michael Wooldridge. An Introduction to MultiAgent Systems. John Wiley & Sons Ltd. 2002.

21. Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From «Intelligent Agents» to Open Systems Science. // IEEE Transactions on Systems, Man, and Cybernetics. 1991 - P. 1409-1418.

22. D. Milojicic. MASIF: The OMG mobile agent system interoperability facility. // Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag. 1998 -P. 50.

23. P. D. О'Brian, R. C. Nicol. FIPA—toward a standard for software agents. 11 ВТ Technol. J. 1998 - V.16, N 3.

24. F. Bellifemine, A. Poggi, G.Giovanni Rimassa. JADE—A FIPAcompliant agent framework. // Proc. PAAM, London, U.K. 1999 - P. 97-108.

25. Проект JavaFlow Электронный ресурс. — режим. дост.: http://commons.apache.org/sandbox/javaflow/

26. Geert Bevin. Continuations in Java HTML. (http://www.artima.com/leiava/articles/continuations.html').

27. Elnozahy E.N. Manetho. Fault tolerance in distributed systems using rollback-recovery and process replication: Ph.D. Thesis. Rice University, Department of Computer Science, 1993.

28. Goldberg A., Gopal A., Li K., Strom R., Bacon D. Transparent recovery of Mach applications. // Usenix Mach Workshop Proceedings 1990 - P. 169-184.

29. Bartlett J.F. A Non Stop Kernel. // Proceedings of the Eighth ACM Symposium on Operating Systems Principles 1981 - P. 22-29.

30. Johnson D.B., Zwaenepoel W. Senderbased message logging. // Digest of Papers FTCS-17, The Seventeenth Annual International Symposium on Fault-Tolerant Computing 1987-P. 14-19.

31. David E. Lowell. Theory and Practice of Failure Transparency: PhD thesis -University of Michigan, 1999.

32. David E. Lowell, Peter M. Chen. Free Transactions with Rio Vista. // Proceedings of the 1997 Symposium on Operating Systems Principles. 1997 - P. 143-146.