OSZTOTT ALGORITMUSOK

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 avezető 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 évtitzedes munkájának eredményeit foglalja össze.

Tartalom
1. Bevezetés
II. Szinkron hálózati algoritmusok
2. Modellezés / I. Szinkron hálózati modell
3. Vezető folyamat kiválasztása szinkron gyűrűben
4. Általános szinkron hálózatok algoritmusai
5. Megegyezés osztott hálózatokban, vonalhibák esetében
6. Egyetértés osztott hálózatokban processzorhibák esetében
7. További megegyezési problémák
III. Aszinkron algoritmusok
8. Modellezés II. Aszinkron rendszerek modelljei
IV.A. Aszinkron közös memóriájú algoritmusok
9. Modellezés /III. Aszinkron közös memóriájú modell
10. Kölcsönös kizárás
11. Erőforrások hozzárendelése
12. Megegyezés
13. Atomi objektumok
II.B. Aszinkron hálózati algoritmusok
14. Modellezés / IV. Aszinkron hálózati modell
15. Alapvető aszinkron hálózati algoritmusok
16. Szinkronizátorok
17. Közös memória és hálózatok
18. Logikai idő
19. Ellentmondásmentes globális fényképek és stabil tulajdonságjelzés
20. Hálózati erőforrások hozzárendelése
21. Aszinkron hálózati számítás folyamat hibákkal
22. Adatkapcsolat protokollok
III. Részlegesen aszinkron algoritmusok
23. Modellezés / V. Részlegesen szinkron rendszerek modelljei
24. Kölcsönös kizárás részleges szinkronizációval
25. Megegyezés részleges szinkronizációval


A kötet adatai:
Méret: 187x235 mm
Kötés: Puhakötés
Megjelenés éve: 2002
Terjedelem: 782 oldal