Распределенные алгоритмы (стр. 41 из 85)
Тупик пошагового продвижения может возникнуть, когда сеть содержит узлы с ограниченной внутренней памятью, которые могут отказываться выводить сообщения, пока некоторые другие сообщения не были сгенерированы. Например, терминал телетайпа должен вывести некоторые символы прежде, чем он сможет принимать следующие символы для отображения. Это нарушает наше предположение, что пакет в адресате всегда может быть выведен.
Тупика пошагового продвижения можно избежать, делая различие между продвигаемыми пакетами и пошаговыми ответами, такими, что пакет первого типа не может быть выведен, пока пакет второго типа не был сгенерирован. Для разных типов сообщений используются различные копии буферного графа.
Тупик перетрансляции может возникнуть в сетях, где большие сообщения для передачи разделяются на более мелкие пакеты, и ни один пакет не может быть удален из сети, пока все пакеты сообщения не достигли адресата. (Сравните с протоколом скользящего окна Раздела 3.1, где слова удаляются из outp только если были получены все слова с меньшим индексом.) Это нарушает наше предположение, что выведение пакета в адресате всегда возможно.
Тупиков перетрансляции можно избежать, используя отдельные группы буферов для пересылки пакета и перетрансляции.
Из определения тупиковых пакетов (Определение 5.2) следует, что под управлением беступикового контроллера для каждого пакета существует по крайней мере одно вычисление, в котором пакет выводится. Т.к. в общем случае возможно большое количество различных вычислений, то это из этого не следует, что каждый пакет в конечном счете доходит до адресата, даже в бесконечном вычислении, как иллюстрируется Рисунок 5.6. Предположим, что u посылает в v бесконечный поток пакетов, и каждый раз, как только буфер в w становится пустым, принимается следующий пакет из u. Узел s имеет пакет для t, который не заходит в тупик, потому что каждый раз, когда буфер в w становится пустым, имеется возможное продолжение вычисления, в котором пакет принимается вершиной w и посылается к t. Это возможно, но не обязательно, и пакет может остаться в s навсегда. Ситуация этого вида называется лайфлок.
Контроллер, обсуждаемый в этой главе, может быть расширен так, чтобы вообще избежать лайфлоков.
Определение 5.23 Дана сеть, контроллер con, и конфигурация g, пакет p заблокирован (лайфлок), если существует бесконечная последовательность передвижений, применимых в g, в результате которых p не выводится. Конфигурация g - конфигурация лайфлока, если она содержит заблокированные пакеты.
Рисунок 5.6 Пример лайфлока.
Контроллер свободен от лайфлока, если ни одна конфигурация лайфлока не достижима из конфигурации, в которой нет пакетов.
В оставшейся части этого подраздела будет доказана свобода контроллера буферных графов от лайфлока; в конце будут упомянуты расширения неструктурированных решений.
Контроллер буферного графа. Можно продемонстрировать, что контроллеры Раздела 5.2 лайфлок-свободны без каких-либо модификаций, если их передвижения в бесконечной последовательности удовлетворяют ряду справедливых предположений. Fl и F2 - сильные предположеня и F3 - слабое предположение.
Fl. Если порождение пакета p предпринимается непрерывно, то каждое бесконечное вычисление, в котором fb (p) свободен в бесконечно большом количестве конфигураций, содержит порождение p.
F2. Если в конфигурации g пакет p должен быть послан от u до w, то каждое бесконечное вычисление, начинающееся в g, в котором nb (p, b) является свободным в бесконечно большом количестве конфигураций, содержит пересылку p.
F3. Если пакет p находится в своем пункте назначения в конфигурации g, то каждое бесконечное вычисление, начинающееся в g, содержит выведение p.
Лемма 5.24 Если справедливые предположения F2 и F3 удовлетворяются в каждом бесконечном вычислении bgc, то каждый буфер свободен бесконечно часто.
Доказательство. Доказывать будем индукцией сверху вниз по классам буферов. Как в доказательстве Теоремы 5.7, пусть R - наибольший буферный класс. Напомним, что в конфигурациях, достижимых под управлением bgc, все пакеты располагаются в подходящих буферах.
Случай r = R: Буфер класса R не имеет исходящих ребер, и, следовательно, пакет из такого буфера достигает пункта назначения. Следовательно, по предположению F3, после каждой конфигурации, в которой такой буфер занят, будет конфигурация, в которой буфер свободен. Отсюда следует, что он пуст в бесконечно большом количестве конфигураций.
Случай r < R: Пусть g - конфигурация, в которой буфер b класса r < R занят пакетом p. Если p достиг своего пункта назначения, то позже будет конфигурация, в которой b будет пустым из F3. Иначе, p должен быть продвинут в буфер nb(p, b) класса r' > r. По индукции, в каждом бесконечном вычислении, начинающемся в g, этот буфер пуст бесконечно часто. Из этого следует (по F2), что p будет передан и, следовательно, будет конфигурация g, после которой b будет пуст.
Теорема 5.25 Если справедливые предположения F1, F2 и F3 удовлетворяются, то в каждом бесконечном вычислении каждый пакет, предлагаемый сети, будет выведен из своего пункта назначения.
Доказательство. По Лемме 5.24 все буферы пусты в бесконечно большом количестве конфигураций. Значит (по Fl) каждый паке, который продолжает предлагаться сети, будет сгенерирован. По F2 он будет продвигаться, пока не достигнет своего пункта назначения. ð
Легко предположить, что механизм недетерминированного выбора в распределенной системе гарантирует, что эти три предположения удовлетворяются. Альтернативно, предположения могут быть введены добавлением к контроллеру механизма, который гарантирует, что, когда буфер становится пустым, более старым пакетам позволяется входить с большими приоритетами.
Неструктурированные решения. Контроллеры Раздела 5.3 нужно модифицировать, чтобы они стали лайфлок-свободными. Это может быть показано моделированием бесконечного вычисления, в котором непрерывный поток пакетов заставляет контроллер запрещать пересылку некоторого пакета. Toueg [TouSOb] представляет такое вычисление (для FC) и представляет модификацию FS (подобную представленной здесь для контроллеров буферных графов), которая является лайфлок-свободной.
Упражнение 5.1 Покажите, что не существует беступикового контроллера, который использует только один буфер на вершину и позволяет каждой вершине посылать пакеты по крайней мере одной другой вершине.
Упражнение 5.2 Покажите, что dest не является беступиковым, если маршрутизация пакетов осуществляется как на Рисунке 5.2.
Упражнение 5.3 (Схема сколько-будет-переходов) Дайте буферный граф и функции fb и nb для контроллера, который использует буфер bu[i] для хранения пакетов, которым нужно сделать еще i переходов по направлению к своим пунктам назначения. Каков буферный класс bu [i] ? Нужно ли хранить счетчик переходов в каждом пакете?
Упражнение 5.4 Закончите доказательство того, что граф BGa (определенный в доказательстве Теоремы 5.13)- в самом деле буферный граф, т.е., для каждого пути P Î P существует гарантированный путь с образом P. Покажите, что, как утверждалось, fb и nb в самом деле описывают путь в BGa.
Проект 5.5 Докажите, что существует беступиковый контроллер, для коммутации пакетов в гиперкубе, который использует всего два буфера на вершину и позволяет маршрутизировать пакеты через минимальные пути. Можно ли получить набор используемых путей посредством алгоритма интервальной маршрутизации (Подраздел 4.4.2)? Можно ли использовать схему линейной интервальной разметки?
Упражнение 5.6 Докажите, что BC и BS - беступиковые контроллеры.
Упражнение 5.7 Докажите, каждое передвижение, позволяемое BC, также позволяется FC.
Часть 2 Фундаментальные алгоритмы
6 Волновые алгоритмы и алгоритмы обхода
При разработке распределенных алгоритмов для различных приложений часто в качестве подзадач возникает несколько общих проблем для сетей процессов. Эти элементарные задачи включают в себя широковещательную рассылку информации - broadcasting (например, посылка начального или заключительного сообщения), достижение глобальной синхронизации между процессами, запуск выполнения некоторого события в каждом процессе, или вычисление функции, входные данные которой распределены между процессами. Эти задачи всегда решаются путем пересылки сообщений согласно некоторой, зависящей от топологии схеме, которая гарантирует участие всех процессов. Эти задачи настолько фундаментальны, что можно дать решения более сложных задач, таких как выбор (Глава 7), обнаружение завершения (Глава 8), или взаимное исключение, в которых связь между процессами осуществляется только через эти схемы передачи сообщений.
Важность схем передачи сообщений, называемых далее волновыми алгоритмами, оправдывает их рассмотрение отдельно от конкретного прикладного алгоритма, в который они могут быть включены. В этой главе формально определяются волновые алгоритмы (Подраздел 6.1.1) и доказываются некоторые общие результаты о них (Подраздел 6.1.2). Замечание о том, что те же самые алгоритмы могут использоваться для всех основных задач, изложенных выше, т.е. широковещание, синхронизация и вычисление глобальных функций, будет формализовано (Подразделы 6.1.3-5). В Разделе 6.2 представлены некоторые широко используемые волновые алгоритмы. В Разделе 6.3 рассматриваются алгоритмы обхода; это волновые алгоритмы, в которых все события вычисления алгоритма совершенно упорядочены каузальным отношением. В Разделе 6.4 представлены несколько алгоритмов для распределенного поиска в глубину.