Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 23
Текст из файла (страница 23)
Канал, сохраняющий порядок передаваемых понему сообщений, называется очередью. Это означает, что если процесс p отправляет два сообщения m1 и m2 в адрес процесса q и при этом отправление80Гл. 2. Модельсообщения m1 происходит раньше чем отправление сообщения m 2 , то получение сообщения m1 также происходит раньше,чем получение сообщения m 2 .
Еслине оговорено противное, мы будем полагать, что рассматриваемые в этой книгеканалы не являются очередями.Очереди хорошо согласуются с определением 2.6; их можно легко представить, заменив совокупность сообщений M множеством очередей, по одной длякаждого канала связи. Отправление сообщения приводит к тому, что это сообщение помещается в конец очереди, а в результате события приема сообщениеизвлекается из начала очереди. Когда возникают очереди, появляется и новыйтип коммуникационных неисправностей, а именно нарушение очередности сообщений в канале; его можно промоделировать с помощью перехода, изменяющегопорядок расположения сообщений в очереди.Иногда случается так, что распределенный алгоритм извлекает определеннуювыгоду из свойства очередности событий в канале; примером тому может служитькоммуникационный протокол, приведенный в § 3.3.1.
Воспользовавшись тем, чтопри приеме сообщений соблюдается очередность, можно уменьшить объем информации, который должен передаваться в каждом сообщении. Однако во многихслучаях алгоритм должен быть устроен так, чтобы он функционировал правильно (и эффективно) даже тогда, когда изменяется порядок расположения событийв канале. В общем случае реализация свойства очередности может уменьшитьприсущий вычислению параллелизм, поскольку принимающий процесс долженобеспечить буферизацию сообщений перед их обработкой. По этой причине мыпредпочли не использовать в этой книге неявного предположения об очередностисообщений.Более слабое предположение было предложено в работе Ахуджи [5] ; выровненным каналом называется канал, в котором сохраняется очередность только тех сообщений, которые были особо отмечены при их отправлении.
Можно рассмотреть и более сильные допущения. Щипер и др. в работе [172] дали следующее определение передачи сообщений, сохраняющей причинноследственный порядок. Если в процессах p1 и p2 происходят события e1 и e2отправления сообщений m1 и m2 процессу q и при этом справедливо соотношение e1 ≺ e2 , то q получает событие m1 раньше, чем событие m2 . Иерархияразличных предположений о порядке доставки сообщений, включающая полную асинхронность, передачу с сохранением причинно-следственного порядка,доставку по очереди и синхронную коммуникацию, была исследована в работеЧаррон-Боста и др. [48] .3.
Пропускная способность каналов. Пропускной способностью канала называется количество сообщений, которые могут одновременно пребыватьв канале на этапе пересылки. Канал считается переполненным в тех конфигурациях, в которых число содержащихся в нем сообщений в точности равно егопропускной способности. Событие отправления допустимо только в тех случаях,когда канал не является переполненным.В определении 2.6 рассматривается модель, каналы которой имеют неограниченную пропускную способность и никогда не переполняются. В нашей книге2.4.
Дополнительные допущения. Сложность81мы всегда будем считать, что пропускная способность каналов является неограниченной.2.4.3. Допущения реального времениВажнейшее свойство рассматриваемых моделей — это, безусловно, их распределенность, т. е. абсолютная независимость событий, происходящих в разныхпроцессах, о чем свидетельствует теорема 2.19. Это свойство утрачивается, кактолько мы вводим модель в рамки реального времени и придаем процессам способность отсчитывать физическое время (встраиваем в процессы таймер). В самом деле, если истекает реальное время, то оно истекает во всех процессах,и течение времени отражается на часах каждого процесса.В нашу модель можно ввести часы реального времени, снабдив каждый процесс вещественной переменной (часами); течение реального времени моделируется посредством перехода, который продвигает вперед показания часов каждогопроцесса (см. § 3.3.2).
Наряду с наличием часов реального времени обычно предполагается, что время доставки сообщения (отрезок времени между осуществлением событий отправления и приема сообщения) ограничено. Этот срок доставкисообщения также может быть включен в общую модель системы переходов.В этой книге, за исключением особо оговоренных случаев, мы будем иметьдело с допущениями реального времени, т. е. мы рассматриваем вполне асинхронные системы и алгоритмы.
Допущения о времени будут использоваться в§ 3.3.2, в гл. 12, и в гл. 15.2.4.4. Осведомленность процессовМы будем использовать термин «осведемленность процессов» для обозначения той информации о распределенной системе, которая представлена в начальном состоянии процессов. В тех случаях, когда мы говорим, что алгоритм опирается на такую информацию, это означает, что соответствующие данные заранеезаложены в память процесса еще до того, как система начинает выполнение.Примером сведений такого рода может быть следующая информация.1. Топологическая информация. Информация о топологии включает сведения о числе процессов, о диаметре графа сети, о топологии сети.
Говорят, чтосеть наделена представлением об ориентации, если процессам известна согласованная ориентированная разметка ребер сети (см. гл. Б).2. Отличительные признаки процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждому процессу было заранее известно его собственное имя. Предполагается, чтов процессах имеется переменная, начальным значением которой является это имя(разные процессы имеют разные имена). Далее, можно уточнить, из какого множества выбираются имена процессов, упорядочены ли эти имена, являются лиэти имена натуральными числами.Если не оговорено противное, при изложении материала мы будем исходитьиз предположения о том, что процессам известны их собственные имена; в та-82Гл.
2. Модель2.4. Дополнительные допущения. Сложностьком случае говорят, что сеть является именованной. Случаи анонимных сетейбудут исследованы в гл. 9.3. Отличительные признаки соседей. Если процессы различаются по ихуникальным именам, то можно предполагать, что каждому процессу заранее известны имена его соседей.
Если не оговорено противное, то допущение о сведениях такого рода, которые называются сведениями о соседях, нами использоватьсяне будут. Имена процессов могут быть использованы в качестве адресов сообщений при отправлении сообщений по прямому адресу. Более сильное допущениепредполагает, что каждому процессу известны имена всех процессов системы.При более слабом допущении предполагается, что процессу известно о существовании соседей, но их имена ему неизвестны.
Прямой адресацией в этомслучае воспользоваться невозможно, и поэтому процессы вынуждены использовать для адресации локальные имена каналов; этот способ адресации называетсякосвенной адресацией; см. [176, с. 54] . Прямая и косвенная адресация проиллюстрированы на рис. 2.5. В случае прямой адресации имена процессов играютроль адресов, а при косвенной адресации процессы p, r и s используют различные имена (a, b и c соответственно), для того чтобы доставить сообщение одномуи тому же процессу q.p- «q»r(а) qp a @@@@ srb -(б)q@@@ Рис. 2.5. Прямая (а) и косвенная (б) адресацияcs2.4.5. Сложность распределенных алгоритмовНаиболее важным качеством распределенных алгоритмов является их корректность: алгоритм должен удовлетворять всем требованиям, которые налагаются на него той задачей, для решения которой предназначен этот алгоритм.
Чтобысравнивать друг с другом различные алгоритмы решения одной и той же задачи, можно оценить объем ресурсов, которые потребляются этими алгоритмами.Чем ниже уровень потребления, тем «лучше» алгоритм. Измерять потреблениересурсов можно по-разному.1. Сложность по числу обменов сообщениями. Это общее число сообщений, которые были отправлены по ходу выполнения алгоритма.832. Битовая сложность.
Обычно множество M содержит несколько разных типов сообщений, и поэтому, чтобы различать эти сообщения, каждое изних должно нести определенное количество информации. Если множество типов сообщений M, используемых алгоритмом, невелико, то для идентификацииэтих сообщений достаточно небольшого числа битов, а вот алгоритмам, в которых задействовано много разных типов сообщений, приходится использоватьбольшее число битов для обозначения каждого сообщения. Так как передача«длинных» сообщений требует больших затрат, нежели передача «коротких» сообщений, нужно оценивать также и суммарное количество битов, содержащихсяв сообщениях.В большинстве алгоритмов, которые описаны в этой книге, сообщения состоят из O(log N) битов, где N — общее число процессов системы, поэтому ихбитовая сложность отличается от сложности по числу сообщений на логарифмический множитель.
Чаще всего мы будем ограничиваться анализом сложностипо числу сообщений, а битовая сложность будет вычисляться только для такихалгоритмов, в которых используются очень длинные или очень короткие сообщения.3. Сложность по времени. Так как в нашей модели распределенных алгоритмов не задействовано понятие времени, неясно, каким образом нам определитьсложность распределенных алгоритмов по времени. В математической литературеимеется немало различных определений этого понятия (их сравнительный анализможно найти в § 6.6.4). В основу того определения, которым мы будем пользоваться в этой книге, положено идеализированное хронометрирование событийвычисления согласно следующим допущениям:а) обработка событий не занимает ни одной единицы времени;б) для передачи сообщения требуется не более одной единицы времени, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
