Raspodeljeno izračunavanje

Raspodeljeno izračunavanje je polje informatike koje proučava raspodeljene sisteme. Raspodeljeni sistem je softverski sistem u kojem komponente postavljene na povezane računare komuniciraju i koordiniraju svoje akcije slanjem poruka. Komponente interaguju jedna sa drugom kako bi postigle zajednički cilj. Postoji mnogo alternativa ovom sistemu, uključujući konektore poput RPC i redovi poruka. Bitne karakteristike rapodeljenih sistema su: konkurentnost komponenti, nedostatak globalnog takta, i nezavisno crkavanje komponenti. Bitan cilj i izaziov ovih sistema je transparencija lokacije. Primeri raspodeljenih sistema variraju od SOA sistema preko MMOG do P2P aplikacija.

Računarski program koji radi u raspodeljenom sistemu se zove rapodeljeni program, i rapodeljeno programiranje je proces pisanja takvih programa.

Raspodeljeno izračunavanje se takođe odnosi na raspodeljene sisteme koji rešavaju računske probleme. U raspodeljenom izračunavanju, problem se deli na mnogo zadataka, od kojih se svaki rešava korišćenjem jednog ili više računara, koji koji komuniciraju preko poruka.

Uvod

Reč raspodeljeno u terminima poput raspodeljeni sistem, raspodeljeno programiranje i raspodeljeni algoritam su se odnosili na računarske mreže gde su pojedinačni računari bili fizički raspodeljeni u nekoj geografskoj oblasti. Ovi termini se danas koriste u mnogo širem smislu, čak se odnose i na autonomne procese koji rade na istom fizičkom računaru i interaguju jedan sa drugim porukama. Ima više definicija raspodeljenog sistema, pa se sledeća svojstva koriste pri definisanju:

• Postoje nekoliko autonomnih računarskih entiteta, od kojih svaki ima svoju lokalnu memoriju.
• Entiteti komuniciraju jedan sa drugim preko slanja poruka.

Na ovoj stranici, računarski entiteti se zovu računari ili čvorovi.

Raspodeljeni sistem može imati zajednički cilj, kao što je rešavanje velikog računskog problema. Alternativno svaki računar može imati sopstvenog korisnika sa posebnim potrebama, i cilj rapodeljenog sistema je da koordiniše korišćenje deljenih resursa i da obezbedi komunikacijske usluge svojim korisnicima.

Ostale osobine raspodeljenih sistema uključuju sledeće:

• Sistem mora da toleriše kvarove u pojedinačnim računarima.
• Struktura sistema (topologija mreže, latencija, broj računara) se ne zna unapred, sistem se može sastojati iz različitih vrsta računara i mrežnih veza, i sistem se može promeniti tokom izvršavanja raspodeljenog programa.
• Svaki računar ima ograničen i nepotpun pogled na sistem. Svaki računar može znati samo jedan deo ulaza.

(a)–(b) Raspodeljeni sistem
(c) Paralelni sistem.

Paralelno i raspodeljeno izračunavanje

Raspodeljeni sistemi su grupe povezanih računara, koji imaju isti cilj svog rada. Termini "Konkurentno izračunavanje", "Paralelna obrada" i "raspodeljeno izračunavanje" imaju mnogo preklapanja, i ne postoji jasna distinkcija. Isti sistem se moće okrarakterisati kao paralelni i raspodeljen. Procesori u tipičnom rapodeljenom sistemu rade konkurentno paralelno. Ipak je moguća gruba klasifikacija konkurentih sistema kao paralelnih ili raspoređenih koristeće sledeće kriterijume:

• U paralelnoj obradi svi procesori mogu imati pristup deljenoj memoriji za razmenu informacija između procesora.
• U raspodeljenom izračunavanju, svaki procesor ima svoju privatnu memoriju (raspoređenu memoriju). Infomacije se prenose porukama među procesorima.

Slika sa desne strane ilustruje razliku između raspoređenih i paralelnih sistema. Prikaz (a) je šematski prikaz tipičnog distribuiranog sistema. Kao i obično, sistem se prikazuje kao mrežna topologija u kojoj je svaki čvor računar i svaka linija koja povezuje čvorove je veza za komuniciranje. Prikaz (b) prikazuje isti raspoređeni sistem sa više detalja: svaki računar ima svoju lokalnu memoriju, i informacija može biti prenesena samo razmenjujući poruke od jednog do drugog čvora koristeći dostupne veze za komunikaciju. Prikaz (c) pokazuje paralelni sistem u kojem svaki procesor ima direktan pristup deljenoj memoriji.

Sistuacija se dalje komplikuje tradicionalnim korišćenjem termina paralelni i raspodeljeni algoritmi koji se ne slažu sa gornjim definicijama tako nazvanih sistema. Ipak kao pravilo, paralelna obrada visokih performansi u multiprocesoru sa deljenom memorijom koristi paralelne algoritme dok koordinacija velikih raspodeljenih sistema koristi raspodeljene algoritme.

Istorija

Korišćenje konkurentnih procesa koji komuniciraju slanjem poruka ima korene u arhitekturama operativnih sistema izučavanih 60-ih godina. Prvi široko raspoređeni sistemi su bili LAN mreže kao što je Eternet, koji je napravljen 1960—ih godina.

ARPANET je prethodnik Interneta, i stvoren je krajem 1960-ih, i ARPANET elektronska pošta je stvorena krajem 70-ih. Elektronska pošta je postala najuspešnija primena ARPANETA, i verovatno je najraniji primer široko rapsrostranjene aplikacije.

Studija rapsrostranjenog izračunavanja je postala svoje polje u informatici u kasnim 70im i ranim 80im godinama. Prva konferencija u ovom polju, Symposium on Principles of Distributed Computing (PODC) je bila 1982, a evropski ekvivalent International Symposium on Distributed Computing (DISC) je prvi put održan 1985.

Primene

Razlozi za korišćenje raspoređenih sistema i izračunavanja su:

• Sama priroda aplikacije možda zahteva korišćenje komunikacione mreže koja povezuje više račuanra. Na primer, podaci proizvedeni na jednoj fizičkoj lokaciji i traženi na drugoj.
• Postoje razni slučajevi u kojima bi korišćenje računara bilo moguće, ali bi raspodeljeno računanje imalo više beneficija. Na primer, može biti efikasnije i jeftinije dobiti nivo performansi od više slabijih računara, umesto jedan veom jak. Raspoređeni sistem može biti pouzdaniji od drugih sistema. Štaviše raspoređeni sistem može biti jednostavniji za širenje i upravljanje od monolitnog jednoprocesorskog sistema.

Primeri

• Telekomunikacione mreže
  • Telefonske i mobilne mreže
  • Računarske mreže kao što je internet
  • Bežične senzorne mreže
  • Algoritmi rutiranja
• Mrežne primene
  • Internet i P2P
  • Raspoređene baze podataka i upravljački sistemi
  • Mrežni sistemi podataka
  • Raspodeljeni sistemi procesuiranja podataka
• Kontrola procesa u realnom vremenu
  • Kontrola avionskih sistema
  • Kontrola industrijskih sistema
• Paralelna obrada
  • Nauno računarstvo
  • Raspodeljeno renderovanje

Izborni koordinator

Kako bi izvršili koordinaciju, raspoređeni sistemi koriste koncept koordinatora. Problem izbornog koordinatora je da izavere proces iz grupe procesa na različitim procesorima u raspoređenom sistemu da se ponaša kao centralni koordinator. Postoji nekoliko algoritama za izbor koodrinatora.

Siledžijski algoritam

Pri korišćenju ovog algoritma, bilo koji proces šalje poruku trenutnom koordinatoru. Ako nema odgovora u određenom vremenskom razdoblju, proces pokušava da izabere sebe za vođu.

Čeng i Robertsov algoritam

Čeng i Robertsov algoritam je izborni algoritam baziran na prstenu, i koristi se za pronalaženje procesora sa najvećim jedinstvenim identifikacionim brojem.

Arhitekture

Razne hadrverske i softverske arhitekture se koriste raspoređeno izračunavanje. Na nižem nivou, neophodno je povezati više CPJ-a sa nekom vrstom mreže, bez obzira da li je ta mreža na štampanoj ploči ili je povezana kablovima. Na višem nivou, neohodno je povezati procese koji rade na tim CPJ-ama sa nekim komunikacionim sistemom.

Raspoređeno programiranje tipično upada u jedan od nekoliko osnovnih arhitektura ili kategorija: klijent-server, n-rang arhitekture, raspodeljeni objekti, labavo spajanje ili tesno spajanje.

Klijent-server: Pametn klijentov kod kontaktira servere za podatke i onda ih formatira i prikazuje korisniku. Ulaz kod klijenta se vraća do servera gde predstavlja promenu.

• Arhitektura trećeg ranga: Tri sistema ranga pomeraju podatke o klijentu u srednji rang kako bi klijenti bez statusa mogli biti korišćeni. Ovo olakšava razvoj aplikacije. Većina Veb aplikacija su sa tri ranga.
• Arhitektura sa n rangova: n-rang se tipično odnosi na veb aplikacije koje dalje prosleđuju svoje aplikacije sa servisima preduzeća. Ovaj tip alikacije je najzaslužniji za uspeh aplikacionih servera.
• Visoko upareni (klaster): odnose se na klaster mašina koje rade blisko zajedno, i izvršavaju deljeni proces paralelno. Zadatak je podeljen na delove koji su pravljeni pojedinačno i onda sastavljeni da naprave konačni rezultat.
• P2P: arhitektura gde ne postoji posebna mašina ili mašine koji prižaju uslugu ili upravljaju mrežnim resursima. Umesto toga, sve odgovornosti su jednako raspoređene na sve mašine, koje se zovu vršnjaci. Vršnjaci mogu služiti kao serveri i klijenti.
• Bazirano na prostoru: odnosi se na infrasturkturu koja pravi iluziju (virtuelizaciju) jednog adresnog prostora. Podaci se transparentno preliciraju po potrebama aplikacije.

Još jedan prost aspekat arhitekture raspoređenog izračunavanja je metod komunikacije i koordinacije posla između konkurentnih procesa. Kroz razne protokole slanja poruka procesi mogu komunicirati direktno jedan sa drugim tipično u gospodar-rob odnosu.

Litaratura

Knjige

• 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 izd.), 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 izd.), 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, Arhivirano iz originala 6. 8. 2009. g., Pristupljeno 15. 1. 2014 .

Članci

• 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, Arhivirano iz originala 16. 01. 2014. g., Pristupljeno 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 .

Veb stranice

• Godfrey, Bill (2002). „A primer on distributed computing”. Arhivirano iz originala 25. 02. 2010. g. Pristupljeno 15. 01. 2014. 
• Peter, Ian (2004). „Ian Peter's History of the Internet”. Pristupljeno 4. 8. 2009. 

Knjige

• 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. izd.). Springer. ISBN 978-3-642-15259-7. 
• Coulouris, George; et al. (2011). Distributed Systems: Concepts and Design (5th izd.). 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 

Artikli

• Keidar, Idit; Rajsbaum, Sergio, ur. (2000), „Distributed computing column”, [[ACM SIGACT News]], Arhivirano iz originala 16. 01. 2014. g., Pristupljeno 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. Arhivirano iz originala (PDF) 10. 8. 2010. g. Pristupljeno 15. 1. 2017. 

Izveštaji sa konferencije

• 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. str. 66—69. S2CID 15185219. doi:10.1109/BIMNICS.2007.4610083. 

Spoljašnje veze

• Distributed computing na sajtu Curlie
• Distributed computing journals na sajtu Curlie