Osztott algoritmusok

Szerző

Szerkesztő

Fordító

Lektor

Budapest

'Nancy Ann Lynch: Osztott algoritmusok ' összes példány

Kiadó:	Kiskapu Kft.
Kiadás helye:	Budapest
Kiadás éve:	2002
Kötés típusa:	Ragasztott papírkötés
Oldalszám:	781 oldal
Sorozatcím:
Kötetszám:
Nyelv:	Magyar
Méret:	23 cm x 19 cm
ISBN:	963-9301-03-5
Megjegyzés:	Néhány fekete-fehér ábrával illusztrálva. További fordítók a könyvben.

Értesítőt kérek a kiadóról

A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról

Fülszöveg

Az osztott algoritmusok kifejezés sokféle, széles körben alkalmazott párhuzamos algoritmust takar. Eredetileg olyan algoritmusokat jelentett, amelyeket nagy földrajzi területen szétosztott processzorokon való futásra terveztek. Ma olyan algoritmusokat is jelent, amelyek helyi hálózaton, sőt közös memóriájú többprocesszoros rendszereken futnak.
Az osztott algoritmusokat használják például a telekommunikáció, az osztott adatfeldolgozás, a tudományos számítások és a valósidejű folyamatirányítás területén.
A könyv négy fő része a szinkron hálózatok, aszinkron közös memóriájú rendszerek, aszinkron hálózatok és a részben szinkron rendszerek algoritmusait elemzi.
A vizsgált problémák közé tartozik a vezető folyamat választása, szélességi keresés, legrövidebb utak, minimális feszítőfa, maximális független halmaz, kölcsönös kizárás, erőforrás-hozzárendelés (étkező filozófusok és ivó filozófusok), adatok ellentmondásmentessége, megegyezés (k-megegyezés és közelítő megegyezés).
Az algoritmusok elemzése rendszerint két formában szerepel: egyrészt könnyen érthető vázlatos formában, másrészt automaták segítségével adott formális modellekre építve. Az elemzések eredménye a tárgyalt algoritmusok helyességének bizonyítása, futási idejük és üzenetszámuk jellemzése alsó és felső korlátokkal, az egyes problémák megoldhatóságának eldöntése, valamint a problémák megoldásához szükséges idő becslése.
A tárgyalás során a szerző figyelembe veszi a működő osztott rendszerekre jellemző nagyfokú bizonytalanságot és hibalehetőséget, például a következőket:
• ismeretlen számú processzor;
• ismeretlen hálózati topológia;
• különböző helyekre egymástól független bemeneti adatok töltődhetnek;
• egyszerre több program hajtódik végre, amelyek különböző időpontokban indultak el és különböző sebességgel hajtódnak végre;
• a processzorok nem determinisztikusak;
• bizonytalan az üzenetek szállítási ideje;
• ismeretlen az üzenetek sorrendje;
• a processzorok és adatátviteli vonalak meghibásodhatnak (ez lehet megállási vagy tetszőleges hibás viselkedést megengedő bizánci hiba).
A könyv szerzője Nancy Ann Lynch professzor, az MIT Osztott rendszerek elmélete kutatócsoport vezetője. A könyvben a szerző a nagy létszámú nemzetközi kutatócsoport több évtizedes munkájának eredményeit foglalja össze. Vissza

Tartalom

Előszó a magyar nyelvű kiadáshoz xiii
Előszó az angol nyelvű kiadáshoz (Lektor: Kiss Attila, fordító Iványi Antal) xiv
1. Bevezetés (Iványi Antal) 1
1.1. Miről szól a könyv? 1
1.2. Nézőpontunk 3
1.3. A 2-25. fejezetek tartalmának áttekintése 5
1.4. Megjegyzések a fejezethez 11
1.5. Jelölések 12
I. Szinkron hálózati algoritmusok (Csörnyei Zoltán) 13
2. Modellezés/I. Szinkron hálózati modell 14
2.1. Szinkron hálózati rendszerek 14
2.2. Hibák 16
2.3. Bemenetek és kimenetek 16
2.4. Végrehajtási sorozatok 16
2.5. Bizonyítási módszerek 17
2.6. Bonyolultsági mértékek 17
2.7. Véletlenítés 18
2.8. Megjegyzések a fejezethez 19
3. Vezető folyamat kiválasztása szinkron gyűrűben (Kovács Attila) 20
3.1. A feladat 20
3.2. Megoldhatatlansági eredmény azonos folyamatokra 21
3.3. Egy alapvető algoritmus 22
3.4. Egy O(n log n) kommunikációs bonyolultságú algoritmus 26
3.5. Nem összehasonlítás-alapú algoritmusok 29
3.5.1. Az Időszelet algoritmus 29
3.5.2. A VáltozóSebességek algoritmus 30
3.6. Alsó korlát az összehasonlítás-alapú algoritmusokra 33
3.7. Alsó korlát a nem összehasonlítás-alapú algoritmusok üzeneteinek számára 38
3.8. Megjegyzések a fejezethez 40
3.9. Gyakorlatok 41
4. Általános szinkron hálózatok algoritmusai (Gregorics Tibor) 43
4.1. Vezetőválasztás általános hálózatokban 43
4.1.1. A feladat 43
4.1.2. Egy egyszerű terjedő algoritmus 44
4.1.3. A kommunikációs bonyolultság csökkentése 46
4.2. Szélességi keresés 48
4.21. A feladat 49
4.2.2. Egy alapvető szélességi kereső algoritmus 49
4.2.3. Alkalmazások 51
4.3. Legrövidebb utak 52
4.4. Minimális feszítőfa 54
4.4.1. A feladat 54
4.4.2. Elméleti háttér 55
4.4.3. Algoritmus 57
4.5. Maximális független halmaz 61
4.5.1. A feladat 61
4.5.2. Véletlenített algoritmus 61
4.5.3. Elemzés 64
4.6. Megjegyzések a fejezethez 67
4.7. Gyakorlatok 67
5. Megegyezés osztott hálózatokban, vonalhibák esetében (Veszprémi Anna) 71
5.1. Az összehangolt támadási feladat - determinisztikus változat 71
5.2. Az összehangolt támadási feladat - véletlenített változat 76
5.2.1. Formális modellezés 76
5.2.2. Egy algoritmus 77
5.2.3. Alsó korlát a megegyezés hiányának valószínűségére 82
5.3. Megjegyzések a fejezethez 85
5.4. Gyakorlatok 85
6. Egyetértés osztott hálózatokban processzorhibák esetében 87
6.1. A feladat 88
6.2. Algoritmusok megállási hibáik kezelésére 90
6.2.1. Egy alapvető algoritmus 90
6.2.2. A kommunikációs bonyolultság csökkentése 93
6.2.3. Exponenciális információgyűjtő algoritmusok 96
6.2.4. Bizánci megegyezés hitelesítéssel 102
6.3. Algoritmusok bizánci hibák kezelésére 103
6.3.1. Egy példa 104
6.3.2. Az EIGY algoritmus a bizánci megegyezésre 106
6.3.3. A bináris bizánci megegyezésen alapuló általános bizánci megegyezés 109
6.3.4. A kommunikációs költség csökkentése 112
6.4. A bizánci megegyezés folyamatainak száma 115
6.5. Bizánci megegyezés általános gráfokban 121
6.6. Gyenge bizánci megegyezés 124
6.7. A menetek száma megállási hibák esetében 128
6.8. Megjegyzések a fejezethez 137
6.9. Gyakorlatok 138
7. További megegyezési problémák (Iványi Antal) 145
7.1. k-megegyezés 145
7.1.1. A feladat 145
7.1.2. Egy algoritmus 146
7.1.3. Alsó korlát 148
7.2. Közelítő megegyezés 159
7.3. A véglegesítési feladat 164
7.3.1. A feladat 164
7.3.2. Kétfázisú véglegesítés 165
7.3.3. Háromfázisú véglegesítés 167
7.3.4. Alsó korlát az üzenetek számára 171
7.4. Megjegyzések a fejezethez 173
7.5. Gyakorlatok 174
II. Aszinkron algoritmusok (Lektor Horváth Zoltán, fordító Kása Zoltán) 177
8. Modellezés/II. Aszinkron rendszerek modelljei 178
8.1. b/k-automaták 179
8.2. Műveletek automatákkal 185
8.2.1. Összekapcsolás 185
8.2.2. Elrejtés 190
8.3. Pártatlanság 190
8.4. Feladatok bemeneti és kimeneti adatai 193
8.5. Tulajdonságok és bizonyítási módszerek 194
8.5.1. Invariáns állítások 194
8.5.2. Történetre vonatkozó tulajdonságok 194
8.5.3. Biztonságossági és elevenségi tulajdonságok 196
8.5.4. Összekapcsolási érvelés 199
8.5.5. Szintekre bontott bizonyítások 202
8.6. Bonyolultsági mértékek 206
8.7. Megkülönböztethetetlen végrehajtási sorozatok 207
8.8. Véletlenítés 207
8.9. Megjegyzések a fejezethez 208
8.10. Gyakorlatok 209
II.A. Aszinkron közös memóriájú algoritmusok (Szűcs Attila) 213
9. Modellezés/III. Aszinkron közös memóriájú modell 214
9.1. Közös memóriájú rendszerek 214
9.2. Környezeti modell 218
9.3. Megkülönböztethetetlen állapotok 220
9.4. Közös változók típusai 220
9.5. Bonyolultsági mértékek 226
9.6. Hibák 226
9.7. Véletlenítés 227
9.8. Megjegyzések a fejezethez 228
9.9. Gyakorlatok 228
10. Kölcsönös kizárás (Zsók Viktória) 230
10.1. Az aszinkron közös memória modellje 231
10.2. A feladat 233
10.3. Dijkstra algoritmusa a kölcsönös kizárás megoldására 239
10.3.1. Az algoritmus 239
10.3.2. Az algoritmus helyessége 243
10.3.3. A kölcsönös kizárás feltételének bizonyítása állítások segítségével 246
10.3.4. Futásidő 248
10.4. Erősebb feltételek a kölcsönös kizárás algoritmusaira 250
10.5. Kizárásmentes kölcsönös kizárási algoritmusok 253
10.5.1. Az algoritmus két folyamat esetében 253
10.5.2. Egy n folyamatra adott algoritmus 258
10.5.3. Verseny algoritmus 264
10.6. Kizárólagosan írható közös regiszteres algoritmus 269
10.7. A VÁRÓTEREM algoritmus 271
10.8. Alsó korlát a regiszterek számára 274
10.8.1. Alapvető tények 275
10.8.2. Kizárólagosan írható közös változók 276
10.8.3. Megosztottan írható közös változók 277
10.9. Kölcsönös kizárás olvasható-módosítható-írható típusú közös változókkal 283
10.9.1. Az alapfeladat 283
10.9.2. Korlátozott megkerülés 285
10.9.3. Kizárásmentesség 293
10.9.4. Szimulációs bizonyítás 296
10.10. Megjegyzések a fejezethez 300
10.11. Gyakorlatok 301
11. Erőforrások hozzárendelése (Tejfel Máté) 308
11.1. A feladat 308
11.1.1. Explicit erőforrás-leírások és kizárási leírások 308
11.1.2. Az erőforrás-hozzárendelési feladat 310
11.1.3. Az étkező filozófusok feladat 312
11.1.4. A megoldások korlátozott formája 313
11.2. Nincs szimmetrikus megoldás az étkező filozófusok problémájára 314
11.3. Jobb-bal algoritmus az étkező filozófusok problémájára 317
11.3.1. Várakozási láncok 317
11.3.2. Az alap algoritmus 319
11.3.3. Egy általánosítás 322
11.4. Véletlenített algoritmus az étkező filozófusok problémájára 327
11.4.1. Az algoritmus 327
11.4.2. Helyesség 330
11.5. Megjegyzések a fejezethez 339
11.6. Gyakorlatok 340
12. Megegyezés (Nikovits Tibor) 343
12.1. A feladat 343
12.2. Megegyezés olvasható/írható közös memóriával 347
12.2.1. Korlátozások 348
12.2.2. Terminológia 348
12.2.3. Kétértékű kezdőérték-beállítások 349
12.2.4. A várakozásmentes befejeződés megoldhatatlansága 350
12.2.5. Az 1-hibás befejeződés megoldhatatlansága 354
12.3. Megegyezés olvasható/módosítható/írható közös memóriával 359
12.4. Más típusú közös memória 360
12.5. Kiszámíthatóság aszinkron közös memóriájú rendszerekben 360
12.6. Megjegyzések a fejezethez 362
12.7. Gyakorlatok 363
13. Atomi objektumok (Horváth Gyula) 367
13.1. Alapfogalmak és eredmények 368
13.1.1. Atomi objektum definíciója 368
13.1.2. Kanonikus várakozásmentes atomi objektum automata 377
13.1.3. Atomi objektumok összekapcsolása 379
13.1.4. Atomi objektumok avagy közös változók 379
13.1.5. Elegendő feltétel atomiság kimutatására 386
13.2. olvasható/módosítható/írható atomi objektum megvalósítása olvasható/írható változókkal 387
13.3. Közös memóriák atomi fényképei 388
13.3.1. A feladat 389
13.3.2. Egy nemkorlátos változót használó algoritmus 390
13.3.3. Egy korlátos változókat használó algoritmus 394
13.4. olvasható/írható atomi objektumok 400
13.4.1. A feladat 400
13.4.2. Egy másik lemma atomiság kimutatására 401
13.4.3. Egy korlátlan változókat használó algoritmus 402
13.4.4. Egy korlátos algoritmus két íróra 405
13.4.5. Egy fénykép objektumot használó algoritmus 412
13.5. Megjegyzések a fejezethez 413
13.6. Gyakorlatok 415
II.B. Aszinkron hálózati algoritmusok (Lektor Kormos János, fordító Fazekas Gábor) 419
14. Modellezés/IV. Aszinkron hálózati modell 420
14.1. Küld/fogad rendszerek 420
14.1.1. Folyamatok 420
14.1.2. Küld/fogad csatornák 421
14.1.3. Aszinkron küld/fogad rendszerek 426
14.1.4. Megbízható FIFO csatornákkal rendelkező küld/fogad rendszerek tulajdonságai 427
14.1.5. Bonyolultsági mértékek 428
14.2. Üzenetszóró rendszerek 428
14.2.1. Folyamatok 429
14.2.2. Üzenetszóró csatorna 429
14.2.3. Aszinkron üzenetszóró rendszerek 430
14.2.4. Megbízható üzenetszóró csatornával rendelkező üzenetszóró rendszerek tulajdonságai 430
14.2.5. Bonyolultsági mértékek 431
14.3. Többletes üzenetszóró rendszerek 431
14.3.1. Folyamatok 432
14.3.2. Többletes üzenetszóró csatorna 432
14.3.3. Aszinkron többletes üzenetszóró rendszerek 433
14.4. Megjegyzések a fejezethez 433
14.5. Gyakorlatok 433
15. Alapvető aszinkron hálózati algoritmusok (Lencse Zsolt) 436
15.1. Vezető folyamat megválasztása gyűrűben 436
15.1.1. Az LCR algoritmus 436
15.1.2. A HS algoritmus 442
15.1.3. A Peterson-féle vezetőválasztási algoritmus 442
15.1.4. Alsó korlát a kommunikációs bonyolultságra 446
15.2. Vezető folyamat megválasztása tetszőleges hálózatban 454
15.3. Feszítőfa konstruálása, üzenetszórás és konvergens üzenetszórás 455
15.4. Szélességi keresés és legrövidebb utak 460
15.5. Minimális feszítőfa 467
15.5.1. A feladat megfogalmazása 467
15.5.2. A szinkron algoritmus: áttekintés 468
15.5.3. A GHS algoritmus vázlata 469
15.5.4. A GHS algoritmus részletesebben 470
15.5.5. Konkrét üzenetek 474
15.5.6. Bonyolultságelemzés 476
15.5.7. A GHS algoritmus helyességének bizonyítása 477
15.5.8. Egy egyszerűbb „szinkron" stratégia 478
15.5.9. A vezetőválasztás alkalmazása 479
15.6. Megjegyzések a fejezethez 480
15.7. Gyakorlatok 481
16. Szinkronizátorok (Hajdú András) 486
16.1. A feladat 487
16.2. Helyi szinkronizátor 490
16.3. Biztonságos szinkronizátor 495
16.3.1. Előtét automata 497
16.3.2. Csatorna automaták 498
16.3.3. A biztonságos szinkronizátor 498
16.3.4. Helyesség 499
16.4. A biztonságos szinkronizátor megvalósításai 500
16.4.1. Az Alfa szinkronizátor 500
16.4.2. A BÉTA szinkronizátor 501
16.4.3. A Gamma szinkronizátor 502
16.5. Alkalmazások 507
16.5.1. Vezetőválasztás 507
16.5.2. Szélességi keresés 508
16.5.3. Legrövidebb utak 508
16.5.4. Üzenetszórás és nyugtázás 509
16.5.5. Maximális független halmaz 509
16.6. Alsó korlát a futási időre 509
16.7. Megjegyzések a fejezethez 513
16.8. Gyakorlatok 514
17. Közös memória és hálózatok 517
17.1. A közös memória modell transzformálása a hálózati modellre 517
17.1.1. A feladat 517
17.1.2. Hibamentességet feltételező stratégiák 518
17.1.3. A folyamatok hibáit tűrő algoritmus 526
17.1.4. Egy megoldhatatlansági eredmény | hiba esetében 531
17.2. A hálózati modell transzformálása a közös memóriájú modellre 532
17.2.1. Küld/fogad rendszerek 533
17.2.2. Üzenetszóró rendszerek 535
17.2.3. Megegyezés megoldhatatlansága aszinkron hálózatokban 536
17.3. Megjegyzések a fejezethez 536
17.4. Gyakorlatok 537
18. Logikai idő (Kollár Lajos) 539
18.1. Logikai idő aszinkron hálózatokra 539
18.1.1. Küld/fogad rendszerek 539
18.1.2. Üzenetszóró rendszerek 543
18.2. Logikai idő hozzáadása az aszinkron algoritmusokhoz 543
18.2.1. Az óra előreállítása 544
18.2.2. Jövőbeli események késleltetése 546
18.3. Alkalmazások 547
18.3.1. Banki rendszerek 547
18.3.2. Globális fényképek 551
18.3.3. Egyállapotú gépek szimulálása 552
18.4. Valósidejű és logikai idejű algoritmusok 557
18.5. Megjegyzések a fejezethez 558
18.6. Gyakorlatok 558
19. Ellentmondásmentes globális fényképek és stabil tulajdonságjelzés (Hajdú András) 562
19.1. Befejeződés jelzése terjesztő algoritmusokhoz 562
19.1.1. A feladat 562
19.1.2. A DijkstraScholten algoritmus 563
19.2. Ellentmondásmentes globális fényképek 569
19.2.1. A feladat 569
19.2.2. A ChandyLamport algoritmus 570
19.2.3. Alkalmazások 576
19.3. Megjegyzések a fejezethez
19.4. Gyakorlatok 579
20. Hálózati erőforrások hozzárendelése (Iványi Antal) 582
20.1. Kölcsönös kizárás 582
20.1.1. A feladat 582
20.1.2. A közös memória szimulálása 584
20.1.3. A KörbejáróJel algoritmus 584
20.1.4. Logikai időn alapuló algoritmus 586
20.1.5. A LogikaiIdőK algoritmus javításai 590
20.2. Általános erőforrás-hozzárendelés 593
20.2.1. A feladat 593
20.2.2. Színezési algoritmus 594
20.2.3. Logikai időn alapuló algoritmusok 595
20.2.4. Algoritmus körmentes irányított gráfra 596
20.2.5. Ivó filozófusok 598
20.3. Megjegyzések a fejezethez 604
20.4. Gyakorlatok 604
21. Aszinkron hálózati számítás folyamat hibákkal (Ispány Márton) 608
21.1. A hálózati modell 608
21.2. Megegyezés megoldhatatlansága hibák esetében 610
21.3. Egy véletlenített algoritmus 611
21.4. Hibajelzők 615
21.5. fc-megegyezés 619
21.6. Közelítő megegyezés 620
21.7. Kiszámíthatóság aszinkron hálózatokban 622
21.8. Megjegyzések a fejezethez 623
21.9. Gyakorlatok 623
22. Adatkapcsolat protokollok (Benczúr András, jr.) 627
22.1. A feladat 627
22.2. A Stenning protokoll 628
22.3. A BitVáltó protokoll 632
22.4. Átrendeződés-tűrő korlátos címkéjű protokollok 636
22.4.1. Megoldhatatlanság átrendezés és többszörözés esetében 637
22.4.2. Egy üzenetvesztést és átrendezést tűrő korlátos címkés protokoll 639
22.4.3. A veszteséges átrendező csatornák hatékonysági korlátja 644
22.5. Katasztrófatűrő protokollok 648
22.5.1. Egy egyszerű megoldhatatlansági bizonyítás 649
22.5.2. Egy erősebb megoldhatatlansági bizonyítás 650
22.5.3. Az ÖtCsomag protokoll 653
22.6. Megjegyzések a fejezethez 660
22.7. Gyakorlatok 661
III. Részben szinkron algoritmusok Részben szinkron algoritmusok 665
23. Modellezés/V. Részben szinkron rendszerek modelljei (Lektor Csirik János, fordító Horváth Gyula) 666
23.1. MMT időzített automata 666
23.1.1. Alapfogalmak 667
23.1.2. Műveletek 672
23.2. Általános időzített automata 674
23.2.1. Alapfogalmak 675
23.2.2. MMT automata átalakítása általános időzített automatával 680
23.2.3. Műveletek 684
23.3. Tulajdonságok és bizonyítási módszerek 686
23.3.1. Invariáns állítások 686
23.3.2. Időzített történet tulajdonságok 689
23.3.3. Szimuláció 690
23.4. Közös memóriájú és hálózati rendszerek modellezése 697
23.4.1. Közös memóriájú rendszerek 697
23.4.2. Hálózatok 698
23.5. Megjegyzések a fejezethez 698
23.6. Gyakorlatok 699
24. Kölcsönös kizárás részleges szinkronizációval (Virágh János) 701
24.1. A feladat 701
24.2. Egyregiszteres algoritmus 702
24.3. Időzítési hibákkal szembeni ellenállóképesség 712
24.4. Megoldhatatlansági eredmények 714
24.4.1. Alsó időkorlát 715
24.4.2. Végső időkorlátos megoldhatatlansági eredmények 716
24.5. Megjegyzések a fejezethez 717
24.6. Gyakorlatok 717
25. Megegyezés részleges szinkronizációval 720
25.1. A feladat 720
25.2. Hibajelző 721
25.3. Alapvető eredmények 723
25.3.1. Felső korlát 723
25.3.2. Alsó korlát 725
25.4. Egy hatékony algoritmus 727
25.4.1. Az algoritmus 727
25.4.2. Biztonságossági tulajdonságok 729
25.4.3. Élénkség és bonyolultság 730
25.5. Az időzítési bizonytalanságot tartalmazó alsó korlát 734
25.6. További eredmények 741
25.6.1. Szinkron folyamatok aszinkron csatornákkal 741
25.6.2. Aszinkron folyamatok szinkron csatornákkal 742
25.6.3. Végső időkorlátok 742
25.7. Utóirat 745
25.8. Megjegyzések a fejezethez 746
25.9. Gyakorlatok 746
Irodalomjegyzék 749
Tárgymutató 764

Témakörök

Nancy Ann Lynch

Nancy Ann Lynch műveinek az Antikvarium.hu-n kapható vagy előjegyezhető listáját itt tekintheti meg: Nancy Ann Lynch könyvek, művek

Megvásárolható példányok

Nincs megvásárolható példány
A könyv összes megrendelhető példánya elfogyott. Ha kívánja, előjegyezheti a könyvet, és amint a könyv egy újabb példánya elérhető lesz, értesítjük.

Előjegyzem