Операционные системы распределенных вычислительных систем


Асинхронная фиксация контрольных точек и восстановление. - часть 5


1 шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал-1 указал 1 (одна тысяча воинов), генерал-2 указал 2, генерал-3 указал трем остальным генералам соответственно x,y,z, а генерал-4 указал 4.

2-ой шаг. Каждый формирует свой вектор из имеющейся информации.

Получается:

vect1 (1,2,x,4)

vect2 (1,2,y,4)

vect3 (1,2,3,4)

vect4 (1,2,z,4)

3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опять произвольные значения).

Генералы получают следующие вектора:

g1

g2

g3

g4

(1,2,y,4)

(1,2,x,4)

(1,2,x,4)

(1,2,x,4)

(a,b,c,d)

(e,f,g,h)

(1,2,y,4)

(1,2,y,4)

(1,2,z.4)

(1,2,z.4)

(1,2,z.4)

(i,j,k.l)

 

4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается «неизвестен».

Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.

Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.

Lamport доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).

 Другие авторы доказали, что в распределенной системе с асинхронными процессорами и неограниченными коммуникационными задержками согласие невозможно достичь даже при одном неработающем процессоре (даже если он не подает признаков жизни).

Применение алгоритма - надежная синхронизация часов.

Алгоритм надежных неделимых широковещательных рассылок сообщений.

Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередей для запоминания поступающих сообщений. В качестве уникального идентификатора сообщения используется его начальный приоритет - логическое время отправления, значение которого на разных процессорах различно.




Начало  Назад  Вперед