Итеративный метод решения сетевых моделей

 

Является ли ситуация, представленная на рис. 4.5, оптимальной или устойчивой? Одним из способов анализа и решения подобных моделей является итеративный метод последовательных улучшений: последовательный выбор наилучших ответов каждым из игроков на текущую ситуацию. Алгоритм завершается устойчивой ситуацией, когда ни один из игроков не может уменьшить собственную задержку на s -t пути.

Рассмотрим более подробно следующий пример анализа сетевой игровой модели с двумя игроками (рис 4.6, а).

 

а)                                                          б)

 

Рис. 4.6. Итеративный метод последовательных улучшений. Начальная ситуация (а) и результат первого шага алгоритма (б)

 

В начальной ситуации на рис. 4.6, а задержка первого игрока составляет , а второго . На первом шаге алгоритма первый игрок изменяет свой путь  и уменьшает задержку до , а задержка второго игрока остается без изменений: . Результат представлен на рис. 4.6, б. На втором шаге алгоритма второй игрок изменяет свой путь  (рис.4.7, а) и получает задержку , тем самым увеличивая .

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

Ситуация на рис. 4.7, б является равновесием по Нэшу, так как ни один из игроков не может увеличить выигрыш (уменьшить задержку) путем выбора другой стратегии (другого s - t пути) при неизменной стратегии соперника.

 

а)                                                          б)

 

Рис. 4.7. Итеративный метод последовательных улучшений. Результаты второго (а) и третьего (б) шагов алгоритма

 

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

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Каково назначение систем и служб управления доступом к ресурсам в распределенных вычислениях?

2. Каковы основные компоненты систем пакетной обработки заданий?

3. Что такое пакет заданий?

4. Каковы основные функции систем управления ресурсами?

5. Что собой представляют специальные атрибуты конфигурирования очередей заданий?

6. Что собой представляет ресурсный запрос задания?

7. Каково назначение механизма контрольных точек?

8. Что такое архитектура OGSA (Open Grid Services Architecture)?

9. Каковы основные особенности планирования вычислений в грид на уровне приложений и потоков заданий?

10. Что такое модель задания в масштабируемой модели планирования?

11. Приведите необходимое условие разрешение конфликта параллельных задач.

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

13. Что такое модель выбора в масштабируемой модели планирования?

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

15. Что такое стратегия планирования?

16. Что такое условно оптимальная стратегия планирования?

17. Что собой представляет собой параллельная схема формирования стратегии для модели задания?

18. Что собой представляет собой Парето-оптимальная стратегия планирования?

19. Что собой представляет обобщенная схема формирования стратегии для модели задания?

20. В чем состоят особенности вычислительных сред с неотчуждаемыми ресурсами?

21. Поясните понятия слота, набора и комбинации слотов для планирования пакета заданий.

22. Что такое оптимальная и эффективная комбинации слотов?

23. Что такое функция уровня ресурсных затрат?

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

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

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

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

28. Поясните общую схему алгоритма отбора подходящих слотов с ранним временем старта «окна».

29. Что такое состояние системы в задаче планирования пакета независимых заданий?

30. Как оценивается эффективность той или иной комбинации слотов с помощью скалярной функции полезности?

31. Дайте определение понятию «игра». Какие существуют классификации игр?

32. Что такое равновесие по Нэшу? Насколько обоснован выбор равновесной ситуации в качестве решения игровой модели?

33. Что такое равновесие дрожащей руки? Приведите пример.

34. Какова процедура проведения аукциона второй цены? Приведите его основные свойства.

35. В чем состоят стратегии участников аукциона второй цены и как оценивается их эффективность?

36. В чем состоит парадокс Браеса? Какие Вы видите пути разрешения ситуации?

37. Каким образом осуществляется поиск решения в сетевой игровой модели? Всегда ли оно достижимо?

СПИСОК ЛИТЕРАТУРЫ

1. Конюховский, П.В., Малова, А.С. Теория игр. - М.: Юрайт, 2015. – 252 с.

2. Таненбаум, Э., ванн Стеен, М. Распределенные системы. Принципы и парадигмы. — СПб.: Питер, 2003. – 877 с.

3. Таненбаум, Э. Архитектура компьютера. — СПб.: Питер, 2002. – 704 с.

4. Топорков, В.В. Модели распределенных вычислений. – М.: ФИЗМАТЛИТ, 2004. – 320 с.

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ................................................................................................................ 3

1. УПРАВЛЕНИЕ РЕСУРСАМИ В РАСПРЕДЕЛЕННЫХ СРЕДАХ........... 6

1.1. Системы и службы управления доступом к ресурсам.................... 6

1.2. Планирование вычислений в грид...................................................... 11

2. СОГЛАСОВАННОЕ ВЫДЕЛЕНИЕ РЕСУРСОВ...................................... 15

2.1. Масштабируемая модель планирования.......................................... 15

2.2. Формирование планов по частному критерию............................... 19

2.3. Пример формирования планов............................................................. 23

2.4. Формирование стратегии вычислений.............................................. 26

2.5. Примеры формирования стратегии.................................................... 29

2.6. Планы для разных моделей задания.................................................. 31

2.7. Пример формирования планов для разных моделей задания..... 33

3. ПАКЕТНАЯ ОБРАБОТКА ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ 34

3.1. Особенности вычислительных сред с неотчуждаемыми ресурсами           34

3.2. Постановка задачи выбора оптимальной комбинации слотов.. 36

3.3. Решение задачи и примеры выбора оптимальной комбинации слотов      39

3.3.1. Схема выбора.................................................................................. 39

3.3.2. Отбор подходящих слотов.......................................................... 41

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

3.3.4. Минимизация суммарного времени завершения пакета заданий при ограничении на бюджет виртуальной организации................................................................................................................. 47

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

3.3.6. Минимизация простоя ресурсов при ограничении на время их использования 48

3.4. Задача выбора эффективной комбинации слотов.......................... 49

3.4.1. Постановка задачи........................................................................ 49

3.4.2. Схема выбора эффективной комбинации слотов.................. 50

3.4.3. Формирование -оптимальной стратегии планирования при заданных ограничениях          53

3.5. Выводы....................................................................................................... 56

4. МНОГОАГЕНТНОЕ ВЗАИМОДЕЙСТВИЕ И ЭЛЕМЕНТЫ ТЕОРИИ ИГР        57

4.1. Введение и основные понятия теории игр........................................ 57

4.1.1. Введение.......................................................................................... 57

4.1.2. Основные определения теории игр.......................................... 57

4.1.3. Формальное представление игровых моделей..................... 59

4.1.4. Биматричные игры........................................................................ 60

4.2. Многоагентное взаимодействие и равновесные ситуации.......... 61

4.2.1. Равновесие по Нэшу..................................................................... 61

4.2.2. Равновесие дрожащей руки........................................................ 63

4.3. Аукционы и справедливое разделение ресурсов............................ 65

4.3.1. Основные определения и классификация аукционов......... 65

4.3.2. Аукцион второй цены................................................................... 67

4.4. Сетевые модели и совместное использование ресурсов............ 70

4.4.1. Сетевые игровые модели и парадокс Браеса........................ 70

4.4.2. Формальное определение сетевой игровой модели............ 73

4.4.3. Итеративный метод решения сетевых моделей.................... 75

КОНТРОЛЬНЫЕ ВОПРОСЫ.............................................................................. 77

СПИСОК ЛИТЕРАТУРЫ...................................................................................... 78