Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 24
Текст из файла (страница 24)
Этот срок доставкисообщения также может быть включен в общую модель системы переходов.В этой книге, за исключением особо оговоренных случаев, мы будем иметьдело с допущениями реального времени, т. е. мы рассматриваем вполне асинхронные системы и алгоритмы. Допущения о времени будут использоваться в§3.3.2, в гл. 12, и в гл. 15.2.4.4. Осведомленность процессовМы будем использовать термин «осведемленность процессов» для обозначения той информации о распределенной системе, которая представлена в начальном состоянии процессов.
В тех случаях, когда мы говорим, что алгоритм опирается на такую информацию, это означает, что соответствующие данные заранеезаложены в память процесса еще до того, как система начинает выполнение.Примером сведений такого рода может быть следующая информация.1. Топологическая информация. Информация о топологии включает сведения о числе процессов, о диаметре графа сети, о топологии сети. Говорят, чтосеть наделена представлением об ориентации, если процессам известна согласованная ориентированная разметка ребер сети (см.
гл. Б).2. Отличительные признаки процессов. Во многих алгоритмах требуется, чтобы процессы имели уникальные имена (идентификаторы), и чтобы каждому процессу было заранее известно его собственное имя. Предполагается, чтов процессах имеется переменная, начальным значением которой является это имя(разные процессы имеют разные имена). Далее, можно уточнить, из какого множества выбираются имена процессов, упорядочены ли эти имена, являются лиэти имена натуральными числами.Если не оговорено противное, при изложении материала мы будем исходитьиз предположения о том, что процессам известны их собственные имена; в та82Гл.
2. Модельком случае говорят, что сеть является именованной. Случаи анонимных сетейбудут исследованы в гл. 9.3.Отличительные признаки соседей. Если процессы различаются по ихуникальным именам, то можно предполагать, что каждому процессу заранее известны имена его соседей. Если не оговорено противное, то допущение о сведениях такого рода, которые называются сведениями о соседях, нами использоватьсяне будут. Имена процессов могут быть использованы в качестве адресов сообщений при отправлении сообщений по прямому адресу. Более сильное допущениепредполагает, что каждому процессу известны имена всех процессов системы.При более слабом допущении предполагается, что процессу известно о существовании соседей, но их имена ему неизвестны.
Прямой адресацией в этомслучае воспользоваться невозможно, и поэтому процессы вынуждены использовать для адресации локальные имена каналов; этот способ адресации называетсякосвенной адресацией; см. [176, с. 54]. Прямая и косвенная адресация проиллюстрированы на рис. 2.5.
В случае прямой адресации имена процессов играютроль адресов, а при косвенной адресации процессы р, г и s используют различные имена (а, b и с соответственно), для того чтобы доставить сообщение одномуи тому же процессу q.Рис. 2.5. Прямая (а) и косвенная (б) адресация2.4.5. Сложность распределенных алгоритмовНаиболее важным качеством распределенных алгоритмов является их корректность: алгоритм должен удовлетворять всем требованиям, которые налагаются на него той задачей, для решения которой предназначен этот алгоритм. Чтобысравнивать друг с другом различные алгоритмы решения одной и той же задачи, можно оценить объем ресурсов, которые потребляются этими алгоритмами.Чем ниже уровень потребления, тем «лучше» алгоритм.
Измерять потреблениересурсов можно по-разному.1.Сложность по числу обменов сообщениями. Это общее число сообщений, которые были отправлены по ходу выполнения алгоритма.2.4. Дополнительные допущения. Сложность832. Битовая сложность. Обычно множество Л4 содержит несколько разных типов сообщений, и поэтому, чтобы различать эти сообщения, каждое изних должно нести определенное количество информации. Если множество типов сообщений Л4, используемых алгоритмом, невелико, то для идентификацииэтих сообщений достаточно небольшого числа битов, а вот алгоритмам, в которых задействовано много разных типов сообщений, приходится использоватьбольшее число битов для обозначения каждого сообщения. Так как передача«длинных» сообщений требует больших затрат, нежели передача «коротких» сообщений, нужно оценивать также и суммарное количество битов, содержащихсяв сообщениях.В большинстве алгоритмов, которые описаны в этой книге, сообщения состоят из О (log N) битов, где N — общее число процессов системы, поэтому ихбитовая сложность отличается от сложности по числу сообщений на логарифмический множитель.
Чаще всего мы будем ограничиваться анализом сложностипо числу сообщений, а битовая сложность будет вычисляться только для такихалгоритмов, в которых используются очень длинные или очень короткие сообщения.3. Сложность по времени. Так как в нашей модели распределенных алгоритмов не задействовано понятие времени, неясно, каким образом нам определитьсложность распределенных алгоритмов по времени. В математической литературеимеется немало различных определений этого понятия (их сравнительный анализможно найти в §6.6.4). В основу того определения, которым мы будем пользоваться в этой книге, положено идеализированное хронометрирование событийвычисления согласно следующим допущениям:а) обработка событий не занимает ни одной единицы времени;б) для передачи сообщения требуется не более одной единицы времени, т. е.протяженность отрезка времени между событием отправления и событиемприема сообщения не превосходит одной единицы;Сложностью алгоритма по времени будет считаться время, которое требуетсядля проведения вычисления в рамках указанных выше допущений.
Следует обратить внимание, что эти допущения были выдвинуты исключительно для того,чтобы ввести определение сложности по времени для распределенных алгоритмов. Корректность асинхронных алгоритмов должна быть доказана независимоот этих допущений4. Сложность по объему памяти. Сложность алгоритма по объему памятиравна количеству единиц памяти, необходимой отдельному процессу для выполнения этого алгоритма. В нашем случае этот объем равен логарифму от числасостояний процесса.Так как функционирование распределенных алгоритмов является недетерминированным, не исключены случаи, когда допустимыми оказываются сразунесколько вычислений, имеющих различные меры сложности.
Поэтому мы будем проводить различие между сложностью в среднем и сложностью в наихудшем случае. Сложность алгоритма в наихудшем случае определяется наибольшейсложностью среди всех возможных вычислений алгоритма. Сложность алгоритмав среднем, как следует из названия, представляет собой среднюю сложность по84Гл. 2. Модельвсем возможным вычислениям, но, чтобы провести ее оценку, нужно определитьраспределение вероятностей по всем возможным вычислениям.2.5. Упражнения к главе 22.5.1Упражнение 2.1. Предложите определение модели распределенной системы, в которой возможен как синхронный, так и асинхронный обмен сообщениями.2.5.2Вниманию читателей предлагаются три упражнения, в которых речь идет о том,в чем состоит различие между инвариантом и всюду истинным предикатом, дизъюнктивными и конъюнктивными свойствами инвариантов и производных, а такжео том, как себя ведут инварианты при параллельной композиции программ.Упражнение 2.2.
Приведите пример такой системы переходов 5 и такогоутверждения Р, что Р всегда истинно в системе S, но при этом не является инвариантом этой системы.(Подсказка: пример системы с тремя конфигурациями приведен в работе [99].Можно ли отыскать пример системы с двумя конфигурациями?)Упражнение 2.3. Предположим, что Р\ и Р2 — это инварианты системы S.Докажите, что (Pi V Р 2 ) и (Pi A Р 2 ) также являются инвариантами.Предположим, что Р\ и Р 2 — это (J-производные системы S.
Докажите, что(Pi V Р 2 ) и (Pi A Р 2 ) также являются (J-производными системы S.Для систем переходов с одним и тем же множеством конфигураций и одинаковыми начальными конфигурациями можно определить композицию их отношенийпереходов. Так, например, параллельной композицией систем Si = (С, —*i, Т)и S 2 = (С, —>2 , X) называется такая система S = (С, — X), у которой —*•==HiU-> 2 ) .Упражнение 2.4. Пусть S — параллельная композиция систем Si и S 2 .Докажите, что всякий инвариант Р систем Si и S 2 также является инвариантом системы S.Докажите, что всякая Q-производная Р систем Si и S 2 также является Qпроизводной системы S.Приведите пример утверждения Р, которое является всегда истинным в обеихсистемах Si и S 2 , но не является таковым в системе S.В следующем упражнении речь идет о фундированных множествах. Множество может быть фундированным даже в том случае, если для некоторого элемента в множестве содержится бесконечно много элементов, меньших этого элемента.
Лексикографический порядок для векторов а = (а\, а2, ■■■, ап) и b == {Ь\, Ь2, . .. , Ьп) определяется следующим соотношением:а<фа\ < b\V( а\ = Ь\А(а2,ап) < i(b2,Ьп) ).2.5. Упражнения к главе 285Упражнение 2.5. Докажите, что в множестве (N", </), где п ^ 2, имеетсятакой элемент, который превосходит бесконечно много элементов этого множества.Докажите, что множество (N™, ^/) является фундированным.2.5.3Упражнение 2.6.
Определите, каковы будут показания логических часовЛампорта для всех событий выполнения, представленного на рис. 2.1.Определите, каковы будет показания часов Маттерна для этих событий.Выделите некоторые пары параллельных событий и проверьте, будут ли упорядочены показания часов для этих событий.Упражнение 2.7. Предложите распределенный алгоритм (подобный алгоритму 2.3), который вычисляет для каждого события показания векторных часовМаттерна.Упражнение 2.8. Можно ли доказать теорему 2.21 путем последовательногоприменения теоремы 2.19 к событиям выполнения Е?Упражнение 2.9.
Докажите теорему 2.24.Упражнение 2.10. Подберите подходящее определение для причинно-следственного порядка переходов системы с синхронным обменом сообщениями. Предложите определение часов для систем такого рода и постройте распределенныеалгоритмы для вычисления показаний этих часов.ГЛАВА3КОММУНИКАЦИОННЫЕ ПРОТОКОЛЫВ этой главе мы рассмотрим два протокола, которые используются для обеспечения надежного обмена данными между двумя вычислительными станциями.В идеальном случае обмен данными можно было бы осуществлять просто путемотправления и приема сообщений. Но, к сожалению, мы не можем игнорироватьвозможность возникновения ошибок при передаче данных; передача сообщенийдолжна проводиться в реальной физической среде, и вследствие этого может происходить потеря или дублирование передаваемых сообщений, изменение порядкаих следования, появление фиктивных сообщений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
