Ðåôåðàò: Ðàñïðåäåëåííûå àëãîðèòìû
Ðåôåðàò: Ðàñïðåäåëåííûå àëãîðèòìû
Ïðîëîã 6
1 Ââåäåíèå: ðàñïðåäåëåííûå ñèñòåìû 7
1.1 ×òî òàêîå ðàñïðåäåëåííàÿ ñèñòåìà? 7
1.1.1 Ìîòèâàöèÿ 8
1.1.2 Êîìïüþòåðíûå ñåòè 10
1.1.3 Ãëîáàëüíûå ñåòè 11
1.1.4 Ëîêàëüíûå ñåòè 13
1.1.5 Ìíîãîïðîöåññîðíûå êîìïüþòåðû 16
1.1.6 Âçàèìîäåéñòâóþùèå ïðîöåññû 19
1.2 Àðõèòåêòóðà è ßçûêè 22
1.2.1 Àðõèòåêòóðà 22
1.2.2 Ññûëî÷íàÿ Ìîäåëü OSI 24
1.2.3 OSI Ìîäåëü â ëîêàëüíûõ ñåòÿõ: IEEE Ñòàíäàðòû 26
1.2.4 Ïîääåðæêà ßçûêà 27
1.3 Ðàñïðåäåëåííûå Àëãîðèòìû 29
1.3.1 Ðàñïðåäåëåííûé ïðîòèâ Öåíòðàëèçîâàííûõ Àëãîðèòìîâ 30
1.3.2 Ïðèìåð: Ñâÿçü ñ îäèíî÷íûì ñîîáùåíèåì 32
1.3.3 Îáëàñòü èññëåäîâàíèÿ 37
1.3.4 Èåðàðõè÷åñêàÿ ñòðóêòóðà êíèãè 37
2 Ìîäåëü 40
2.1 Ñèñòåìû ïåðåõîäà è àëãîðèòìû 41
2.1.1 Ñèñòåìû ïåðåõîäîâ 42
2.1.2 Ñèñòåìû ñ àñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé 43
2.1.3 Ñèñòåìû ñ ñèíõðîííîé ïåðåäà÷åé ñîîáùåíèé 45
2.1.4 Ñïðàâåäëèâîñòü 47
2.2 Äîêàçàòåëüñòâî ñâîéñòâ ñèñòåì ïåðåõîäà 47
2.2.1 Ñâîéñòâà áåçîïàñíîñòè 48
2.2.2 Ñâîéñòâà æèâîñòè 50
2.3 Êàóçàëüíûé ïîðÿäîê ñîáûòèé è ëîãè÷åñêèå ÷àñû 51
2.3.1 Íåçàâèñèìîñòü è çàâèñèìîñòü ñîáûòèé 52
2.3.2 Ýêâèâàëåíòíîñòü èñïîëíåíèé: âû÷èñëåíèÿ 54
2.3.3 Ëîãè÷åñêèå ÷àñû 57
2.4 Äîïîëíèòåëüíûå äîïóùåíèÿ, ñëîæíîñòü 60
2.4.2 Ñâîéñòâà êàíàëîâ 62
2.4.3 Äîïóùåíèÿ ðåàëüíîãî âðåìåíè 64
2.4.4 Çíàíèÿ ïðîöåññîâ 64
2.4.5 Ñëîæíîñòü ðàñïðåäåëåííûõ àëãîðèòìîâ 66
3 Ïðîòîêîëû Ñâÿçè 66
3.1 Ñáàëàíñèðîâàííûé ïðîòîêîë ñêîëüçÿùåãî îêíà 68
3.1.1 Ïðåäñòàâëåíèå ïðîòîêîëà 68
3.1.2 Äîêàçàòåëüñòâî ïðàâèëüíîñòè ïðîòîêîëà 71
3.1.3 Îáñóæäåíèå ïðîòîêîëà 73
3.2 Ïðîòîêîë, îñíîâàííûé íà òàéìåðå 75
3.2.1 Ïðåäñòàâëåíèå Ïðîòîêîëà 78
3.2.2 Äîêàçàòåëüñòâî êîððåêòíîñòè ïðîòîêîëà 81
3.2.3 Îáñóæäåíèå ïðîòîêîëà 85
Óïðàæíåíèÿ ê ãëàâå 3 88
Ðàçäåë 3.1 88
Ðàçäåë 3.2 89
4 Àëãîðèòìû ìàðøðóòèçàöèè 89
4.1 Àäðåñàò-îñíîâàííàÿ ìàðøðóòèçàöèÿ 91
4.2 Ïðîáëåìà êðîò÷àéøèõ ïóòåé âñåõ ïàð 95
4.2.1 Àëãîðèòì Ôëîéäà-Óîøàëà 95
4.2.2 Àëãîðèòì êðîò÷àéøåãî ïóòè.(Toueg) 98
4.2.3 Îáñóæäåíèå è Äîïîëíèòåëüíûå Àëãîðèòìû 102
4.3 Àëãîðèòì Netchange 106
4.3.1 Îïèñàíèå àëãîðèòìà 107
4.3.2 Êîððåêòíîñòü àëãîðèòìà Netchange 112
4.3.3 Îáñóæäåíèå àëãîðèòìà 113
4.4 Ìàðøðóòèçàöèÿ ñ Êîìïàêòíûìè Òàáëèöàìè ìàðøðóòèçàöèè 114
4.4.1 Ñõåìà ðàçìåòêè äåðåâüåâ 115
4.4.2 Èíòåðâàëüíàÿ ìàðøðóòèçàöèÿ 118
4.4.3 Ïðåôèêñíàÿ ìàðøðóòèçàöèÿ 125
4.5 Èåðàðõè÷åñêàÿ ìàðøðóòèçàöèÿ 127
4.5.1 Óìåíüøåíèå êîëè÷åñòâà ðåøåíèé ìàðøðóòèçàöèè 128
Óïðàæíåíèÿ ê ×àñòè 4 130
Ðàçäåë 4.1 130
Ðàçäåë 4.2 131
Ðàçäåë 4.3 131
Ðàçäåë 4.4 131
Ðàçäåë 4.5 132
5 Áåñòóïèêîâàÿ êîììóòàöèÿ ïàêåòîâ 132
5.1 Ââåäåíèå 133
5.2 Ñòðóêòóðèðîâàííûå ðåøåíèÿ 134
5.2.1 Áóôåðíûå Ãðàôû 135
5.2.2 Îðèåíòàöèè G 138
5.3 Íåñòðóêòóðèðîâàííûå ðåøåíèÿ 141
5.3.1 Êîíòðîëëåðû ñ ïðÿìûì è îáðàòíûì ñ÷åòîì 141
5.3.2 Êîíòðîëëåðû ñ îïåðåæàþùèì è îòñòàþùèì ñîñòîÿíèåì 142
5.4 Äàëüíåéøèå ïðîáëåìû 144
5.4.1 Òîïîëîãè÷åñêèå èçìåíåíèÿ 145
5.4.2 Äðóãèå âèäû òóïèêîâ 146
5.4.3 Ëàéôëîê (livelock) 147
Óïðàæíåíèÿ ê Ãëàâå 5 149
Ðàçäåë 5.1 149
Ðàçäåë 5.2 149
Ðàçäåë 5.3 149
6 Âîëíîâûå àëãîðèòìû è àëãîðèòìû îáõîäà 149
6.1 Îïðåäåëåíèå è èñïîëüçîâàíèå âîëíîâûõ àëãîðèòìîâ 150
6.1.1 Îïðåäåëåíèå âîëíîâûõ àëãîðèòìîâ 151
6.1.2 Ýëåìåíòàðíûå ðåçóëüòàòû î âîëíîâûõ àëãîðèòìàõ 153
6.1.3 Ðàñïðîñòðàíåíèå èíôîðìàöèè ñ îáðàòíîé ñâÿçüþ 155
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
Ñòðàíèöû: 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
