6.1.4 Ñèíõðîíèçàöèÿ 156
6.1.5 Âû÷èñëåíèå ôóíêöèé èíôèìóìà 156
6.2 Âîëíîâûå àëãîðèòìû 158
6.2.1 Êîëüöåâîé àëãîðèòì 158
6.2.2 Äðåâîâèäíûé àëãîðèòì 159
6.2.3 Ýõî-àëãîðèòì 161
6.2.4 Àëãîðèòì îïðîñà 163
6.2.5 Ôàçîâûé àëãîðèòì 164
6.2.6 Àëãîðèòì Ôèííà 167
6.3 Àëãîðèòìû îáõîäà 169
6.3.1 Îáõîä êëèê 170
6.3.2 Îáõîä òîðîâ 171
6.3.3 Îáõîä ãèïåðêóáîâ 172
6.3.4 Îáõîä ñâÿçíûõ ñåòåé 173
6.4 Âðåìåííàÿ ñëîæíîñòü: ïîèñê â ãëóáèíó 175
6.4.1 Ðàñïðåäåëåííûé ïîèñê â ãëóáèíó 176
6.4.2 Àëãîðèòìû ïîèñêà â ãëóáèíó çà ëèíåéíîå âðåìÿ 177
6.4.3 Ïîèñê â ãëóáèíó ñî çíàíèåì ñîñåäåé 182
6.5 Îñòàëüíûå âîïðîñû 182
6.5.1 Îáçîð âîëíîâûõ àëãîðèòìîâ 182
6.5.2 Âû÷èñëåíèå ñóìì 184
6.5.3 Àëüòåðíàòèâíûå îïðåäåëåíèÿ âðåìåííîé ñëîæíîñòè 186
Óïðàæíåíèÿ ê Ãëàâå 6 188
Ðàçäåë 6.1 188
Ðàçäåë 6.2 189
Ðàçäåë 6.3 190
Ðàçäåë 6.4 190
Ðàçäåë 6.5 190
7 Àëãîðèòìû âûáîðà 190
7.1 Ââåäåíèå 191
7.1.1 Ïðåäïîëîæåíèÿ, èñïîëüçóåìûå â ýòîé ãëàâå 192
7.1.2 Âûáîð è âîëíû 193
7.2 Êîëüöåâûå ñåòè 196
7.2.1 Àëãîðèòìû ËåËàííà è ×àíãà-Ðîáåðòñà 196
7.2.2 Àëãîðèòì Petersen / Dolev-Klawe-Rodeh 200
7.2.3 Âûâîä íèæíåé ãðàíèöû 203
7.3 Ïðîèçâîëüíûå Ñåòè 207
7.3.1 Âûðîæäåíèå è Áûñòðûé Àëãîðèòì 208
7.3.2 Àëãîðèòì Gallager-Humblet-Spira 210
7.3.3 Ãëîáàëüíîå Îïèñàíèå GHS Àëãîðèòìà. 212
7.3.4 Äåòàëüíîå îïèñàíèÿ GHS àëãîðèòìà 215
7.3.5 Îáñóæäåíèÿ è Âàðèàíòû GHS Àëãîðèòìà 219
7.4 Àëãîðèòì Korach-Kutten-Moran 220
7.4.1 Ìîäóëüíîå Ñòðîèòåëüñòâî 221
7.4.2 Ïðèìåíåíèÿ Àëãîðèòìà KKM 225
Óïðàæíåíèÿ ê Ãëàâå 7 225
Ðàçäåë 7.1 225
Ðàçäåë 7.2 226
Ðàçäåë 7.3 226
Ðàçäåë 7.4 226
8 Îáíàðóæåíèå çàâåðøåíèÿ 227
8.1 Ïðåäâàðèòåëüíûå çàìå÷àíèÿ 228
8.1.1 Îïðåäåëåíèÿ 228
8.1.2 Äâå íèæíèõ ãðàíèöû 231
8.1.3 Çàâåðøåíèå Ïðîöåññîâ 233
8.2.2 Àëãîðèòì Shavit-Francez 237
8.3 Ðåøåíèÿ, îñíîâàííûå íà âîëíàõ 241
8.3.1 Àëãîðèòì Dijkstra-Feijen-Van Gasteren 242
8.3.2 Ïîäñ÷åò Îñíîâíûõ Ñîîáùåíèé: Àëãîðèòì Ñàôðà 245
8.3.3 Èñïîëüçîâàíèå Ïîäòâåðæäåíèé 249
8.3.4 Îáíàðóæåíèå çàâåðøåíèÿ ñ ïîìîùüþ âîëí 252
8.4 Äðóãèå Ðåøåíèÿ 254
8.4.1 Àëãîðèòì âîññòàíîâëåíèÿ êðåäèòà 254
8.4.2 Ðåøåíèÿ, èñïîëüçóþùèå âðåìåííûå ïîìåòêè 256
Óïðàæíåíèÿ ê Ãëàâå 8 259
Ðàçäåë 8.1 259
Ðàçäåë 8.2 259
Ðàçäåë 8.3 259
Ðàçäåë 8.4 260
13 Îòêàçîóñòîé÷èâîñòü â Àñèíõðîííûõ Ñèñòåìàõ 260
13.1 Íåâîçìîæíîñòü ñîãëàñèÿ 260
13.1.1 Îáîçíà÷åíèÿ, Îïðåäåëåíèÿ, Ýëåìåíòàðíûå Ðåçóëüòàòû 260
13.1.2 Äîêàçàòåëüñòâî íåâîçìîæíîñòè 262
13.1.3 Îáñóæäåíèå 264
13.2 Èçíà÷àëüíî-ìåðòâûå Ïðîöåññû 265
13.3 Äåòåðìèíèðîâàííî Äîñòèæèìûå Ñëó÷àè 268
13.3.1 Ðàçðåøèìàÿ Ïðîáëåìà: Ïåðåèìåíîâàíèå 269
13.3.2 Ðàñøèðåíèå Ðåçóëüòàòîâ Íåâîçìîæíîñòè 273
13.4 Âåðîÿòíîñòíûå Àëãîðèòìû Ñîãëàñèÿ 275
13.4.1 Àâàðèéíî-óñòîé÷èâûå Ïðîòîêîëû Ñîãëàñèÿ 276
13.4.2 Âèçàíòèéñêî-óñòîé÷èâûå Ïðîòîêîëû Ñîãëàñèÿ 280
13.5 Ñëàáîå Çàâåðøåíèå 285
Óïðàæíåíèÿ ê Ãëàâå 13 289
Ðàçäåë 13.1 289
Ðàçäåë 13.2 289
Ðàçäåë 13.3 289
Ðàçäåë 13.4 290
Ðàçäåë 13.5 291
14 Îòêàçîóñòîé÷èâîñòü â Ñèíõðîííûõ Ñèñòåìàõ 291
14.1 Ñèíõðîííûå Ïðîòîêîëû Ðåøåíèÿ 292
14.1.1 Ãðàíèöà Ñïîñîáíîñòè âîññòàíîâëåíèÿ 293
Ñòðàíèöû: 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
