Lynch, Nancy Ann : 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 hely 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ás-mentessé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.