Расподељено израчунавање

Расподељено израчунавање је поље информатике које проучава расподељене системе. Расподељени систем је софтверски систем у којем компоненте постављене на повезане рачунаре комуницирају и координирају своје акције слањем порука. Компоненте интерагују једна са другом како би постигле заједнички циљ. Постоји много алтернатива овом систему, укључујући конекторе попут РПЦ и редови порука. Битне карактеристике раподељених система су: конкурентност компоненти, недостатак глобалног такта, и независно цркавање компоненти. Битан циљ и изазиов ових система је транспаренција локације. Примери расподељених система варирају од СОА система преко ММОГ до П2П апликација.

Рачунарски програм који ради у расподељеном систему се зове раподељени програм, и раподељено програмирање је процес писања таквих програма.

Расподељено израчунавање се такође односи на расподељене системе који решавају рачунске проблеме. У расподељеном израчунавању, проблем се дели на много задатака, од којих се сваки решава коришћењем једног или више рачунара, који који комуницирају преко порука.

Увод

Реч расподељено у терминима попут расподељени систем, расподељено програмирање и расподељени алгоритам су се односили на рачунарске мреже где су појединачни рачунари били физички расподељени у некој географској области. Ови термини се данас користе у много ширем смислу, чак се односе и на аутономне процесе који раде на истом физичком рачунару и интерагују један са другим порукама. Има више дефиниција расподељеног система, па се следећа својства користе при дефинисању:

• Постоје неколико аутономних рачунарских ентитета, од којих сваки има своју локалну меморију.
• Ентитети комуницирају један са другим преко слања порука.

На овој страници, рачунарски ентитети се зову рачунари или чворови.

Расподељени систем може имати заједнички циљ, као што је решавање великог рачунског проблема. Алтернативно сваки рачунар може имати сопственог корисника са посебним потребама, и циљ раподељеног система је да координише коришћење дељених ресурса и да обезбеди комуникацијске услуге својим корисницима.

Остале особине расподељених система укључују следеће:

• Систем мора да толерише кварове у појединачним рачунарима.
• Структура система (топологија мреже, латенција, број рачунара) се не зна унапред, систем се може састојати из различитих врста рачунара и мрежних веза, и систем се може променити током извршавања расподељеног програма.
• Сваки рачунар има ограничен и непотпун поглед на систем. Сваки рачунар може знати само један део улаза.

(a)–(b) Расподељени систем
(c) Паралелни систем.

Паралелно и расподељено израчунавање

Расподељени системи су групе повезаних рачунара, који имају исти циљ свог рада. Термини "Конкурентно израчунавање", "Паралелна обрада" и "расподељено израчунавање" имају много преклапања, и не постоји јасна дистинкција. Исти систем се моће окрарактерисати као паралелни и расподељен. Процесори у типичном раподељеном систему раде конкурентно паралелно. Ипак је могућа груба класификација конкурентих система као паралелних или распоређених користеће следеће критеријуме:

• У паралелној обради сви процесори могу имати приступ дељеној меморији за размену информација између процесора.
• У расподељеном израчунавању, сваки процесор има своју приватну меморију (распоређену меморију). Инфомације се преносе порукама међу процесорима.

Слика са десне стране илуструје разлику између распоређених и паралелних система. Приказ (а) је шематски приказ типичног дистрибуираног система. Као и обично, систем се приказује као мрежна топологија у којој је сваки чвор рачунар и свака линија која повезује чворове је веза за комуницирање. Приказ (b) приказује исти распоређени систем са више детаља: сваки рачунар има своју локалну меморију, и информација може бити пренесена само размењујући поруке од једног до другог чвора користећи доступне везе за комуникацију. Приказ (c) показује паралелни систем у којем сваки процесор има директан приступ дељеној меморији.

Систуација се даље компликује традиционалним коришћењем термина паралелни и расподељени алгоритми који се не слажу са горњим дефиницијама тако названих система. Ипак као правило, паралелна обрада високих перформанси у мултипроцесору са дељеном меморијом користи паралелне алгоритме док координација великих расподељених система користи расподељене алгоритме.

Историја

Коришћење конкурентних процеса који комуницирају слањем порука има корене у архитектурама оперативних система изучаваних 60-их година. Први широко распоређени системи су били ЛАН мреже као што је Етернет, који је направљен 1960—их година.

АРПАНЕТ је претходник Интернета, и створен је крајем 1960-их, и АРПАНЕТ електронска пошта је створена крајем 70-их. Електронска пошта је постала најуспешнија примена АРПАНЕТА, и вероватно је најранији пример широко рапсрострањене апликације.

Студија рапсрострањеног израчунавања је постала своје поље у информатици у касним 70им и раним 80им годинама. Прва конференција у овом пољу, Symposium on Principles of Distributed Computing (PODC) је била 1982, а европски еквивалент International Symposium on Distributed Computing (DISC) је први пут одржан 1985.

Примене

Разлози за коришћење распоређених система и израчунавања су:

• Сама природа апликације можда захтева коришћење комуникационе мреже која повезује више рачуанра. На пример, подаци произведени на једној физичкој локацији и тражени на другој.
• Постоје разни случајеви у којима би коришћење рачунара било могуће, али би расподељено рачунање имало више бенефиција. На пример, може бити ефикасније и јефтиније добити ниво перформанси од више слабијих рачунара, уместо један веом јак. Распоређени систем може бити поузданији од других система. Штавише распоређени систем може бити једноставнији за ширење и управљање од монолитног једнопроцесорског система.

Примери

• Телекомуникационе мреже
  • Телефонске и мобилне мреже
  • Рачунарске мреже као што је интернет
  • Бежичне сензорне мреже
  • Алгоритми рутирања
• Мрежне примене
  • Интернет и П2П
  • Распоређене базе података и управљачки системи
  • Мрежни системи података
  • Расподељени системи процесуирања података
• Контрола процеса у реалном времену
  • Контрола авионских система
  • Контрола индустријских система
• Паралелна обрада
  • Науно рачунарство
  • Расподељено рендеровање

Изборни координатор

Како би извршили координацију, распоређени системи користе концепт координатора. Проблем изборног координатора је да изавере процес из групе процеса на различитим процесорима у распоређеном систему да се понаша као централни координатор. Постоји неколико алгоритама за избор коодринатора.

Силеџијски алгоритам

При коришћењу овог алгоритма, било који процес шаље поруку тренутном координатору. Ако нема одговора у одређеном временском раздобљу, процес покушава да изабере себе за вођу.

Ченг и Робертсов алгоритам

Ченг и Робертсов алгоритам је изборни алгоритам базиран на прстену, и користи се за проналажење процесора са највећим јединственим идентификационим бројем.

Архитектуре

Разне хадрверске и софтверске архитектуре се користе распоређено израчунавање. На нижем нивоу, неопходно је повезати више ЦПЈ-а са неком врстом мреже, без обзира да ли је та мрежа на штампаној плочи или је повезана кабловима. На вишем нивоу, неоходно је повезати процесе који раде на тим ЦПЈ-ама са неким комуникационим системом.

Распоређено програмирање типично упада у један од неколико основних архитектура или категорија: клијент-сервер, n-ранг архитектуре, расподељени објекти, лабаво спајање или тесно спајање.

Клијент-сервер: Паметн клијентов код контактира сервере за податке и онда их форматира и приказује кориснику. Улаз код клијента се враћа до сервера где представља промену.

• Архитектура трећег ранга: Три система ранга померају податке о клијенту у средњи ранг како би клијенти без статуса могли бити коришћени. Ово олакшава развој апликације. Већина Веб апликација су са три ранга.
• Архитектура са n рангова: n-ранг се типично односи на веб апликације које даље прослеђују своје апликације са сервисима предузећа. Овај тип аликације је најзаслужнији за успех апликационих сервера.
• Високо упарени (кластер): односе се на кластер машина које раде блиско заједно, и извршавају дељени процес паралелно. Задатак је подељен на делове који су прављени појединачно и онда састављени да направе коначни резултат.
• П2П: архитектура где не постоји посебна машина или машине који прижају услугу или управљају мрежним ресурсима. Уместо тога, све одговорности су једнако распоређене на све машине, које се зову вршњаци. Вршњаци могу служити као сервери и клијенти.
• Базирано на простору: односи се на инфрастурктуру која прави илузију (виртуелизацију) једног адресног простора. Подаци се транспарентно прелицирају по потребама апликације.

Још један прост аспекат архитектуре распоређеног израчунавања је метод комуникације и координације посла између конкурентних процеса. Кроз разне протоколе слања порука процеси могу комуницирати директно један са другим типично у господар-роб односу.

Литаратура

Књиге

• Andrews, Gregory R. (2000), Foundations of Multithreaded, Parallel, and Distributed Programming, Addison–Wesley, ISBN 978-0-201-35752-3 .
• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity – A Modern Approach, Cambridge, ISBN 978-0-521-42426-4 .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990), Introduction to Algorithms (1st изд.), MIT Press, ISBN 978-0-262-03141-7 .
• Dolev, Shlomi (2000), Self-Stabilization, MIT Press, ISBN 978-0-262-04178-2 .
• Elmasri, Ramez; Navathe, Shamkant B. (2000), Fundamentals of Database Systems (3rd изд.), Addison–Wesley, ISBN 978-0-201-54263-9 .
• Ghosh, Sukumar (2007), Distributed Systems – An Algorithmic Approach, Chapman & Hall/CRC, ISBN 978-1-58488-564-1 .
• Lynch, Nancy A. (1996), Distributed Algorithms, Morgan Kaufmann, ISBN 978-1-55860-348-6 .
• Herlihy, Maurice P.; Shavit, Nir N. (2008), The Art of Multiprocessor Programming, Morgan Kaufmann, ISBN 978-0-12-370591-4 .
• Papadimitriou, Christos H. (1994), Computational Complexity, Addison–Wesley, ISBN 978-0-201-53082-7 .
• Peleg, David (2000), Distributed Computing: A Locality-Sensitive Approach, SIAM, ISBN 978-0-89871-464-7, Архивирано из оригинала 6. 8. 2009. г., Приступљено 15. 1. 2014 .

Чланци

• Cole, Richard; Vishkin, Uzi (1986), „Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control, 70 (1): 32—53, doi:10.1016/S0019-9958(86)80023-7 .
• Keidar, Idit (2008), „Distributed computing column 32 – The year in review”, ACM SIGACT News, 39 (4): 53—54, S2CID 7607391, doi:10.1145/1466390.1466402, Архивирано из оригинала 16. 01. 2014. г., Приступљено 15. 01. 2014 .
• Linial, Nathan (1992), „Locality in distributed graph algorithms”, SIAM Journal on Computing, 21 (1): 193—201, doi:10.1137/0221015 .
• Naor, Moni; Stockmeyer, Larry (1995), „What can be computed locally?”, SIAM Journal on Computing, 24 (6): 1259—1277, doi:10.1137/S0097539793254571 .

Веб странице

• Godfrey, Bill (2002). „A primer on distributed computing”. Архивирано из оригинала 25. 02. 2010. г. Приступљено 15. 01. 2014. 
• Peter, Ian (2004). „Ian Peter's History of the Internet”. Приступљено 4. 8. 2009. 

Књиге

• Attiya, Hagit; Welch, Jennifer (2004). Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley-Interscience. ISBN 978-0-471-45324-6. 
• Cachin, Christian; Guerraoui, Rachid; Rodrigues, Luís (2011). Introduction to Reliable and Secure Distributed Programming (2. изд.). Springer. ISBN 978-3-642-15259-7. 
• Coulouris, George; et al. (2011). Distributed Systems: Concepts and Design (5th изд.). Addison-Wesley. ISBN 978-0-13-214301-1. 
• Faber, Jim (1998), Java Distributed Computing, O'Reilly : Java Distributed Computing by Jim Faber, 1998
• Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 978-0-471-03600-5. 
• Tel, Gerard (1994), Introduction to Distributed Algorithms, Cambridge University Press 
• Chandy, Mani; et al., Parallel Program Design 

Артикли

• Keidar, Idit; Rajsbaum, Sergio, ур. (2000), „Distributed computing column”, [[ACM SIGACT News]], Архивирано из оригинала 16. 01. 2014. г., Приступљено 15. 01. 2014  .
• Birrell, A. D.; Levin, R.; Schroeder, M. D.; Needham, R. M. (1982). „Grapevine: An exercise in distributed computing” (PDF). Communications of the ACM. 25 (4): 260—274. S2CID 16066616. doi:10.1145/358468.358487. Архивирано из оригинала (PDF) 10. 8. 2010. г. Приступљено 15. 1. 2017. 

Извештаји са конференције

• Rodriguez, Carlos; Villagra, Marcos; Baran, Benjamin (2007). „Asynchronous team algorithms for Boolean Satisfiability”. 2007 2nd Bio-Inspired Models of Network, Information and Computing Systems. Bionetics. стр. 66—69. S2CID 15185219. doi:10.1109/BIMNICS.2007.4610083. 

Спољашње везе

• Distributed computing на сајту Curlie (језик: енглески)
• Distributed computing journals на сајту Curlie (језик: енглески)