Реферат: Распределенные алгоритмы
7.1.1 Предположения, используемые в этой главе
Рассмотрим предположения, при которых задача выбора изучалась в этой главе.
(1) Система полностью асинхронна. Предполагается, что процессам недоступны общие часы, и что время передачи сообщения может быть произвольно долгим или коротким.
Оказывается, что предположение о синхронной передаче сообщений (т.е. когда отправление и получение сообщения считается единой передачей) незначительно влияет на результаты, полученные для задачи выбора. Читатель может сам убедиться, что алгоритмы, данные в этой главе, могут применяться в системах с синхронной передачей сообщений, и что полученные нижние границы также применимы в этом случае.
Предположение о существовании глобального времени, также как и предположение о том, что процессам доступно реальное время и что задержка сообщений ограничена, имеют важное влияние на решения задачи выбора.
(2) Каждый процесс идентифицируется уникальным именем, своим идентификатором, который известен процессу изначально. Для простоты предполагается, что идентификатор процесса p - просто p. Идентификаторы извлекаются из совершенно упорядоченного множества P, т.е. для идентификаторов определено отношение £. Количество бит, представляющих идентификатор, равно w.
Важность уникальных идентификаторов в задаче выбора состоит в том, что они могут использоваться не только для адресации сообщений, но и для нарушения симметрии между процессами. При разработке алгоритма выбора можно, например, потребовать, что процесс с наименьшим (или наоборот, с наибольшим) идентификатором должен победить. Тогда задача состоит в поиске наименьшего идентификатора с помощью децентрализованного алгоритма. В этом случае задачу выбора называют задачей поиска экстремума.
Хотя некоторые из алгоритмов, обсуждаемых в этой главе, изначально были изложены для нахождения наибольшего процесса, мы излагаем большинство алгоритмов для выбора наименьшего процесса. Во всех случаях алгоритм для выбора наибольшего процесса можно получить, изменив порядок сравнения идентификаторов.
(3) Некоторые результаты этой главы относятся к алгоритмам сравнения. Алгоритмы сравнения - это алгоритмы, которые используют сравнение как единственную операцию над идентификаторами. Как мы увидим, все алгоритмы, представленные в этой главе, являются алгоритмами сравнения. Всякий раз, когда дается оценка нижней границы, мы явно отмечаем, касается ли она алгоритмов сравнения.
Было показано (например, Бодлендером [Bodlaender, Bod91b] для случая кольцевых сетей), что в асинхронных сетях произвольные алгоритмы не достигают лучшей сложности, чем алгоритмы сравнения. Это не так в случае синхронных систем, как будет показано в Главе 11; в этих системах произвольные алгоритмы могут достигать лучшей сложности, чем алгоритмы сравнения.
(4) Каждое сообщение может содержать O(w) бит. Каждое сообщение может содержать не более постоянного числа идентификаторов процессов. Это предположение сделано для того, чтобы позволить справедливое сравнение сложности сообщений различных алгоритмов.
Уже было замечено, что идентификаторы процессов могут использоваться для нарушения симметрии между процессами. Можно разработать алгоритм выбора так, чтобы выбирался процесс с наименьшим идентификатором. Согласно результатам в Подразделе 6.1.5, наименьший идентификатор может быть вычислен за одну волну. Это означает, что выбор можно провести, выполняя волну, в которой вычисляется наименьший идентификатор, после чего процесс с этим идентификатором становится лидером. Т.к. алгоритм выбора должен быть децентрализованным, этот принцип может быть применен только к децентрализованным волновым алгоритмам (см. Таблицу 6.19).
Выбор с помощью древовидного алгоритма. Если топология сети - дерево или доступно остовное дерево сети, выбор можно провести с помощью древовидного алгоритма (Подраздел 6.2.2). В древовидном алгоритме требуется, чтобы хотя бы все листья были инициаторами алгоритма. Чтобы получить развитие алгоритма в случае, когда некоторые процессы также являются инициаторами, добавляется фаза wake-up. Процессы, которые хотят начать выбор, рассылают сообщение <wakeup> всем процессам. Логическая переменная ws используется, чтобы каждый процесс послал сообщения <wakeup> не более одного раза, а переменная wr используется для подсчета количества сообщений <wakeup>, полученных процессом. Когда процесс получит сообщение <wakeup> через каждый канал, он начинает выполнять Алгоритм 6.3, который расширен (как в Теореме 6.12) таким образом, чтобы вычислять наименьший идентификатор и чтобы каждый процесс принимал решение. Когда процесс принимает решение, он знает идентификатор лидера; если этот идентификатор совпадает с идентификатором процесса, он становится лидером, а если нет - проигравшим; см. Алгоритм 7.1.
var wsp : boolean init false ;
wrp : integer init 0 ;
recp[q] : boolean для всех q Î Neighp init false ;
vp : P init p ;
statep : (sleep, leader, lost) init sleep ;
begin if p - инициатор then
begin wsp := true ;
forall q Î Neighp do send <wakeup> to q
end ;
while wrp < # Neighp do
begin receive <wakeup> ; wrp := wrp + 1 ;
if not wsp then
begin wsp := true ;
forall q Î Neighp do send <wakeup> to q
end
end ;
(* Начало древовидного алгоритма *)
while # {q : Ørecp[q]} > 1 do
begin receive <tok,r> from q ; recp[q] := true ;
vp := min (vp,r)
end ;
send <tok,vp> to q0 with Ørecp[q0] ;
receive <tok,r> from q0 ;
vp := min (vp,r) ; (* decide с ответом vp *)
if vp = p then statep := leader else statep := lost ;
forall q Î Neighp, q ¹ q0 do send <tok,vp> to q
end
Алгоритм 7.1 Алгоритм выборов для деревьев.
Теорема 7.2 Алгоритм 7.1 решает задачу выбора на деревьях, используя O(N) сообщений и O(D) единиц времени.
Доказательство. Когда хотя бы один процесс инициирует выполнение алгоритма, все процессы посылают сообщения <wakeup> всем своим соседям, и каждый процесс начинает выполнение древовидного алгоритма после получения сообщения <wakeup> от каждого соседа. Все процессы завершают древовидный алгоритм с одним и тем же значением v, а именно, наименьшим идентификатором процесса. Единственный процесс с этим идентификатором закончит выполнение в состоянии лидер, а все остальные процессы - в состоянии проигравший.
Через каждый канал пересылается по два сообщения <wakeup> и по два сообщения <tok,r>, откуда сложность сообщений равна 4N-4. В течение D единиц времени после того, как первый процесс начал алгоритм, каждый процесс послал сообщения <wakeup>, следовательно, в течение D+1 единиц времени каждый процесс начал волну. Легко заметить, что первое решение принимается не позднее, чем через D единиц времени после начала волны, а последнее решение принимается не позднее D единиц времени после первого, откуда полное время равно 3D+1. Более тщательный анализ показывает, что алгоритм всегда завершается за 2D единиц времени, но доказательство этого оставлено читателю; см. Упражнение 7.2.
Если порядок сообщений в канале может быть изменен (т.е. канал - не FIFO), процесс может получить сообщение <tok,r> от соседа прежде чем он получил сообщение <wakeup> от этого соседа. В этом случае сообщение <tok,r> может быть временно сохранено или обработано как сообщения <tok,r>, прибывающие позднее.
Количество сообщений может быть уменьшено с помощью двух модификаций. Во-первых, можно устроить так, чтобы не-инициатор не посылал сообщение <wakeup> процессу, от которого он получил первое сообщение <wakeup>. Во-вторых, сообщение <wakeup>, посылаемое листом, может быть объединено с сообщением <tok,r>, посылаемым этим листом. С этими изменениями количество сообщений, требуемое алгоритмом, уменьшается до 3N-4+k, где k - количество нелистовых стартеров [Tel91b, с.139].
Выбор с помощью фазового алгоритма. Фазовый алгоритм можно использовать для выбора, позволив ему вычислять наименьший идентификатор за одну волну, как в Теореме 6.12.
Теорема 7.3 С помощью фазового алгоритма (Алгоритм 6.7) можно провести выбор в произвольных сетях, используя O(D*|E|) сообщений и O(D) единиц времени.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 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, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
