Llogaritja e shpërndarë

Llogaritja e shpërndarë është një fushë e shkencës kompjuterike që studion sistemet e shpërndara, të definuara si sisteme kompjuterike, komponentët ndër-komunikues të të cilave janë të vendusura në kompjuterë të ndryshëm të lidhur në rrjet.

Komponentët e një sistemi të shpërndarë komunikojnë dhe koordinojnë veprimet e tyre duke i kaluar mesazhe njëri-tjetrit për të arritur  në një qëllim të përbashkët. Tre sfida të sistemeve të shpërndara janë: menagjimin paralel të komponentëve, tejkalimi i mungesës së një orë globale, dhe menaxhimi i dështimit të pavarur të komponentëve.Kur një komponent i një sistemi dështon, i gjithë sistemi nuk dështon.Shembuj të sistemeve të shpërndara variojnë nga sistemet e bazuara në SOA te mikroshërbimet, te lojërat masive online me shumë lojtarë dhe te aplikacionet peer-to-peer . Sistemet e shpërndara kushtojnë më shumë se arkitekturat monolitike, kryesisht për shkak të nevojave në rritje për pajisje shtesë, servera, porta hyrëse,murii i zjarrit(shtresë mbrojtëse nga virusët), nënrrjete të reja, preyantues, e kështu me radhë.Sistemet e shpërndara gjithashtu mund të vuajnë nga gabimet e informatikës së shpërndarë .Anasjelltas, një sistem i shpërndarë i projektuar mirë është më i shkallëzueshëm, më i qëndrueshëm, më i ndryshueshëm dhe më i përsosur se një aplikacion monolitik i vendosur në një makinë të vetme.Sipas Marc Brooker:"një sistem është i shkallëzueshëm në rangun ku kostoja marxhinale e ngarkesës shtesë të punës është pothuajse konstante." Teknologjitë pa server i përshtaten këtij përkufizimi, por duhet të merret në konsideratë kostoja totale e pronësisë, dhe jo vetëm kostoja e infrastrukturës.  

Një program kompjuterik që operon brenda një sistemi të shpërndarë quhet program i shpërndarë,dhe programimi i shpërndarë është procesi i shkrimit të programeve të tilla.Ekzistojnë shumë lloje implementimesh për mekanizmin e kalimit të mesazheve, duke përfshirë HTTP të pastër, lidhës të ngjashëm me RPC, dhe radhët e mesazheve .

Llogaritja e shpërndarë i referohet gjithashtu përdorimit të sistemeve të shpërndara për të zgjidhur problemet e llogaritjes. Në llogaritjen e shpërndarë, një problem ndahet në shumë detyra, secila prej të cilave zgjidhet nga një ose më shumë kompjuterë, të cilët komunikojnë me njëri-tjetrin nëpërmjet kalimeve të mesazheve., p. 291–292. , p. 5.

 Hyrje 
Fjala  i shpërndarë në termat e tillë si "sistem i shpërndarë", "programim i shpërndarë", dhe "algoritëm i shpërndarë" fillimisht i referohej rrjeteve kompjuterike ku kompjuterët individualë ishin të shpërndarë fizikisht brenda një zone gjeografike.Termat sot përdoren në një kuptim shumë më të gjerë, madje duke iu referuar proceseve autonome që funksionojnë në të njëjtin kompjuter fizik dhe bashkëveprojnë me njëri-tjetrin duke kaluar mesazhe., p. 291–292. , p. 5.

Nuk ka asnjë përkufizim të vetëm të një sistemi të shpërndarë,, p. 10.por përgjithësisht citohen dy veti të përbashkëta:

 Ekzistojnë disa entitete llogaritëse autonome (kompjuterë ose nyje),secila prej të cilave ka memorien e vet lokale.
 Entitetet komunikojnë me njëra-tjetrën duke kaluar mesazhe.  

Një sistem i shpërndarë mund të ketë një qëllim të përbashkët, siç është zgjidhja e një problemi të madh llogaritës;përdoruesi më pas e percepton koleksionin e procesorëve autonomë si një njësi. Nga ana tjetër, çdo kompjuter mund të ketë përdoruesin e vet me nevoja individuale, dhe qëllimi i sistemit të shpërndarë është të koordinojë përdorimin e burimeve të përbashkëta ose të ofrojë shërbime komunikimi për përdoruesit.

Veti të tjera tipike të sistemeve të shpërndara janë:

 Sistemi duhet të tolerojë dështimet në kompjuterët individualë.
 Struktura e sistemit (topologjia e rrjetit, vonesa e rrjetit, numri i kompjuterëve) nuk dihet paraprakisht.
 Sistemi mund të përbëhet nga lloje të ndryshme kompjuterësh dhe lidhjesh rrjeti.
 Sistemi mund të ndryshojë gjatë ekzekutimit të një programi të shpërndarë.  
 Çdo kompjuter ka një pamje të kufizuar dhe të paplotë të sistemit.
 Çdo kompjuter mund të dijë vetëm një pjesë të të dhënave hyrëse.  

 Modele 
Ja disa modele arkitekturore të zakonshme të përdorura për informatikën e shpërndarë:

 Modeli i ndërveprimit të Sagës
 Mikroshërbime
 Arkitekturë e drejtuar nga ngjarjet

 Ngjarjet kundër Mesazheve 
Në sistemet e shpërndara, ngjarjet përfaqësojnë një ndryshim fakti ose gjendjeje (p.sh., Porositja e Vendosur) dhe zakonisht transmetohen në mënyrë asinkrone te shumë konsumatorë, duke nxitur lidhje të lirshme dhe shkallëzueshmëri. Ndërsa ngjarjet në përgjithësi nuk presin një përgjigje të menjëhershme, mekanizmat e konfirmimit shpesh zbatohen në nivelin e infrastrukturës (p.sh., kompensimet e kryerjes Kafka, statuset e dorëzimit SNS) në vend që të jenë një pjesë e natyrshme e vetë modelit të ngjarjes.

Në të kundërt, mesazhet luajnë një rol më të gjerë, duke përfshirë komanda (p.sh., Procesi i Pagesës), ngjarje (p.sh., Pagesa u Procesua) dhe dokumente (p.sh., Ngarkesë etë dhënave). Si ngjarjet ashtu edhe mesazhet mund të mbështesin garanci të ndryshme dorëzimi, duke përfshirë të paktën një herë, më së shumti një herë, dhe saktësisht një herë, varësisht nga grupi i teknologjisë dhe zbatimi. Megjithatë, dorëzimi saktësisht një herë shpesh arrihet përmes mekanizmave të idempotencës në vend të semantikës së vërtetë saktësisht një herë në nivel infrastrukture.

Modelet e shpërndarjes si për ngjarjet ashtu edhe për mesazhet përfshijnë publikimin/abonimin (një-me-shumë) dhe pikë-me-pikë (një-me-një). Ndërsa kërkesa/përgjigja është teknikisht e mundur, ajo shoqërohet më shpesh me modelet e mesazheve sesa me sistemet e thjeshta të drejtuara nga ngjarjet. Ngjarjet shkëlqejnë në përhapjen e gjendjes dhe njoftimet e shkëputura, ndërsa mesazhet janë më të përshtatshme për ekzekutimin e komandave, orkestrimin e rrjedhës së punës, dhe koordinimin e qartë.

Arkitekturat moderne zakonisht i kombinojnë të dyja qasjet, duke shfrytëzuar ngjarjet për njoftime të shpërndara të ndryshimeve të gjendjes dhe mesazhet për ekzekutimin e komandave të synuara dhe rrjedhat e punës të strukturuara bazuar në kërkesat specifike të kohës, porosisë dhe dorëzimit.

 Informatika paralele dhe e shpërndarë 
qendër|parapamje|412x412px|(a), (b): Shembulli i një sistemi të  shpërndarë. (c): Shembulli i një sistemi paralel.
Sistemet e shpërndara janë grupacione kompjuterësh të rrjetëzuar që ndajnë një qëllim të përbashkët për punën e tyre. Termat            "llogaritje e njëkohshme", "llogaritje paralele" dhe "llogaritje e shpërndarë" kanë shumë mbivendosje dhe nuk ekziston ndonjë dallim i qartë midis tyre.I njëjti sistem mund të karakterizohet si "paralel" dhe "i shpërndarë"; procesorët në një sistem tipik të shpërndarë funksionojnë njëkohësisht paralelisht.Llogaritja paralele mund të shifet si një formë veçanërisht e lidhur ngushtë e llogaritjes së shpërndarë,dhe llogaritja e shpërndarë mund të shihet si një formë e lidhur lirshëm e llogaritjes paralele., p. 10.Megjithatë, është e mundur të klasifikohen përafërsisht sistemet e njëkohshme si "paralele" ose "të shpërndara" duke përdorur kriteret e mëposhtme:

 Në llogaritjen paralele, të gjithë procesorët mund të kenë qasje në një memorie të përbashkët për të shkëmbyer informacion midis procesorëve.
 Në informatikën e shpërndarë, çdo procesor ka memorien e vet private (memorie të shpërndarë). Informacioni shkëmbehet duke kaluar mesazhe midis procesorëve.

Figura në të djathtë ilustron ndryshimin midis sistemeve të shpërndara dhe paralele. Figura (a) është një pamje skematike e një sistemi tipik të shpërndarë; sistemi përfaqësohet si një topologji rrjeti në të cilën çdo nyje është një kompjuter dhe çdo linjë që lidh nyjet është një lidhje komunikimi. Figura (b) tregon të njëjtin sistem të shpërndarë në më shumë detaje: çdo kompjuter ka memorien e vet lokale dhe informacioni mund të shkëmbehet vetëm duke kaluar mesazhe nga një nyje në tjetrën duke përdorur lidhjet e komunikimit në dispozicion. Figura (c) tregon një sistem paralel në të cilin çdo procesor ka një qasje të drejtpërdrejtë në një memorie të përbashkët.

Situata ndërlikohet më tej nga përdorimet tradicionale të termave algoritëm paralel dhe i shpërndarë që nuk përputhen plotësisht me përkufizimet e mësipërme të sistemeve paralele dhe të shpërndara (shih më poshtë për një diskutim më të detajuar). Megjithatë, si rregull i përgjithshëm, llogaritja paralele me performancë të lartë në një multiprocesor me memorie të përbashkët përdor algoritme paralele, ndërsa koordinimi i një sistemi të shpërndarë në shkallë të gjerë përdor algoritme të shpërndara.1q

 Historia 
Përdorimi i proceseve të njëkohshme që komunikojnë përmes kalimit të mesazheve i ka rrënjët në arkitekturat e sistemeve operative të studiuara në vitet 1960.Sistemet e para të shpërndara të përhapura ishin rrjetet lokale si Etherneti, i cili u shpik në vitet 1970.

ARPANET, një nga paraardhësit e internetit, u prezantua në fund të viteve 1960, dhe email-i ARPANET u shpik në fillim të viteve 1970. Email-i u bë aplikacioni më i suksesshëm i ARPANET-it,dhe është ndoshta shembulli më i hershëm i një aplikacioni të shpërndarë në shkallë të gjerë. Përveç ARPANET-it (dhe pasardhësit të tij, internetit global), rrjete të tjera të hershme kompjuterike në mbarë botën përfshinin Usenet dhe FidoNet nga vitet 1980, të cilat të dyja u përdorën për të mbështetur sistemet e diskutimit të shpërndara. 

Studimi i informatikës së shpërndarë u bë degë më vete e shkencës kompjuterike në fund të viteve 1970 dhe fillim të viteve 1980. Konferenca e parë në këtë fushë, Simpoziumi mbi Parimet e Informatikës së Shpërndarë (PODC), daton që nga viti 1982, dhe homologu i tij Simpoziumi Ndërkombëtar mbi Informatikën e Shpërndarë (DISC) u mbajt për herë të parë në Ottawa në vitin 1985 si Seminari Ndërkombëtar mbi Algoritmet e Shpërndara në Grafe. 

 Arkitekturat e Kompjuterizimit të Shpërndarë 
Arkitektura të ndryshme hardueri dhe softueri përdoren për informatikën e shpërndarë. Në një nivel më të ulët, është e nevojshme të ndërlidhen shumë CPU me një lloj rrjeti, pavarësisht nëse ky rrjet është i shtypur në një qark apo i përbërë nga pajisje dhe kabllo të lidhura lirshëm. Në një nivel më të lartë, është e nevojshme të ndërlidhen proceset që funksionojnë në ato CPU me një lloj sistemi komunikimi.

Nëse këto CPU ndajnë burimet apo jo përcakton një dallim të parë midis tre llojeve të arkitekturës:

 Memorie e përbashkët
 Disk i shpërndarë
 Nuk shpërndan asgjë.

Programimi i shpërndarë zakonisht bie në njërën nga disa arkitektura themelore:klient-server, tre-shtresore, n- shtresore ose peer-to-peer(një me një); ose kategori: lidhje e lirshme ose lidhje e ngushtë.

 Klient-server:arkitektura ku klientët inteligjentë kontaktojnë serverin për të dhëna, pastaj i formatojnë dhe ua shfaqin përdoruesve. Të dhënat e dhëna te klienti i kthehen serverit kur ato përfaqësojnë një ndryshim të përhershëm.
 Tre-shtresore:arkitektura që e zhvendosin inteligjencën e klientit në një nivel të mesëm në mënyrë që të mund të përdoren klientë pa shtetësi. Kjo thjeshton vendosjen e aplikacioneve. Shumica e aplikacioneve web janë tre-shtresore.
 n -tier: arkitektura që i referohen zakonisht aplikacioneve web të cilat i përcilljnë më tej kërkesat e tyre në shërbime të tjera të ndërmarrjes. Ky lloj aplikacioni është më përgjegjës për suksesin e serverëve të aplikacioneve.
 Peer-to-peer:arkitektura ku nuk ka makina të veçanta që ofrojnë një shërbim ose menaxhojnë burimet e rrjetit.Vigna P, Casey MJ. The Age of Cryptocurrency: How Bitcoin and the Blockchain Are Challenging the Global Economic Order St. Martin's Press January 27, 2015   Në vend të kësaj, të gjitha përgjegjësitë ndahen në mënyrë uniforme midis të gjitha makinave, të njohura si kolegë. Kolegët(shpërndarësit) mund të shërbejnë si klientë dhe si serverë.Shembuj të kësaj arkitekture përfshijnë BitTorrent dhe rrjetin e bitcoinit.

Një aspekt tjetër themelor i arkitekturës së informatikës së shpërndarë është metoda e komunikimit dhe koordinimit të punës midis proceseve të njëkohshme. Përmes protokolleve të ndryshme të kalimit të mesazheve, proceset mund të komunikojnë drejtpërdrejt me njëri-tjetrin, zakonisht në një marrëdhënie kryesore/nën-procesore. Nga ana tjetër, një arkitekturë "e përqendruar në bazën e të dhënave" mund të mundësojë që informatika e shpërndarë të bëhet pa asnjë formë komunikimi të drejtpërdrejtë ndër-procesor, duke përdorur një bazë të dhënash të përbashkët.Arkitektura e përqendruar në bazën e të dhënave në veçanti ofron analiza të përpunimit relacional në një arkitekturë skematike që lejon transmetimin e mjedisit të drejtpërdrejtë. Kjo mundëson funksionet e informatikës së shpërndarë si brenda ashtu edhe përtej parametrave të një baze të dhënash të rrjetëzuar.  

 Arkitektura e Bazuar në Qeliza 
Arkitektura e bazuar në qeliza është një qasje e informatikës së shpërndarë në të cilën burimet llogaritëse janë të organizuara në njësi të pavarura të quajtura qeliza. Çdo qelizë vepron në mënyrë të pavarur, duke përpunuar kërkesat duke ruajtur shkallëzueshmërinë, izolimin e defekteve dhe disponueshmërinë.

Një qelizë zakonisht përbëhet nga shërbime ose komponentë të shumëfishtë aplikacioni dhe funksionon si një njësi autonome. Disa implementime replikojnë grupe të tëra shërbimesh nëpër qeliza të shumëfishta, ndërsa të tjera ndajnë ngarkesat e punës midis qelizave. Në modelet e replikuara, kërkesat mund të ridrejtohen në një qelizë operative nëse një tjetër përjeton një dështim. Ky dizajn ka për qëllim të rrisë qëndrueshmërinë e sistemit duke zvogëluar ndikimin e dështimeve të lokalizuara.

Disa implementime përdorin ndërprerës qarku brenda dhe midis qelizave. Brenda një qelize, ndërprerësit e qarkut mund të përdoren për të parandaluar dështimet kaskaduese midis shërbimeve, ndërsa ndërprerësit e qarkut midis qelizave mund të izolojnë qelizat që dështojnë dhe të ridrejtojnë trafikun tek ato që mbeten funksionale.

Arkitektura e bazuar në qeliza është adoptuar në disa sisteme të shpërndara në shkallë të gjerë, veçanërisht në mjediset me cloud-native dhe me disponueshmëri të lartë, ku izolimi i defekteve dhe redundanca janë konsiderata kryesore të projektimit. Zbatimi i saj ndryshon në varësi të kërkesave të sistemit, kufizimeve të infrastrukturës dhe objektivave operacionale.

 Aplikacionet 
Arsyet për përdorimin e sistemeve të shpërndara dhe informatikës së shpërndarë mund të përfshijnë:

 Vetë natyra e një aplikacioni mund të kërkojë përdorimin e një rrjeti komunikimi që lidh disa kompjuterë: për shembull, të dhënat e prodhuara në një vendndodhje fizike dhe të kërkuara në një vendndodhje tjetër.
 Ka shumë raste në të cilat përdorimi i një kompjuteri të vetëm do të ishte i mundur në parim, por përdorimi i një sistemi të shpërndarë është i dobishëm për arsye praktike. Për shembull:
 Mund të lejojë ruajtje dhe memorie shumë më të madhe, llogaritje më të shpejtë dhe gjerësi bande më të lartë sesa një makinë e vetme.
 Mund të ofrojë më shumë besueshmëri sesa një sistem jo i shpërndarë, pasi nuk ka një pikë të vetme dështimi. Për më tepër, një sistem i shpërndarë mund të jetë më i lehtë për t'u zgjeruar dhe menaxhuar sesa një sistem monolit me një procesor.
 Mund të jetë më ekonomike nga ana e kostos të arrihet niveli i dëshiruar i performancës duke përdorur një grumbull prej disa kompjuterësh të nivelit të ulët, në krahasim me një kompjuter të vetëm të nivelit të lartë.

 Shembuj 
Shembuj të sistemeve të shpërndara dhe aplikimeve të informatikës së shpërndarë përfshijnë sa vijon: 

 rrjetet e telekomunikacionit:
 rrjetet telefonike dhe rrjetet celulare,
 rrjetet kompjuterike, të tilla si interneti,
 rrjetet e sensorëve pa tel,
 algoritmet e rrugëzimit.
 aplikacionet e rrjetit:
 World Wide Web dhe rrjetet peer-to-peer,
 lojëra masive shumëlojtarëshe online dhe komunitete të realitetit virtual,
 bazat e të dhënave të shpërndara dhe sistemet e menaxhimit të bazave të të dhënave të shpërndara,
 sistemet e skedarëve të rrjetit,
 memoria e shpërndarë,siç janë buffer-at e shpërthimit,
 sisteme të përpunimit të informacionit të shpërndarë, siç janë sistemet bankare dhe sistemet e rezervimit të linjave ajrore;
 kontrolli i procesit në kohë reale:
 sistemet e kontrollit të avionëve,
 [. /Industrial_control_systemhttps://en.wikipedia.org/wiki/Industrial_control_system sistemet e kontrollit industrial].
 llogaritje paralele:
 informatikë shkencore, duke përfshirë informatikën në grupe, informatikën në rrjet, informatikën në cloud,dhe projekte të ndryshme vullnetare informatike,
 Renderimi i shpërndarë në grafikën kompjuterike.
 peer-to-peer

Sipas Manifestit Reaktiv, sistemet e shpërndara reaktive janë të përgjegjshme, elastike, elastike dhe të orientuara drejt mesazheve. Rrjedhimisht, sistemet Reaktive janë më fleksibile, të lidhura lirshëm dhe të shkallëzueshme. Për t'i bërë sistemet tuaja reaktive, ju këshillohet të zbatoni Parimet Reaktive. Parimet Reaktive janë një sërë parimesh dhe modelesh që të ndihmojnë për ta bërë aplikacionin tuaj vendas te resë(cloud), si dhe aplikacionet edge native më reaktive.

 Themelet teorike 

 Modelet 
Shumë detyra që do të donim të automatizonim duke përdorur një kompjuter janë të tipit pyetje-përgjigje: ne do të donim të bënim një pyetje dhe kompjuteri duhet të jepte një përgjigje. Në shkencën teorike të kompjuterave, detyra të tilla quhen probleme llogaritëse . Formalisht, një problem llogaritës përbëhet nga raste së bashku me një zgjidhje për secilin rast. Rastet janë pyetje që mund të bëjmë, dhe zgjidhjet janë përgjigje të dëshiruara për këto pyetje.

Shkenca teorike e kompjuterave kërkon të kuptojë se cilat probleme llogaritëse mund të zgjidhen duke përdorur një kompjuter (teoria e llogaritshmërisë) dhe sa efikase (teoria e kompleksitetit llogaritës). Tradicionalisht, thuhet se një problem mund të zgjidhet duke përdorur një kompjuter nëse mund të hartojmë një algoritëm që prodhon një zgjidhje të saktë për çdo instancë të caktuar. Një algoritëm i tillë mund të zbatohet si një program kompjuterik që funksionon në një kompjuter me qëllim të përgjithshëm: programi lexon një instancë problemi nga hyrja, kryen disa llogaritje dhe prodhon zgjidhjen si dalje. Formalizmat si makinat me akses të rastësishëm ose makinat universale Turing mund të përdoren si modele abstrakte të një kompjuteri sekuencial me qëllim të përgjithshëm që ekzekuton një algoritëm të tillë.

Fusha e informatikës së njëkohshme dhe të shpërndarë studion pyetje të ngjashme në rastin e kompjuterëve të shumtë ose të një kompjuteri që ekzekuton një rrjet procesesh bashkëvepruese: cilat probleme llogaritëse mund të zgjidhen në një rrjet të tillë dhe me sa efikasitet? Megjithatë, nuk është aspak e qartë se çfarë nënkuptohet me "zgjidhjen e një problemi" në rastin e një sistemi të njëkohshëm ose të shpërndarë: për shembull, cila është detyra e projektuesit të algoritmit dhe cili është ekuivalenti i njëkohshëm ose i shpërndarë i një kompjuteri sekuencial me qëllim të përgjithshëm? [ nevojitet citim ]

Diskutimi më poshtë përqendrohet në rastin e shumë kompjuterëve, megjithëse shumë nga problemet janë të njëjta për proceset që funksionojnë njëkohësisht në një kompjuter të vetëm.

Zakonisht përdoren tre këndvështrime:

 Algoritmet paralele në modelin e memories së përbashkët

 Të gjithë procesorët kanë qasje në një memorie të përbashkët. Projektuesi i algoritmit zgjedh programin që ekzekutohet nga secili procesor.
 Një model teorik janë makinat paralele me akses të rastësishëm (PRAM) që përdoren. Megjithatë, modeli klasik PRAM supozon akses sinkron në memorien e përbashkët.
 Programet me memorie të përbashkët mund të zgjerohen në sisteme të shpërndara nëse sistemi operativ themelor përfshin komunikimin midis nyjeve dhe virtualisht unifikon memorien në të gjitha sistemet individuale.
 Një model që është më afër sjelljes së makinave me shumë procesorë në botën reale dhe merr në konsideratë përdorimin e udhëzimeve të makinës, siç është Krahaso-dhe-shkëmbej (CAS), është ai i memories së përbashkët asinkrone. Ekziston një numër i madh punimesh mbi këtë model, një përmbledhje e të cilave mund të gjendet në literaturë.

 Algoritmet paralele në modelin e kalimit të mesazheve

 Dizajneri i algoritmit zgjedh strukturën e rrjetit, si dhe programin që ekzekutohet nga secili kompjuter.
 Përdoren modele të tilla si qarqet booleane dhe rrjetet e renditjes . Një qark boolean mund të shihet si një rrjet kompjuterik: çdo portë është një kompjuter që ekzekuton një program kompjuterik jashtëzakonisht të thjeshtë. Në mënyrë të ngjashme, një rrjet renditjeje mund të shihet si një rrjet kompjuterik: çdo krahasues është një kompjuter.

 Algoritmet e shpërndara

 Dizajnuesi i algoritmit zgjedh vetëm programin kompjuterik. Të gjithë kompjuterët ekzekutojnë të njëjtin program. Sistemi duhet të funksionojë saktë pavarësisht nga struktura e rrjetit.
 Një model i përdorur zakonisht është një graf me një makinë me gjendje të fundme për nyje.

Në rastin e algoritmeve të shpërndara, problemet llogaritëse zakonisht lidhen me grafet. Shpesh grafiku që përshkruan strukturën e rrjetit kompjuterik është instanca e problemit. Kjo ilustrohet në shembullin e mëposhtëm.

 Një shembull 
Merrni parasysh problemin llogaritës të gjetjes së një ngjyrosjeje të një grafi të caktuar G. Fusha të ndryshme mund të ndjekin qasjet e mëposhtme:

 Algoritme të centralizuara

 Grafi G kodohet si një varg, dhe vargu i jepet si të dhëna hyrëse një kompjuteri. Programi kompjuterik gjen një ngjyrosje të grafikut, e kodon ngjyrosjen si një varg, dhe jep rezultatin në dalje.

 Algoritme paralele

 Përsëri, grafi G është koduar si një varg. Megjithatë, shumë kompjuterë mund të qasen në të njëjtin varg paralelisht. Çdo kompjuter mund të përqendrohet në një pjesë të grafit dhe të prodhojë një ngjyrosje për atë pjesë.
 Fokusi kryesor është në llogaritjen me performancë të lartë që shfrytëzon fuqinë përpunuese të shumë kompjuterëve paralelisht.

 Algoritmet e shpërndara

 Grafi G është struktura e rrjetit kompjuterik. Ekziston një kompjuter për secilën nyje të G dhe një lidhje komunikimi për secilën skaj të G. Fillimisht, çdo kompjuter di vetëm për fqinjët e tij të menjëhershëm në grafin G ; kompjuterët duhet të shkëmbejnë mesazhe me njëri-tjetrin për të zbuluar më shumë rreth strukturës së G. Çdo kompjuter duhet të prodhojë ngjyrën e vet si rezultat.
 Fokusi kryesor është në koordinimin e funksionimit të një sistemi të shpërndarë arbitrar.

Ndërsa fusha e algoritmeve paralele ka një fokus të ndryshëm nga fusha e algoritmeve të shpërndara, ka shumë ndërveprim midis dy fushave. Për shembull, algoritmi Cole-Vishkin për ngjyrosjen e grafikëve  u paraqit fillimisht si një algoritëm paralel, por e njëjta teknikë mund të përdoret edhe drejtpërdrejt si një algoritëm i shpërndarë.

Për më tepër, një algoritëm paralel mund të zbatohet ose në një sistem paralel (duke përdorur memorie të përbashkët) ose në një sistem të shpërndarë (duke përdorur kalimin e mesazheve). Kufiri tradicional midis algoritmeve paralele dhe të shpërndara (zgjidhni një rrjet të përshtatshëm kundrejt ekzekutimit në çdo rrjet të caktuar) nuk shtrihet në të njëjtin vend si kufiri midis sistemeve paralele dhe të shpërndara (memorie e përbashkët kundër kalimit të mesazheve).

 Masat e kompleksitetit 
Në algoritmet paralele, një burim tjetër përveç kohës dhe hapësirës është numri i kompjuterëve. Në të vërtetë, shpesh ekziston një kompromis midis kohës së ekzekutimit dhe numrit të kompjuterëve: problemi mund të zgjidhet më shpejt nëse ka më shumë kompjuterë që punojnë paralelisht (shih përshpejtimin). Nëse një problem vendimmarrjeje mund të zgjidhet në kohë polilogaritmike duke përdorur një numër polinomial procesorësh, atëherë problemi thuhet se është në klasën NC . Klasa NC mund të përcaktohet po aq mirë duke përdorur formalizmin PRAM ose qarqet booleane – makinat PRAM mund të simulojnë qarqet booleane në mënyrë efikase dhe anasjelltas.

Në analizën e algoritmeve të shpërndara, zakonisht i kushtohet më shumë vëmendje operacioneve të komunikimit sesa hapave llogaritëse. Ndoshta modeli më i thjeshtë i llogaritjes së shpërndarë është një sistem sinkron ku të gjitha nyjet funksionojnë në një mënyrë të barabartë. Ky model njihet zakonisht si modeli LOKAL. Gjatë çdo raundi komunikimi, të gjitha nyjet janë në paralel (1)  marrin mesazhet e fundit nga fqinjët e tyre, (2)  kryej llogaritje lokale arbitrare, dhe (3)  dërgojnë mesazhe të reja te fqinjët e tyre. Në sisteme të tilla, një masë qendrore e kompleksitetit është numri i raundeve të komunikimit sinkron të kërkuara për të përfunduar detyrën.

Kjo masë e kompleksitetit është e lidhur ngushtë me diametri n e rrjetit. Le të jetë D diametri i rrjetit. Nga njëra anë, çdo problem i llogaritshëm mund të zgjidhet në mënyrë të thjeshtë në një sistem të shpërndarë sinkron në afërsisht raunde komunikimi 2D: thjesht mblidhni të gjithë informacionin në një vendndodhje (raunde D), zgjidhni problemin dhe informoni secilën nyje rreth zgjidhjes (raunde D).

Nga ana tjetër, nëse koha e ekzekutimit të algoritmit është shumë më e vogël se D raundet e komunikimit, atëherë nyjet në rrjet duhet të prodhojnë rezultatin e tyre pa pasur mundësinë të marrin informacion në lidhje me pjesët e largëta të rrjetit. Me fjalë të tjera, nyjet duhet të marrin vendime globalisht të qëndrueshme bazuar në informacionin që është i disponueshëm në lagjen e tyre lokale D. Shumë algoritme të shpërndara njihen me kohë ekzekutimi shumë më të vogël se D raundet, dhe të kuptuarit se cilat probleme mund të zgjidhen nga algoritme të tilla është një nga pyetjet qendrore kërkimore të fushës. Zakonisht një algoritëm që zgjidh një problem në kohë polilogaritmike në madhësinë e rrjetit konsiderohet efikas në këtë model.

Një tjetër masë e përdorur zakonisht është numri total i bitëve të transmetuar në rrjet (kompleksiteti i komunikimit ).  Karakteristikat e këtij koncepti zakonisht kapen me modelin CONGEST(B), i cili përkufizohet në mënyrë të ngjashme si modeli LOCAL, por ku mesazhet e vetme mund të përmbajnë vetëm bite B.

 Probleme të tjera 
Problemet tradicionale llogaritëse marrin perspektivën ku përdoruesi bën një pyetje, një kompjuter (ose një sistem i shpërndarë) e përpunon pyetjen, pastaj prodhon një përgjigje dhe ndalet. Megjithatë, ka edhe probleme ku sistemi kërkohet të mos ndalet, duke përfshirë problemin e filozofëve të ngrënies dhe probleme të tjera të ngjashme të përjashtimit të ndërsjellë . Në këto probleme, sistemi i shpërndarë supozohet të koordinojë vazhdimisht përdorimin e burimeve të përbashkëta në mënyrë që të mos ndodhin konflikte ose bllokime .

Ekzistojnë gjithashtu sfida themelore që janë unike për informatikën e shpërndarë, për shembull ato që lidhen me tolerancën ndaj defekteve.Shembuj të problemeve të lidhura përfshijnë problemet e konsensusit, tolerancën Bizantine ndaj defekteve, dhe vetë-stabilizimin .

Shumë kërkime janë përqendruar gjithashtu në kuptimin e natyrës asinkrone të sistemeve të shpërndara:

 Sinkronizuesit mund të përdoren për të ekzekutuar algoritme sinkrone në sisteme asinkrone.
 Orët logjike ofrojnë një renditje shkakësore të ngjarjeve të ndodhura para se të ndodhin.  
 Algoritmet e sinkronizimit të orës ofrojnë pulla kohore fizike globalisht të qëndrueshme.  

Vini re se në sistemet e shpërndara, latenca duhet të matet deri në "percentilin e 99-të" sepse "mesatarja" dhe "mesatarja" mund të jenë mashtruese.

 Zgjedhjet 
Zgjedhja e koordinatorit (ose zgjedhja e udhëheqësit) është procesi i përcaktimit të një procesi të vetëm si organizator i një detyre të shpërndarë midis disa kompjuterëve (nyjeve). Përpara se të fillojë detyra, të gjitha nyjet e rrjetit ose nuk janë në dijeni se cila nyje do të shërbejë si "koordinator" (ose udhëheqës) i detyrës, ose nuk janë në gjendje të komunikojnë me koordinatorin aktual. Megjithatë, pasi të jetë ekzekutuar një algoritëm i zgjedhjes së koordinatorit, çdo nyje në të gjithë rrjetin njeh një nyje të veçantë dhe unike si koordinatorin e detyrës. 

Nyjet e rrjetit komunikojnë midis tyre për të vendosur se cila prej tyre do të hyjë në gjendjen "koordinator". Për këtë, ato kanë nevojë për një metodë për të thyer simetrinë midis tyre. Për shembull, nëse secila nyje ka identitete unike dhe të krahasueshme, atëherë nyjet mund të krahasojnë identitetet e tyre dhe të vendosin që nyja me identitetin më të lartë është koordinatori. 

Përkufizimi i këtij problemi shpesh i atribuohet LeLann, i cili e formalizoi atë si një metodë për të krijuar një token të ri në një rrjet token ring në të cilin tokeni është humbur.

Algoritmet e zgjedhjes së koordinatorëve janë projektuar të jenë ekonomike në aspektin e bajteve totale të transmetuara dhe kohës. Algoritmi i sugjeruar nga Gallager, Humblet dhe Spira  për grafet e përgjithshme të padrejtuara ka pasur një ndikim të fortë në projektimin e algoritmeve të shpërndara në përgjithësi dhe fitoi Çmimin Dijkstra për një punim me ndikim në informatikën e shpërndarë.

Shumë algoritme të tjera u sugjeruan për lloje të ndryshme të grafeve të rrjetit, siç janë unazat e padrejtuara, unazat unidireksionale, grafet e plota, rrjetat, grafet e drejtuara të Eulerit dhe të tjera. Një metodë e përgjithshme që shkëput çështjen e familjes së grafeve nga projektimi i algoritmit të zgjedhjes së koordinatorit u sugjerua nga Korach, Kutten dhe Moran.

Për të kryer koordinimin, sistemet e shpërndara përdorin konceptin e koordinatorëve. Problemi i zgjedhjes së koordinatorit është të zgjidhet një proces nga një grup procesesh në procesorë të ndryshëm në një sistem të shpërndarë për të vepruar si koordinator qendror. Ekzistojnë disa algoritme të zgjedhjes së koordinatorit qendror.

 Vetitë e sistemeve të shpërndara 
Deri më tani, fokusi ka qenë në hartimin e një sistemi të shpërndarë që zgjidh një problem të caktuar. Një problem plotësues kërkimor është studimi i vetive të një sistemi të shpërndarë të caktuar.

Problemi i ndalimit është një shembull analog nga fusha e llogaritjes së centralizuar: na është dhënë një program kompjuterik dhe detyra është të vendosim nëse ai ndalet apo funksionon përgjithmonë. Problemi i ndalimit është i pazgjidhshëm në rastin e përgjithshëm, dhe natyrisht të kuptuarit e sjelljes së një rrjeti kompjuterik është të paktën po aq e vështirë sa të kuptuarit e sjelljes së një kompjuteri.

Megjithatë, ka shumë raste të veçanta interesante që janë të zgjidhshme. Në veçanti, është e mundur të arsyetohet rreth sjelljes së një rrjeti makinash me gjendje të fundme. Një shembull është të tregohet nëse një rrjet i caktuar makinash me gjendje të fundme bashkëvepruese (asinkrone dhe jo-deterministe) mund të arrijë në një bllokim. Ky problem është i plotë sipas PSPACE, d.m.th., është i vendoshëm, por nuk ka gjasa që të ketë një algoritëm efikas (të centralizuar, paralel ose të shpërndarë) që zgjidh problemin në rastin e rrjeteve të mëdha.

 Shënime 

 Libra
 Andrews, Gregory R. (2000), Bazat e Programimit Shumëfijesh, Paralel dhe të Shpërndarë, Addison–Wesley, ISBN 978-0-201-35752-3.
 Arora, Sanjeev; Barak, Boaz (2009), Kompleksiteti Kompjuterik – Një Qasje Moderne, Kembrixh, ISBN 978-0-521-42426-4.
 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990), Hyrje në Algoritme (botimi i 1-rë), Shtëpia Botuese MIT, Kodi Bib:1990ita..libër.....C, ISBN 978-0-262-03141-7.
 Dolev, Shlomi (2000), Vetë-Stabilizimi, Shtëpia Botuese MIT, ISBN 978-0-262-04178-2.
 Elmasri, Ramez; Navathe, Shamkant B. (2000), Bazat e Sistemeve të Bazës së të Dhënave (botimi i 3-të), Addison–Wesley, ISBN 978-0-201-54263-9.
 Ghosh, Sukumar (2007), Sistemet e Shpërndara – Një Qasje Algoritmike, Chapman & Hall/CRC, ISBN 978-1-58488-564-1.
 Lynch, Nancy A. (1996), Algoritmet e Shpërndara, Morgan Kaufmann, ISBN 978-1-55860-348-6.
 Herlihy, Maurice P.; Shavit, Nir N. (2008), Arti i Programimit me Shumëprocesorë, Morgan Kaufmann, ISBN 978-0-12-370591-4.
 Papadimitriou, Christos H. (1994), Kompleksiteti Kompjuterik, Addison–Wesley, ISBN 978-0-201-53082-7.
 Peleg, David (2000), Informatika e Shpërndarë: Një Qasje e Ndjeshme ndaj Vendndodhjes, SIAM, ISBN 978-0-89871-464-7, arkivuar nga origjinali më 2009-08-06, marrë më 2009-07-16.

 Referime 

Artikuj
 Cole, Richard; Vishkin, Uzi (1986), "Hedhja e monedhës deterministe me aplikime për renditjen optimale paralele të listave", Informacion dhe Kontroll, 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7.
 Keidar, Idit (2008), "Kolona 32 e informatikës së shpërndarë – Viti në përmbledhje", ACM SIGACT News, 39 (4): 53–54, CiteSeerX 10.1.1.116.1285, doi:10.1145/1466390.1466402, S2CID 7607391, arkivuar nga origjinali më 16-01-2014, marrë më 20-08-2009.
 Linial, Nathan (1992), "Lokaliteti në algoritmet e grafeve të shpërndarë", SIAM Journal on Computing, 21 (1): 193–201, CiteSeerX 10.1.1.471.6378, doi:10.1137/0221015.
 Naor, Moni; Stockmeyer, Larry (1995), "Çfarë mund të llogaritet në nivel lokal?" (PDF), SIAM Journal on Computing, 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669, doi:10.1137/S0097539793254571, arkivuar (PDF) nga origjinali më 2013-01-08.
 Faqet e internetit
 Godfrey, Bill (2002). "Një hyrje në informatikën e shpërndarë". Arkivuar nga origjinali më 2021-05-13. Marrë më 2021-05-13. Peter, Ian (2004). "Historia e internetit nga Ian Peter". Arkivuar nga origjinali më 2010-01-20. Marrë më 2009-08-04.

 Lexime të mëtejshme 
Libra

 Attiya, Hagit dhe Jennifer Welch (2004), Informatika e Shpërndarë: Bazat, Simulimet dhe Temat e Avancuara, Wiley-Interscience ISBN 0-471-45324-2.
 Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Hyrje në Programimin e Shpërndarë të Besueshëm dhe të Sigurt (botimi i 2-të), Springer, Bibcode:2011itra.book.....C, ISBN 978-3-642-15259-7
 Coulouris, George; et al. (2011), Sistemet e Shpërndara: Konceptet dhe Dizajni (Botimi i 5-të), Addison-Wesley ISBN 0-132-14301-1.
 Faber, Jim (1998), Java Distributed Computing, O'Reilly, arkivuar nga origjinali më 24-08-2010, marrë më 29-09-2010: Java Distributed Computing nga Jim Faber, 1998 Arkivuar më 24-08-2010 te Wayback Machine
 Garg, Vijay K. (2002), Elementet e Distributed Computing, Wiley-IEEE Press ISBN 0-471-03600-5.
 Tel, Gerard (1994), Hyrje në Algoritmet e Shpërndara, Cambridge University Press
 Chandy, Mani; et al. (1988), Dizajni i Programit Paralel, Addison-Wesley ISBN 0201058669
 Dusseau, Remzi H.; Dusseau, Andrea (2016). Sistemet Operative: Tre Pjesë të Lehta, Kapitulli 48 Sistemet e Shpërndara (PDF). Arkivuar nga origjinali (PDF) më 31 gusht 2021. Marrë më 8 tetor 2021.

Artikuj

 Keidar, Idit; Rajsbaum, Sergio, red. (2000–2009), "Kolona e informatikës së shpërndarë", ACM SIGACT News, arkivuar nga origjinali më 16-01-2014, marrë më 16-08-2009.
 Birrell, A. D.; Levin, R.; Schroeder, M. D.; Needham, R. M. (Prill 1982). "Grapevine: Një ushtrim në informatikën e shpërndarë" (PDF). Communications of the ACM. 25 (4): 260–274. doi:10.1145/358468.358487. S2CID 16066616. Arkivuar (PDF) nga origjinali më 30-07-2016.

Punime Konference

 Rodriguez, Carlos; Villagra, Marcos; Baran, Benjamin (2007). "Algoritme asinkrone të ekipit për kënaqshmërinë booleane". Modelet e 2-ta të frymëzuara nga biologjia të rrjetit, informacionit dhe sistemeve kompjuterike 2007. f. 66–69. doi:10.1109/BIMNICS.2007.4610083. S2CID 15185219.

Kategoria:Faqe me adresa nga Wayback Machine që përdorin stampën e arkivës së rrjetit
Kategoria:Llogaritje e shpërndarë
Kategoria:Llogaritje (kompjuterike)