Быстрый поиск

Реферат: Распределенные алгоритмы

Сценарий 2

Рисунок 14.5 Сценарии для детерминированного протокола.

Чтобы показать нижнюю границу для точности, пусть дан детерминированный протокол; в этом протоколе p и s обмениваются некоторыми сообщениями, после которых p корректирует свои часы. Рассматриваются два сценария для протокола, как изображено на Рисунке 14.5. В первом сценарии, часы равны до выполнения, все сообщения из s в p доставляются после , и все сообщения из p в s доставляются после . Если корректировка в этом сценарии - , то часы p в точности на опережают после синхронизации.

Во втором сценарии до выполнения отстает от на , все сообщения из p в s доставляются после , и все сообщения из s в p доставляются после . Назвав корректировку в этом сценарии , мы видим, что часы p после синхронизации отстают от в точности на .

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

Этот минимум равняется (и случается при ). o

Если два процесса p и q синхронизируют свои часы с сервером с этой точностью, достигается глобальная -синхронизация, который достаточно для большинства прикладных программ.

Лучшая точность достижима у вероятностного протокола синхронизации, предложенного Кристианом [Cri89]. Для этого протокола принимается, что задержка сообщения - стохастическая переменная, распределенная согласно (не обязательно известной) функции . Вероятность прибытия любого сообщения в течение x - F(x), и задержки различных сообщений независимы. Произвольная точность достижима только если нижняя граница плотна, то есть, для всех x>, F (x) > 0.

Протокол прост; p просит, чтобы s послал время, и s немедленно отвечает сообщением <time, T>. Процесс p измеряет время I между посылкой запроса и получения ответа; справедливо . Задержка сообщения ответа - по крайней мере и самое большее , и следовательно отличается самое большее на от . Таким образом, p может установить свои часы в , и достигает точности . Если желательная точность - , p посылает новый запрос если , в противном случае завершается.

Лемма 14.13 Вероятностный протокол синхронизации часов достигает точности с ожидаемым числом сообщений самое большее .

Доказательство. Вероятность того, что запрос p прибывает в течение - и такова же вероятность того, что ответ прибывает внутри в течение . Следовательно, вероятность того, что p получает ответ в течение - по крайней мере , что означает границу в на ожидаемое число испытаний до успешного обмена сообщениями. o

Временная сложность протокола уменьшается, если p посылает новый запрос когда никакого ответа не было получено после посылки запроса. Ожидаемое время тогда не зависит от ожидаемой или максимальной задержки, а именно , и протокол устойчив против потери сообщений. (Нужно использовать номера в порядке следования, чтобы отличить устаревшие ответы.)

14.3.2 Распределенная Синхронизация Часов

Этот раздел представляет t-Византийско-устойчивый (при t < N/3) распределенный алгоритм синхронизации часов Махани и Шнайдера [MS85]. Долев, Халперн и Стронг [DHS84] показали, что никакая синхронизация не возможна при , если не используется установление подлинности.

Ядро алгоритма синхронизации - протокол, который достигает неточного соглашения о средних значениях часов. Процессы корректируют свои часы и достигают высокой степени синхронизации. Из-за отклонения через некоторое время точность ухудшается, что влечет за собой новый раунд синхронизации после некоторого интервала. Предположим, что в реальное время часы -синхронизированы; тогда до времени часы -синхронизированы. Таким образом, если желательная точность - , и раунд синхронизации достигает точности , раунды повторяются каждые единиц времени. Так как время, допустим S, для выполнения раунда синхронизации обычно очень мало по сравнению с R, то оправдано упрощающее предположение о том, что в течение синхронизации отклонением можно пренебречь, то есть, часы являются идеальными.

Неточное соглашение: алгоритм с быстрой сходимостью. В проблеме неточного соглашения, используемой Махани и Шнайдером [MS85] для синхронизации часов, процесс p имеет действительное входное значение , где для корректных p и q . Выход процесса p - действительное значение , и точность выхода определяется как ; цель алгоритма состоит в том, чтобы достичь очень малого значения точности.