Introducere…5 [601373]

4
Cuprins
Introducere………………………………………………………………………………………………..5
Capitolul I – Descrierea sistemului de calcul distribuit……………………………………8
I.1 Fundamente teoretice……………………………………………………………………8
I.2 Arhitecturi posibile……………………………………………………………………..12
I.3 Descrierea arhitecturii aleasă……………………………………………………….14
I.4 Implementarea sistemului de calcul distribuit………………………………..17
I.5 Concluzii………………………………………………………………………………….25
Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri……………….27
II.1 Modelarea corespunzătoare Modulului de Conectare…………………….27
II.2 Modelarea corespunzătoare Modulului de Prelucrare a Datelor………28
II.3 Modelarea corespunzătoare Modulului Căutare……………………………30
II.4 Concluzii…………………………………………………………………………………32
Capitolul III – Particularizarea sistemului-CLEFIP 2010……………………………….34
III.1 CLEF-IP 2010…………………………………………………………………………34
III.2 Lucene .Net…………………………………………………………………………….36
III.3 Adaptarea Sistemului……………………………………………………………….37
III.4 Concluzii………………………………………………………………………………..39
Concluzii și Posibilități de dezvoltare………………………………………………………….40
Contribuții……………………………………………………………………………………………….43
Bibliografie……………………………………………………………………………………………..44

Introducere 5
Introducere
Dintotdeauna o problem ă extrem de dificilă în domeniul informaticii a fost procesarea cantitaților
mari de informație. Rezolvat ă în anii de pionierat al informatiici de sistemele de tip mainframe
care erau capabile sa proceseze cantitați mari de informație pentru acea vreme, problema a
reapărut odată cu dispariția mainframe-urilor în favoarea calculatoarelor de tip PC. Sfidând
progresul tehnologic care a dezvoltat deosebit de mult calculatoarele personale, informaticienii
continuă să scrie programe ce necesit ă din ce în ce mai mult ă memorie și care manipuleaz ă uneori
cantitați uriașe de documente text, fișiere ori fluxuri de date.
Astfel a apărut nevoia dezvoltarii sistemelor distribuite. Un sistem distribuit constă din mai multe
calculatorare autonome care comunică între ele în cadrul unei rețele de calculatoare.
Calculatoarele interacționează unul cu celălalt cu scopul de a realiza un obiectiv comun. Astfel o
problemă poate fi împărțită în mai multe sarcini, ce vor fi rezolvate, fiecare în parte, de către un
calculator.
La nivel individual, necesitatea dezvoltării unui sistem distribuit a apărut în cadrul proiectarii
alături de grupa 5A1 a sistemului ce a reprezentat Universitatea „Al. I. Cuza” în cadrul
concursului CLEF-IP 20092. Acesta a trebuit să proceseze o cantitate foarte mare3 de documente
text. Astfel timpul consumat de operațiile desfașurate pe aceste documente, efectuate pe un sigur
calculator, era deosebit de mare, producând probleme de sincronizare a modulelor de lucru, dar și
de actualizare a rezultatelor.
Pentru a rezolva, aceste probleme, colecția de documente a fost împărțită în 3 parți, care au fost
procesate cu ajutorul a 3 calculatoare. Problemele au fost parțial rezolvate, însă existența unui
sistem distribuit, care sa gestioneze diferitele operații efectuate pe documentele de lucru, ar fi
1Proiect desfașurat în timpul anului universitar 2008-2009, în cadrul obiectului „Ingineria programării”, sub
îndrumarea Dm Asist. Dr. Adrian Iftene
2http://www.ir-facility.org/research/evaluation/clef-ip-09/overview
3Aproximativ 75 Gb

Introducere 6
eliminat integral atât prelucrarea manuală cât și problemele existente.
Această lucrare își propune să descrie un sistem de procesare distribuit, care să aibă o structură
generalizată, capabilă de particularizare, cu scopul de a fi folosit în diverse situații și probleme
ulterioare de prelucrare a colecțiilor mari de documente.
În final, sistemul succint descris mai sus, va fi particularizat, drept exemplu fiind aleasă problema
propusă de competiția CLEF-IP 20104. Aceasta competiție a fost lansat ă de Information Retrieval
Facility & Matrixware în anul 2009 și continuat ă anul acesta, propunându-și investigarea
tehnicilor de extragere a informațiilor din domeniul proprietații intelectuale.
Am ales această problemă deoarece se încadreaz ă într-un domeniu nou de interes internațional și
pentru că reprezintă o provocare nouă și interesantă. Acordarea noilor brevete a devenit o misiune
dificilă având în vedere atât cantitatea mare de invenții patentate în trecut cât și multitudinea de
noi cereri de înregistrare a brevetelor survenit ă odata cu cautarea tehnologiilor alternative care ar
putea rezolva problemele aparute în ultimele decenii la nivel mondial. Astfel aceasta misiune ar
putea fi ușurată prin utilizarea sistemelor informatice, care s ă păstreze, ordoneze mult mai ușor
informațiile și să coordoneze mult mai eficient resursele organizațiilor responsible de patentarea
noilor invenții.
Motivația alegerie acestei teme const ă și în participarea la cunoscuta campanie CLEF5 (Cross
Language Evaluation Forum) desf ășurată în ultimii zece ani. CLEF 2010 va acoperi o gam ă largă
din domeniile de evaluare a accesului multilingv și multimodal al informației.
Lucrarea este structurată după cum urmează:
Capitolul I – Descrierea Sistemului de procesare distribuit – Descrie în prima sa parte
fundamentele teoretice ce stau la baza sistemelor și algoritmilor distribuiți. Este
prezentată apoi motivația alegerii unui sistem distribuit, această motivație fiind urmată de
prezentarea arhitecturilor posibile din cadrul calculului distribuit. Arhitectura aleasă este
4http://www.ir-facility.org/research/evaluation/clef-ip-10/overview
5http://www.clef-campaign.org/

Introducere 7
descrisă fiind puse în evidență adaptările și modificarile aduse. În final este descrisă
implementarea sistemului distribuit, implementarea efectuată în limbajul C#
Capitolul II – Modelarea sistemului prin intermediul Rețelelor Petri – Prezintă și descrie
modelarea sistemului ilustrat în capitolul anterior. Modelarea este efectuată pe module,
fiind scoase în evidență atât caracteristicile proprii cât și legaturile dintre ele. Sunt
prezentate deasemenea concluziile referitoare la simularea prin intermediul acestui model,
fiind astfel ilustrate proprietățile sistemului.
Capitolul III – Particularizarea sistemului-CLEFIP 2010 – Prezintă modalitatea în care
sistemul poate fi particularizat pentru o anumită sarcină de lucru. Drept exemplu este
aleasă sarcina propusă de CLEF-IP 2010 și anume căutarea „Prior Art”
Concluzii și posibilități de dezvoltare

Capitolul I – Descrierea sistemului de procesare distribuit 8
Capitolul I – Descrierea Sistemului de Procesare Distribuit
I.1 Fundamente Teoretice
Multe procese pe care am dori să le automatizăm, prin folosirea unui calculator, sunt de tipul
întrebare-răspuns: am dori să punem o întrebare iar calculatorul să fie capabil să producă un
răspuns. În teoria informaticii, astfel de probleme sunt numite probleme computaționale. Formal,
o problema computațională este alcătuită din mai multe instanțe, fiecare dintre acestea având o
soluție. Instanțele sunt întrebări pe care le putem răspunde, și soluțiile sunt răspunsurile dorite la
aceste întrebări.
Informatica teoretică caută să înteleagă ce probleme computaționale pot fi rezolvate prin
utilizarea unui calculator (teoria computațională) și cât de eficient (teoria complexității
computaționale) (Goldreich, 2008). Tradițional, se spune că o problemă poate fi rezolvată dacă
suntem capabili să proiectăm un algoritm care produce o soluție corectă pentru o anumită instanță
dată. Un astfel de algoritm poate fi implementat sub forma unui program, într-un anumit limbaj,
și rulat pe un calculator cu scop general.
Domeniul calculului concurent și distribuit studiază întrebări similare efectuate fie în cazul mai
multor calculatoare, fie în cazul unui calculator ce execută mai multe procese ce interacționează
între ele. Întrebarea firească ce apare se leagă de natura problemelor ce pot fi rezolvate în astfel
de sisteme dar și de eficiența rezolvărilor. Cu toate acestea, nu este deloc clar ce se înțelege prin
„rezolvarea unei probleme” în cazul unui sistem concurent sau distribuit. De exemplu care este
scopul celui care proiectează algoritmul sau care este echivalentul concurent și/sau distribuit
pentru un calculator secvențial cu scop general (Filman și Friedman, 1984)?
În ceea ce privește modelele existente în cazul sistemelor ce folosesc mai multe calculatoare (deși
multe dintre aceste probleme sunt similare și în cazul proceselor concurente rulate pe același
calculator) , există trei puncte de vedere frecvent utilizate (Taubenfeld și Gadi, 2006):

Capitolul I – Descrierea sistemului de procesare distribuit 9
Modelul algoritmilor paraleli cu memorie partajată
•Toate calculatoarele au acces la o memorie partajată. Proiectantul algoritmului alege
programul executat pe fiecare calculator (Figura 1).
•Un model care se apropie de comportamentul mașinilor reale cu multiprocesoare și ia
în calcul folosirea instrucțiunilor mașină de genul Compare-and-Swap6 (Herlihy și
Shavit, 2008) este memoria partajată asincronă.
Modelul algoritmilor paraleli cu transmitere de mesaj
•Proiectantul algoritmului alege atât structura rețelei, cât și programul executat pe
fiecare calculator în parte.
•Sunt folosite modele ca circuitele booleene sau rețelele de sortare ( Cormen et al,
1990). Un circuit boolean poate fi vazut ca o rețea de calculatoare: fiecare poartă este
un calculator care rulează un program foarte simplu. Similar, o rețea de sortare poate
fi văzută ca o rețea unde fiecare comparator este un calculator.
Modelul algoritmilor distribuiți cu transmitere de mesaj
•Proiectantul algoritmului alege doar programul, toate calculatoarele rulând același
program. Sistemul trebuie să funcționeze corect indiferent de structura rețelei (Figura
1).
•Un model des folosit este un graf, unde fiecare nod descrie comportamentul unui
automat finit.
•În cazul algoritmilor distribuiți, problemele computaționale sunt de obicei asociate cu
grafurile. De obicei graful ce descrie structura rețelei de calculatoare este instanța
problemei.
6Instrucțiunea CPU Compare-and-Swap („CAS”) este o instrucțiune specială ce compară conținutul unei locații de
memorie cu o valoare dată, și dacă acestea sunt egale, modifică conținutul respectivei locații de memorie cu o altă
valoare dată.

Capitolul I – Descrierea sistemului de procesare distribuit 10
Figura 1: Exemple de sisteme distribuite7
Pentru a exemplifica diferențele dintre modelele descrise mai sus, vom considera problema
comutațională de găsire a unei colorări pentru un graf dat G (Iftene și Croitoru, 2006). Ar putea
exista următoarele abordări (Taubenfeld și Gadi, 2006):
Algoritmi centralizați
•Graful G este codat ca un șir de caractere, acesta fiind dar calculatorului ca date de
intrare. Programul gasește colorarea grafului, criptează colorarea ca un șir de
caractere, transmițând-ul ca date de ieșire.
Algoritmi paraleli
•Din nou graful G este codat ca un șir de caractere, însă, în acest caz mai multe
calculatoare pot accesa în paralel respectivul șir. Fiecare calculator s-ar putea ocupa de
o parte a grafului, și determina în final o colorare pentru acea parte.
•Accentul este pus pe calculul de înaltă performanță, ce exploatează puterea de
procesare în paralel a mai multor calculatoare.
Algoritmi distribuiți
•Graful G este structura rețelei de calculatoare. Există câte un calculator pentru fiecare
nod din G, și câte o punte de comunicare pentru fiecare muchie din G. Inițial, fiecare
calculator își cunoaște doar vecinul imediat din graf, însă prin schimburi de mesaje
calculatoarele descoperă din ce în ce mai multe informații despre structura grafului G.
7http://en.wikipedia.org/wiki/File:Distributed-parallel.svg

Capitolul I – Descrierea sistemului de procesare distribuit 11
Fiecare calculator trebuie să își determine propria colorare ca dată de ieșire.
•Accentul este pus pe coordonarea operațiilor din cadrul unui sistem distribuit arbitar.
Chiar dacă abordarea algoritmilor paraleli pune un accent diferit față de abordarea algoritmilor
distribuiți, există multe interacțiuni între aceste două domenii. De exemplu algoritmul Cole-
Vichkin pentru colorarea unui graf ( Cole și Vishkin, 1986) a fost original prezentat ca un algoritm
paralel, însă aceeași tehnică poate fi folosită direct ca algoritm distribuit.
Mai mult, un algoritm paralel poate fi implementat fie într-un sistem paralel (folosind memorie
partajată) fie într-un sistem distribuit (folosind transmiterea prin mesaj) ( Andrews și Gregory,
2000). Granița tradițională dintre algoritmii paraleli și cei distribuiți (alegerea unei rețele potrivite
vs. rularea în orice rețea) nu se află în același loc ca granița dintre sistemele paralele și cele
distribuite (memorie partajată vs. transmitere prin mesaj).
Din punct de vedere al complexitații un algoritm centralizat nu necesită foarte mult timp (număr
de pași computaționali) sau spațiu (capacitatea memoriei folosite). Aceste masurători dau o clasă
de complexitate P (probleme de decizie în timp polinomial) și PSPACE (probleme de decizie în
spațiu polinomial) (Papadimitriou, 1994). În ceea ce privește algoritmii paraleli, o altă resursă ce
trebuie avută în vedere este numărul de calculatoare. Întradevăr, există o legatură între timpul de
execuție și numărul de calculatoare: problema poate fi rezolvată mai rapid dacă există mai multe
calculatoare ce rulează în paralel. Dacă o problemă de decizie poate fi rezolvată în timp
polinomial, folosind un numar polinomial de calculatoare, atunci spunem că problema este în
clasa NC (Arora și Barak, 2009 ).
Analizând algoritmii distribuiți, mai multă atenție trebuie acordată operațiilor de comunicare
decât celor de calcul. Poate cel mai simplu model de calcul distribuit este un sistem sincron unde
toate nodurile funcționează blocant. Într-un astfel de sistem, o măsurare a complexitații este dată
de numărul de runde de comunicare sincronă necesare pentru efectuarea unei cerințe
(Papadimitriou, 1994). Deasemenea complexitatea este strâns legată de diametrul rețelei (ce mai
mare distanță dintre doua noduri în cadrul grafului ce reprezină rețeaua).

Capitolul I – Descrierea sistemului de procesare distribuit 12
I.2 Arhitecturi Posibile
Pentru calculul distribuit sunt folosite diverse arhitecturi hardware sau software. La nivel jos,
este necesară interconectarea mai multor procesoare într-un fel de rețea, indiferent dacă această
rețea este imprimată pe o placă de circuit sau este formată din dispozitive vag-cuplate și cabluri.
La nivel înalt, este necesară interconectarea proceselor ce rulează pe aceste procesoare printr-un
sistem de comunicare.
Programarea distribuită se încadrează de obicei în una din arhitecturile sau categoriile de bază:
client-server, arhitectura pe 3 nivele8, arhitectura multi-nivel9, obiecte distribuite, cuplaj slab sau
cuplaj strâns (Godfrey, 2002).
Client-Server (Figura 2): Clientul are capacitatea inteligentă de a se conecta la server,
pentru a primi datele pe care le formatează și le afișează utilizatorului. Datele de intrare
transmise ulterior de utilizator sunt trimise serverului, care înregistrează astfel o
schimbare permanentă.
Arhitectura pe 3 nivele (Figura 2): Sistemele pe trei nivele mută clientul inteligent pe un
nivel de mijloc, astfel încât clienții exteriori pot fi folosiți. Acest lucru simplifică
implementarea aplicației. Majoritatea aplicațiilor web sunt structurate pe 3 nivele.
Arhitectura multinivel (Figura 2): Multinivelul se referă uzual la aplicațiile web care
transmit mai departe cererile primite spre servicii specializate. Succesul avut de serverele
de aplicații a fost determinat în mare parte și de acest tip de aplicații.
Cuplajul strâns (Figura 2): Se referă în general la un cluster de calculatoare ce lucrează
în comun, rulând în paralel un proces partajat. Acesta este împarțit în mai multe sarcini, ce
sunt rezolvate de catre un calculator în parte, rezultatele fiind puse în final în comun
pentru a obține datele de ieșire ale sistemului.
Peer-to-Peer (Figura 2): O arhitectură unde nu există unul sau mai multe calculatoare
care să ofere un serviciu responsabil cu gestionarea resurselor rețelei. În schimb, toate
responsabilitățile sunt împățite uniform între membrii rețelei, cunoscuți ca „peeri”. Un
peer poate servi atât ca server cât și ca client.
8În engleză „3-tier architecture”
9În engleză „n-tier architecture”

Capitolul I – Descrierea sistemului de procesare distribuit 13
Figura 2: Arhitecturi posibile ale Sistemelor Distribuite10
10http://en.wikipedia.org

Capitolul I – Descrierea sistemului de procesare distribuit 14
Un alt aspect de bază, în ceea ce privește arhitectura de calcul distribuit, este metoda de
comunicare și coordonare a sarcinilor efectuate de catre procesele concurente. Deși există
numeroase protocoale de transmitere de mesaje, procesele pot comunica direct unul cu celălalt,
de obicei prin intermediul unei relații master-slave. Alternativ, o arhitectură centrată pe o bază de
date, poate permite efectuarea unui calcul distribuit fară nici o formă de comunicare între procese,
utilizând însă o bază de date partajată.

I.3 Descrierea arhitecturii alese
Să revenim așadar la scopul dat acestei lucrări și anume acela de a descrie un sistem distribuit de
prelucrare a datelor. Motivația creării unui sistem distribuit, și nu al unuia paralel, constă în
avantajele legate de flexibilitatea unei astfel de rețele de lucru. În cadrul unei rețele de dimensiuni
mari sau foarte mari, timpul de rulare și eficiența trec în plan secund (deoarece acestea deja au
valori foarte bune datorită capacității de procesare ridicate a calculatoarelor ce alcătuiesc rețeaua),
pe primul plan urcând problemele de comunicare dintre calculatoare și problemele de
conectivitate a acestora în cadrul rețelei.
Arhitectura pe care este dezvoltat sistemul este arhitectura peer-to-peer11. Așa cum a fost explicat
succint și în subcapitolul anterior c onceptul peer-to-peer const ă, în general, în lipsa unui server, în
sensul clasic al cuvântului, și în preluarea de catre membrii rețelei atât a sarcinilor de client cât și
a celor de server.
Administrarea fișierelor deținute de membrii rețelei trebuie însă efectuată de un server cu
caracteristici mai speciale.Acest server, numit și server de indexare, nu conține nici un fișier și
nici o informație fizic ă necesară în procesele rulate. Serverul de indexare ajut ă doar la reținerea
informațiilor despre clienții care sunt înregistrați, a adresele IP ale acestora sau sarcinilor
efectuate/de efectuat de c ătre un anumit client. Serverul de indexare comunic ă cu clienții prin
conexiuni cu ajutorul socket-ilor utilizând comenzi simple.

O funcționalitate de baz ă a unui astfel de sistem P2P ar fi urm ătoarea (Schollmeier, 2002):
11Prescurtarea folosită uzual este P2P

Capitolul I – Descrierea sistemului de procesare distribuit 15
Un client A dorește să caute fișiere puse la dispoziție de alți clienți în cadrul rețelei P2P.
Clientul A se înregistreaz ă la serverul de indexare cu un ID și cu informațiile legate de
fișierele pe care este dispus s ă le pună la dispoziție rețelei.
Serverul înregistreaz ă fișierele clientului A astfel încât ceilalți clienți s ă poată căuta aceste
fișiere.
Clientul A face o cerere, la serverul de indexare, de c ăutare a tuturor fișierelor ce se
potrivesc unui anumit șablon dat.
Serverul caută în index acele fișiere ce se potrivesc cu solicitarea clientului, și îi întoarce
acestuia clientul care deține fișierul solicitat (de exemplu clientul B), adresa IP a acestuia,
și numele fișierelor cautate.
Odată ce clientul A dorește s ă descarce aceste fișiere, el va crea un socket prin intermediul
căruia se va realiză o conexiune la adresa IP a clientului B, adres ă returnată de server la
pasul anterior.
Arhitectura sistemului nostru pleac ă de la cea expusă mai sus cu mențiunea ca fiecare client poate
deveni la rândul s ău un server de indexare. Serverul de indexare va p ăstra lista clienților
înregistrați și pentru fiecare în parte numele/ID-ul fișierelor deținute și nivelul de procesare a
acestora. În exemplele generale și în cadrul descrierii teoretice a sistemului distribuit dezvoltat
vom considera ca fișierele deținute au trei stari de procesare pe care le vom numerota generic de
la 1 la 3. Acestea ar putea fi de exemplu stare brută, fișiere filtrate și fișiere indexate. În funcție de
particularizarea aleasă ulterior atât numărul starilor, cât și semnificația acestora se poate
modifica.
Datorită dimensiunilor mari ale colenției de date un client poate fi la rândul sau serverul altor
clienți, respectându-se astfel noțiunea peer. Nivelul de procesare atribuit unui astfel de client va fi
cel mai mic dinstre nivelele de procesare are copiilor s ăi.
În momentul în care un client se conecteaz ă la server, acesta din urm ă va analiza nivelul de
procesare a datelor clientului și îi va trasa acestuia sarcini astfel încât subcolenția sa de
documente să fie gata pentru căutare. Dacă clientul este la rândul s ău server, el va transmite mai

Capitolul I – Descrierea sistemului de procesare distribuit 16
departe sarcinile clienților s ăi în funcție de datele deținute de aceștia. Mai multe detalii vor fi însă
oferite în subcapitolul următor.
Inițial, arhitectura sistemului pare una dezvoltată pe un arbore, unde radăcina acestuia este peer-ul
care inițiază rețeaua, nodurile de pe urmatoarele nivele sunt peeri ce se conectează ulterior, iar
frunzele sunt ultimii peeri conectați (peeri care au doar rolul de client pentru parinții lor din
cadrul arborelui).
Ulterior însă, orice entitate va putea efectua/porni operațiile posibile în cadrul sistemului.
Eventualele operații vor putea fi efectuate doar după ce toate fișierele din cadrul rețelei au ajuns
la ultimul stadiu de prelucrare. Astfel arborele va deveni un graf deoarece în cadrul acestor
operații vor fi create legături între peeri, indiferent de nivelul sau legăturile lor în cadrul arborelui
conform protocolului mai jos descris:
Peer-ul A va efectua operația dorită pe colecția proprie de documente, aceasta numai în
cazul în care fișierele sunt preg ătite pentru efectuarea operației, dupa care va crea o lista
de rezultate.
Va deschide un port de comunicare în care va aștepta r ăspunsurile primite de la celelate
entitați din sistem, r ăspunsuri care odata primite vor fi ad ăugate la lista de rezultate creat ă
la pasul anterior.
Peer-ul A, solicitantul operației, va trimite atât vecinilor inferiori cât și celor superiori
tipul operației, informații referitoare la operație (Ex șablonul de c ăutare), IP-ul și portul la
care se așteapta răspunsul.
Când o entitate (Peer-ul B) primește o cerere pentru efectuarea unei operații, aceasta
efectuează operațiile asupra fișierelor proprii (dac ă are astfel de fișiere), transmite
răspunsul la IP-ul și prin portul comunicat dup ă care transmite cererea atât la nivel
superior cât și la nivel inferior cu excepția sursei inițiale.
Dacă Peer-ul B nu are alte legaturi cu excepția sursei îi va trimite acesteia un semnal prin
care o înștiințează că pe firul său s-au terminat de efectuat toate operațiile și s-au trimis
toate răspunsurile (semnal de confirmare).
Dacă Peer-ul B a transmis cereri, atunci așteaptă s ă primeasca semnalul de confirmare de

Capitolul I – Descrierea sistemului de procesare distribuit 17
la fiecare nod, după care transmite, sursei sale, la rândul ei un semnal de confirmare.
În momentul în care Peer-ul A primește semnale de confirmare de la toți vecinii spre care
a transmis cereri inițial, preia lista cu răspunsuri, și unindu-i elementele creaz ă răspunsul
final.
I.4 Implementarea sistemului de calcul distribuit
După cum s-a sugerat și în capitolul anterior, sistemul distribuit va fi alcatuit din 3 module
principale:
Modulul de conectivitate: va gestiona creearea de conexiuni și întreținerea acestora.
Modulul de prelucrare: va coordona prelucrarea datelor, astfel încât la un moment dat
fiecare membru al rețelei sa execute dacă este posibil aceeași operație.
Modulul de efectuare a operațiilor: va coordona efectuarea distribuită a operațiilor în
cadrul sistemului, culegand rezultatele parțiale și ulterior oferind la ieșire rezultatul final
obținut prin unirea celor parțiale.
Înainte de a trece la descrierea fiecărui modul, ar trebuie precizat faptul că fiecare element al
rețelei are un comportament identic, cu excepția primului peer, cel ce a inițiat rețeaua.
Flexibilitatea este pusă, în cadrul acestei arhitecturi, pe un nivel foarte ridicat, însă siguranța
conexiunilor este și mai importantă. Din acest motiv este nevoie ca în anumite momente cheie ale
execuției să existe o entitate supremă care să ia anumite decizii.

Primul pas în extinderea sau crearea unei noi rețele este crearea unui peer. Pentru creearea
acestuia avem nevoie de datele de intrare din care să aflam informațiile necesare pentru creare
conexiunilor dar și pentru identificarea fișierelor proprii. Odata stocate datele de intrare, sunt
inițializate structurile în care vom memora informații despre peerii ce se vor conecta ulterior la
elementul curent(vezi Figura 3). Tot la acest pas, în funcție de informațile primite vom stabili
dacă actualul peer este primul din cadrul unei noi rețele sau nu.

Capitolul I – Descrierea sistemului de procesare distribuit 18
public Peer(String ip, int port, int statusFiles, String filesLocation_,
String parentIP, int parentPort, int nrMaxChildrens_)
{
if (parentIP == null)
mainServer = true;
else
{
parent = parentIP;
parentComPort = parentPort;
}
ipAdress = ip;
portAcceptPeers = port;
filesLocation = filesLocation_;
files = statusFiles;
nrMaxChildrens = nrMaxChildrens_;

childrenPeers = new List<String>();
childrenPeersComPorts = new List<int>();
childrenFilesStatus = new List<int>();
}
Figura 3: Constructorul
Urmatoarele operații ar fi pornirea unui nou fir de execuție în care peer-ul curent să aștepte
conectarea unor noi eventuali membri ai rețelei, dar și conectarea sa la membrul de care este
legat, și despre care cunoaște informații din cadrul rețelei.
Cele două operații pot fi concurente, firul de execuție ce permite acceptarea altor entitați în cadrul
rețelei prin intermediul nodului curent, fiind în viață atât timp cât numarul maxim de copii nu
este depășit.
În cadrul acestuia se creează rând pe rând socket-uri care acceptă noi conexiuni. În cadrul
acestora peer-ul curent primește informții (așa cum se poate vedea în Figura 4) atât despre
fișierele deținute de noii membri ai rețelei, cât și informații legate de modalitățile viitoare de
comunicare – adrese de IP. La rândul său transmite peeri-lor copii numarul unui port la care va
trimite comenzile viitoare. Aceste comenzi vor fi fie comenzi de prelucrarea datelor, fie comenzi
de efectuare a operațiile posibile.

Capitolul I – Descrierea sistemului de procesare distribuit 19
private void AcceptPeers()
{
listenForPeers.Start();
while (nrMaxChildrens > childrenPeers.Count)
{
Socket curentNewChild = listenForPeers.AcceptSocket();
//Citim ip-ul
byte[] bb = new byte[100];
curentNewChild.Receive(bb);
StringBuilder bufer = new StringBuilder();
for (int i = 0; i < bb.Length; i++)
{
if (bb[i] == 0) break;
bufer.Append(Convert.ToChar(bb[i]));
}
childrenPeers.Add(bufer.ToString());
//setam portul
int futureComPort = childrenPeers.Count + 6000;
childrenPeersComPorts.Add(futureComPort);
//trimitem portul
curentNewChild.Send
(asen.GetBytes(futureComPort.ToString()));
//citim statusul fisierelor
byte[] bb2 = new byte[100];
curentNewChild.Receive(bb2);
StringBuilder bufer2 = new StringBuilder();
for (int i = 0; i < bb2.Length; i++)
{
if (bb2[i] == 0) break;
bufer2.Append(Convert.ToChar(bb2[i]));
}

childrenFilesStatus.Add( int.Parse(bufer2.ToString()));
}
listenForPeers.Stop();
}
Figura 4 – Funcția în care rulează firul de execuție responsabil cu acceptarea copiilor
Funcția de conectare la părinte execută aceleași operațiile efectuate și la fiecare pas din cadrul
funcției AcceptPeers (vezi Figura 4), doar că acestea sunt oglindite, funcțiile fiind practic
complementare. Totuși funcția de conectare este responsabilă de pornirea unui nou fir de
execuție, fir ce va asculta la portul comunicat de părinte, eventualele comenzi ulterioare ale
acestuia (vezi Figura 5).

Capitolul I – Descrierea sistemului de procesare distribuit 20
public void ConnectToServer()
{
TcpClient client = new TcpClient(parent, parentComPort);
Stream stream = client.GetStream();
//trimitere IP, receptare port, trimitere status fisiere
client.Close();
Thread listingForComands = new Thread
(new ThreadStart(ListingCom));
ListingForComands.Start();
}
Figura 5: Conectarea la server; pornirea firului de execuție responsabil de primirea comenzilor
Chiar daca nu toți peerii din cadrul rețelei și-au finalizat procesul de conectare, în sensul în care
numărul curent de fii nu este egal cu cel maxim, rețeaua poate porni procedura de prelucrare
sincronizată a datelor. Acest proces poate fi pornit doar de către inițiatorul sistemului, celelalte
entitați membre neavând dreptul de a porni acest modul. În cadrul acestui modul, comunicarea se
poartă pe structura arborescentă a sistemului. Inițiatorul procedurii, fixează nivelul de prelucrare
care se dorește a fi atins în cadrul rețelei la final (uzual se va alege cel mai înalt nivel), după care
apelează funția care va coordona prelucrarea pas cu pas a datelor din sistem (implementarea
funcției poate fi consultată în Figura 6).
Așa cum s-a precizat și în subcapitolul anterior, un peer, pe lânga starea fișierelor proprii,
păstrează și stare de prelucrare a fișierelor copiilor săi. Starea globală a fișierelor unui peer este
dată de minimul dintre coeficientul stării fișierelor proprii și coeficienții stărilor copiilor. De
exemplu dacă fișierele proprii se află în stadiul de prelucrare 1, iar fiii 1 și 2 în stadiu 2, starea
globală de prelucrare va fi 1. Aceasta va fi și starea păstrată de părintele peer-ului curent,
corespunzătoare acestuia.
Înainte de fiecare pas din cadrul funcției de prelucrare se execută o verificare a nivelelor de
prelucrare a fișierelor proprii sau deținute de copii. Dacă toate acestea au ajuns la nivelul dorit,
înseamnă că procedura s-a finalizat cu succes. Dacă nu, se va trece în starea ce permite conectarea
unor noi copii, această procedură fiind încă posibilă. Astfel, timp de 5 secunde se așteaptă
conectarea unui nou peer, iar în cazul în care avem o nouă conexiune procedura de așteptare se
repetă. Timpul de 5 secunde s-a considerat a fi unul optim, deoarece, în mod normal procedurile

Capitolul I – Descrierea sistemului de procesare distribuit 21
de prelucrare a datelor de dimensiuni mari cer mult mai mult timp. Din acest motiv conectarea a
cât mai mulți membri în cadrul rețelei poate îmbunătăți semnificativ timpul final de prelucrare.
Dacă după 5 secunde, nu se mai conectează nici un peer, atunci se determină stadiul minim de
procesare la care se găsesc copii actuali ai elementului curent. Acesta se compară în final și cu
fișierele proprii, iar daca acestea au cel mai mic stadiu de prelucrare, se ridică acest nivelul (în
cazurile particulare ale acestui sistem se va apela funcția respectivă de prelucrare a fișierelor).
Apoi, se compară, rând pe rând, stadiile de procesare a fiecărui copil în parte, și în cazurile în
care acestea sunt egale cu minumul, se transmite o comandă de ridicare a nivelului. Această
comandă se realizează prin crearea unei noi conexiuni, peer-ul curent cunoscând adresa IP a
fiecarui copil, dar și porturile la care aceștia așteaptă eventualele comenzi.
void MoveUP(int limit)
{
//în cadrul funcției VerifyChildren se verifică dacă
//stadiile de prelucrare au ajuns la nivelul dorit
while (!VerifyChildren(limit))
{
int beforeSleep = childrenPeers.Count;
Thread.Sleep(5000);
while (beforeSleep < childrenPeers.Count)
{
beforeSleep = childrenPeers.Count;
Thread.Sleep(5000);
}
int minim = limit;
foreach (int x in childrenFilesStatus)
{
if (x < minim) minim = x;
}
if (files <= minim)
{
minim = files;
files++;

}
for (int i = 0; i < childrenFilesStatus.Count; i++)
{

Capitolul I – Descrierea sistemului de procesare distribuit 22
if (childrenFilesStatus.ElementAt(i) == minim)
{

String peer = childrenPeers.ElementAt(i);
int peerPort = childrenPeersComPorts.ElementAt(i);
TcpClient sendInstruction = new TcpClient
(peer, peerPort);
Stream stream = sendInstruction.GetStream();
//trimitere comanda
byte[] bb = asen.GetBytes( "moveUP");
stream.Write(bb, 0, bb.Length);
//citim OK-ul
byte[] bb2 = new byte[100];
stream.Read(bb2, 0, 100);
StringBuilder bufer = new StringBuilder();
for (int j = 0; j < bb2.Length; j++)
{
if (bb2[j] == 0) break;
bufer.Append(Convert.ToChar(bb2[j]));
}
sendInstruction.Close();
if (bufer.ToString() == "OK")
{
int aux = childrenFilesStatus.ElementAt(i);
childrenFilesStatus.RemoveAt(i);
childrenFilesStatus.Insert(i, aux + 1);
}}}}}
Figura 6: Funcția ce coordonează prelucrarea datelor
În cazul peeri-lor ce primesc comanda de ridicare de nivel, ei apelează aceași funcție prezentată
în Figura 6 specificând ca nivel dorit, nivelul actual incrementat cu 1. Ulterior recalculează
nivelul curent și comparând-ul cu cel anterior stabilesc mesajul care trebuie trimis înapoi
părintelui – upgrade reușit cu succes sau eroare (Figura 7)
//bufer păstrează comanda primită
if (bufer.ToString() == "moveUP")
{
int curent = overallFilesStatus;
MoveUP(curent + 1);
//funcția UpdateOverallFileStatus analizează
//statutul fișierelor proprii și a copiilor
//reactualizând overallFilesStatus
UpdateOverallFileStatus();

Capitolul I – Descrierea sistemului de procesare distribuit 23
if ((curent + 1) == overallFilesStatus)
{
newInstruction.Send(asen.GetBytes( "OK"));
}
else newInstruction.Send(asen.GetBytes( "Fail")); }
Figura 7: Tratarea comenzii de ridicare de nivel
Odată finalizată prelucrarea datelor, sistemul trebuie pregatit pentru pornirea ulterioară a
anumitor operații de procesare. Cum doar peer-ul inițiator al rețelei poate ști momentul în care
toate nodurile din sistem și-au terminat prelucrarea, tot el este responsabil cu trimiterea acestui
semnal. Astfel, în momentul în care funcția din Figura 6 își în cheie execuția, deoarece nivelul de
prelucrare este cel maxim în toată rețeaua, peer-ul inițial pornește un nou fir de execuție în care să
aștepte, la un port standard, eventualele cereri de efectuare de operații din partea copiilor săi.
Apoi, le transmite acestora o comandă prin care să îi înștiințeze de noua stare a sistemului, ei
efectuâd la rândul lor operațiile descrise mai sus. Procedeul se repetă rând pe rând, până în
momentul în care semnalul este transmis în toată rețeaua.
Operațiile posibile în cadrul rețelei pot avea caracteristici diferite, în funcție de particularizarea
ulterioară a rețelei, însă toate acestea sunt bazate pe trimitere de mesaje și recepțioanare de
răspuns. Practic nodul ce inițiază operația le trimite vecinilor săi tipul operației dorire și un șir de
caractere, iar receptorii transmit un rezultat.
În momentul în care un peer din cadrul rețelei dorește începerea unei anumite operații, acesta
deschide un port de comunicare, în cadrul unui nou fir de execuție, la care va aștepta
răspunsurile. Apoi apelează o metodă generică, în interiorul căreia se vor transmite copiilor
comenzi cu operația curentă, prin intermediul mecanismului de recepționare de comenzi deja
implementat, și cereri parinților, aceștia ascultând cererile la portul deschis în timpul execuției
submodulului de pregătire a operațiilor (Figura 8).
Odată cu tipul și comanda propriu-zisă, peeri primesc și IP-ul expeditorului însoțit de port-ul la
care acesta așteaptă răspunsul. Așadar, peer-ul destinatar, dupa ce apelează însuși metoda generică
de trimitere de comenzi, efectuează comanda pe propriile fișiere, și conectându-se direct la
inițiatorul comenzii, transmite răspunsul.

Capitolul I – Descrierea sistemului de procesare distribuit 24
void sendComands(int notSendHere,string operation,string IpDest,int portDest)
{
for (int i = 0; i < childrenFilesStatus.Count; i++)
{
if (i != notSendHere)
{
String peer = childrenPeers.ElementAt(i);
int peerPort = childrenPeersComPorts.ElementAt(i);
TcpClient sendInstruction = new TcpClient
(peer, peerPort);
Stream stream = sendInstruction.GetStream();
//trimitere comanda de efectuare a
//operatiei „operation”
byte[] bb = asen.GetBytes (operation);
byte[] bb2 = new byte[100];
stream.Write(bb, 0, bb.Length);
stream.Read(bb2, 0, 100);
byte[] bb1 = asen.GetBytes(IpDest);
stream.Write(bb1, 0, bb1.Length);
stream.Read(bb2, 0, 100);
byte[] bb3 = asen.GetBytes(portDest.ToString());
stream.Write(bb3, 0, bb3.Length);

stream.Read(bb2, 0, 100);
StringBuilder bufer = new StringBuilder();
for (int j = 0; j < bb2.Length; j++)
{
if (bb2[j] == 0) break;
bufer.Append(Convert.ToChar(bb2[j]));
}
sendInstruction.Close();
}
}
}
Figura 8: Funcția prin care sunt trimise comenzi de efectuare a operației curente
În momentul în care un peer nu mai are copii, el trasmite, în cadrul conexiunii sale de efectuare
de operație, un semnal prin care semnalizează faptul că a finalizat procesul de aflare și
transmitere a răspunsului. În mod identic când un peer primește astfel de semnale de la toate
nodurile spre care a emis comanda sau cererea de efectuare a operației, semnalizează la rândul
său finalul operației în cadrul subrețelei sale.

Capitolul I – Descrierea sistemului de procesare distribuit 25
Peer-ul ce a inițiat căutarea recepționează, odată cu transmisia semnalului în rețea, rezultatele
parțiale (Figura 9). Rezultatul final este asamblat pe parcursul, primirii rezultatelor din partea
nodurilor rețelei, el fiind depus ca dată de ieșire, într-un fișier sau pe un anumit server în funcție
de particularizarea suferită de sistem, în momentul în care se primesc toate semnalele de
finalizare a operației.
void getResult()
{
acceptingResults.Start();

while (searching)
{
Socket curentPeer = acceptingResults.AcceptSocket();
//citim rezultat
byte[] bb = new byte[100];
curentPeer.Receive(bb);
StringBuilder bufer = new StringBuilder();
for (int i = 0; i < bb.Length; i++)
{
if (bb[i] == 0) break;
bufer.Append(Convert.ToChar(bb[i]));
}
Rezultat = Rezultat.Append( bufer.ToString() + "\r\n");

}
acceptingResults.Stop();
}
Figura 9: Primirea rezultatelor parțiale și asamblarea acestora
I.5 Concluzii
Problemele computaționale ce au nevoie în rezolvarea lor clasică de multe resurse pot fi rezolvate
în cadrul unei rețele de calculatoare prin intermediul algoritmilor paraleli și/sau distribuiți.
Algoritmii distribuiți prezintă avantajul nepartajării resurselor, fiecare calculator rulând același
proces, comunicarea efectuându-se pe baza transmiterilor de mesaje. Deasemenea în cadrul
rețelelor de dimensiuni foarte mari, timpul de rulare trece în plan secund, flexibilitatea sistemelor
distribuite oferind astfel un mare avantaj.

Capitolul I – Descrierea sistemului de procesare distribuit 26
Arhitectura aleasă este una de tip peer-to-peer, un tip caracteristic în general sistemelor
distribuite. Funcționarea sistemului este structurată pe baza a trei module. Primul dintre ele,
modulul de conectare asigură comunicarea inițiala dintre peeri și realizarea tuturor schimburilor
de informație necesare în vederea efectuarii urmatoarelor proceduri.
Cel de-al doilea modul, folosește conexiunile realizate anterior pentru a efectua procesarea
datelor în mod sincronizat. Acest lucru presupune efectuarea pe cât posibil, a aceeași operație
simultan, pe toate entitațile membre ale rețelei.
Dacă inițial structura rețelei părea a fi arborescentă, acest lucru se modifică în cadrul ultimului
modul. Aici orice nod poate începe o anumită operație de procesare a datelor anterior prelucrate,
comunicarea comenzilor efectuându-se între peeri din aproape în aproape, însă transmiterea
rezultatelor realizându-se direct la peer-ul inițiator. Astfel schema conexiunilor din cadrul rețelei
devine un graf.
Sistemul descris este unul generalizat, scopul său fiind oferirea unei platforme de prelucrare și
procesare de date în mod distribuit. Fiind capabil de particularizări diferite, sistemul poate fi
adaptat în funcție de necesitățile avute la un moment dat. Mai multe despre particularizarea
sistemului în Capitolul III.

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 27
Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri
Pentru a demonstra capacitățile sistemului descris în anterior, în acest capitol vom modela și
verifica prin intermediul rețelelor Petri de tip P/T (Jucan și Țiplea, 1998) funcționabilitățile
modulelor acestuia.
II.1 Modelarea corespunzătoare Modulului de Conectare
Să analizăm în prima parte comportamentul primului modul descris anterior și anume modul de
conectare. În Figura 10 este modelat comportamentul acestui modul pentru un peer care are
numărul maxim de fii 5.
Figura 10: Rețeaua Petri corespunzătoare modulului de conectare
Deoarece acest model, la fel ca și modulul pe care îl reprezintă, face parte dintr-un ansamblu mult
mai mare, analizele clasice prin intermediul S-invarianților, T-invarianților, sifoanelor, sau
capcanelor nu sunt viabile. Graful de accesibilitate este unul liniar, urmând procesul de conectare
a peeri-lor:
(0,6,0,1,0) → t1 → (1,5,0,0,0) → t2 → (1,4,1,0,0) → t2 … (t2 se efectuează de 4 ori aici) … t2 →
(1,0,5,0,0) → t3 → (0,0,0,2,5)
După cum se poate observa și din cadrul acestuia, prima tranziție posibilă, și anume t1,
marchează începutul comenzii de conectare. Odata efectuată, t1 depune un punct în P1, astfel

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 28
devenind viabilă tranziția t2. Aceasta reprezintă practic, conectările efectuate rând pe rând de
evetualii copii ai peer-ului curent. În momentul în care toți posibilii copii sunt conectați se
activează tranziția t3 ca va determina finalul procedurii de conectivitate. Odata finalizată
procedura de conectare, ea nu mai poate reîncepe deoarece locația P2 este goală, peer-ul fiind
nevoit să continue executarea următoarelor module.
Rețeaua Petri prezentată în Figura 10 are urmatoarele proprietăți:
Este pseudo-viabilă, din starea inițială fiind posibile toate cele 3 tranziții => Procedura de
conectare este posibilă.
Nu este viabilă – a se vedea graful de accesibilitate liniar.
Implicit nu este reversibilă => Conectarea se poate efectua o singură dată
Este marginită, toate locațiile conținând, în orice moment un numar limitat de puncte =>
Nu se pot conecta decat un numar dorit de peeri.
Există un singur blocaj, care reprezintă practic finalul modulului de căutare.
II.2 Modelarea corespunzătoare Modulului de Prelucrare a datelor
Al doilea model descrie comportamentul modulului de procesare a informațiilor.
Comportamentul acestuia este bazat în primul rând pe natura peer-ului. Astfel un peer oarecare
are posibilitatea de a se conecta la părintele său și de a asculta eventualele comenzi de ridicare a
nivelului de procesare, pe când inițiatorul rețelei are capacitatea de a porni procedura sincronizată
procesare a informațiilor.
Drept exemplu am modelat (Figura 11) comportamentul unui peer care are 5 clienți conectați la el
și este membru al unei rețele cu 3 nivele de procesare a datelor. Comportamentul în cadrul
modelului este simetric în cazurile în care peer-ul are părinte sau este nod inițial. Astfel pot exista
2 stări inițiale: (0,1,5,2,0,0,3,0,0,0,0,0,0,0,0) și (0,0,5,2,0,0,3,0,0,1,0,0,0,0,0). Implicit vom avea 2
grafuri de accesibilitate, liniare, simularea fiind și în acest caz deterministă, neexistând decât un
singur drum spre starea finală.

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 29
În primul caz, se va putea produce inițial tranziția t6, ce va marca începutul procedurii, urmată
apoi de cele 3 stadii de prelucrare a datelor. În cadrul fiecarui stadiu, pornit prin producerea
tranziției t8, se vor efectua doua feluri de comenzi concurente: ridicarea nivelului propriilor
fișiere și comenzi de sincronizare catre cei 5 clienți. Odată finalizate stadiile de prelucrare, locația
P7 nu va mai avea nici un punct, sistemul fiind astfel limitat la numărul dorit de prelucrări.
Complementarietatea locațiilor P2 și P10 demonstrează faptul că un peer poate avea părinte dacă
și numai dacă el nu este inițiatorul rețelei.
Figura 11: Rețeaua Petri corespunzătoare modulului de prelucrare a datelor
Rețeaua petri prezentată în Figura 11 are următoarele proprietăți:
Nu este pseudo-viabilă. Aceasta proprietate se respectă doar pe partea corespunzătoare

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 30
tipului peer-ului. Se demonstrează astfel faptul că peer-ul inițiator nu se poate conecta deoarece
nu are părinte, iar celelalte noduri nu pot porni operația de prelucrare a datelor.
Nu este viabilă.
Implicit nu este reversibilă => Odată încheiată procedura de prelucrare ea nu poate fi
reluată.
Este marginită, toate locațiile conținând, în orice moment un număr limitat de puncte =>
Numărul prelucrarilor este respectat, configurația sistemului păstrand marcările inițiale
(numarul de clienți acceptați, faptul ca peer-ul curet are părinte sau nu)
Există un singur blocaj, în momentul în care locația P1 acumulează numărul de puncte
avut în starea inițială de P7. Acest lucru marchează faptul ca toate procedurile de
procesare propuse au fost îndeplinite.
II.3 Modelarea corespunzătoare Modulului de Căutare
Operațiile de procesare a datelor din cadrul ultimului modul vor fi considerate, în cadrul
modelului prezentat, operații de căutare, principiul de procesare în scopul obținerii unui șir de
caractere fiind identic. Astfel, modelarea surprinde cele trei acțiuni posibile în cadrul unui peer:
începerea unei căutari, ascultarea unei comenzi din partea părintelui, dacă acesta există, și
ascultarea cererilor din partea copiilor.
În Figura 12 este prezentat modelul unui peer, care a trecut prin trei nivele de procesare din trei
posibile. Acesta are conectați la el cinci clienți, la rândul său fiind conectat la propriul părinte.
Singura tranziție posibilă inițial este t16, tranziție ce depune un punct în locația P20 marcând
astfel faptul ca sistemul este pregătit pentru căutare.
Dacă peer-ul curent are părinte, se marchează posibilitatea primirii unei comenzi de căutare prin
efectuarea lui t15, procedeul fiind identic în cazul ascultarii de cereri de la copii prin intermediul
tranziției t17. Astfel devin viabile tranzițiile t18, t19 și t20, tranziții ce semnifică începutul
acțiunilor de căutare. În cadrul fiecăreia, dintre aceste acțiuni se vor produce concurent trei tipuri
de căutari:

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 31
Figura 12: Rețeaua Petri corespunzătoare modulului căutare
Căutarea în fișierele proprii și prelucrarea răspunsului prin întermediul secvenței t24 →
t25
Căutarea la părinte prin efectuarea tranziției t26, ce semnifică efectuarea unei cereri, în
cazul în care părintele există, sau anularea cererii spre părinte în cazul opus prin
intermediul tranziției t27.
Căutarea la clienți prin efectuarea tranziției t21, ce semnifică efectuarea unei cereri de
căutare. Numărul de clienti spre care se trimit comenzi este stric controlat prin
intermediul locațiilor P23 și P24, deoarece în cazul în care operația curentă de căutare este
pornită în peer-ul curent de un copil de-al său prin tranziția t20, acel copil nu trebuie să
mai primească comanda.
Tranzițiile responsabile de pornirea acestor căutari (t18, t19 și t20) nu sunt concurent posibile
deoarece partajează locația P29, ce semnifică disponibilitatea unei operații. Această locație are
inițial 3 puncte, fiecare reprezentând una dintre căutarile mai sus amintite. În finalul efectuării

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 32
tuturor celor 3 operații de căutare, locația P29 revine la setarea inițială, permițând efectuarea unei
noi acțiuni de căutare.
Rețeaua Petri, prezentată în figura 12, corespunzătoare modulului de căutare are urmatoarele
proprietăți:
Este pseudo-viabilă
Nu este în totalitate viabilă. Proprietatea de viabilitate este respectată întreaga rețea cu
excepția tranzițiilor t15, t16 și t17. Acestea doar setează sistemul, viabilitatea restului
rețelei demonstrând capacitatea sa de efectuare a mai multor proceduri de căutare,
respectiv a mai multor operații de procesare a datelor.
În cazul reversibilității, se repetă situația prezentată mai sus. Rețeaua poate reveni la
configurația avută dupa efectuarea tranzițiilor t15,t16 și t17.
Este marginită, controlul asupra efectuării operațiilor fiind stric.
Datorită proprietății de reversibilitate parțială, rețeaua nu are blocaje.
II.4 Concluzii
Modelarea sistemului prin intermediul Rețelelor Petri de tip P/T, este o misiune dificilă, aceast
lucru nefiind determinat doar din cauza dimensiunilor și capacităților sistemului. Nivelul ridicat
al controlului dorit asupra conexiunilor și comunicării din cadrul rețelei este principalul
responsabil al stricteții cu care poate fi simulat modelul.
Numărul ridicat al locațiilor de control, slabesc puterea de analiză a modelului. Sistemele clasice
de analiză în cazul rețelelor Petri de tip P/T, așa cum ar fi calcularea S/T invarianților, verificarea
capcanelor, a sifoanelor, nu sunt viabile, simularea cu ajutorul unui program specializat, urmată
de o analiză empirică fiind singurele modalități de demonstrare a capacităților sistemului. Ca
unealtă de design și simulare a rețelei Petri a fost folosit programul Renew12.
Rețeua este structurată pe 3 module principale: modulul de conectare, cel de prelucrare a datelor
12http://www.renew.de

Capitolul II –Modelarea sistemului prin intermediul Rețelelor Petri 33
în mod sincronizat și modulul de căutare. Executarea primelor două se realizează în mod liniar,
contolul fiind deosebit de strict. În cadrul modulului secund există doua modalități
complementare de execuție, fiind aleasă cea corespunzătoare proprietăților peer-ului curent, în
funcție de statutul acestuia în cadrul rețelei. Spre deosebire de primele doua, modulul trei are o
componentă reversibilă, aceasta asigurând faptul că se pot executa mai multe căutari. Rețeaua
completă și legăturile dintre module pot fi consultate în Figura 13.
Figura 13: Modelul Sistemului Distribuit – Legăturile dintre module

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 34
Capitolul III – Particularizarea sistemului – CLEF-IP 2010
Sistemul distribuit de procesare a datelor prezentat în cadrul acestei lucrări, a fost realizat cu
scopul de putea fi utilizat în orice situație clasică de procesare a datelor care consuma foarte
multe resurse și timp. Caracteristicile sale sunt generale, sistemul fiind ușor de instalat în cadrul
unei rețele locale de calculatoare. Particularizările dorite sunt ușor realizabile doar prin
introducerea funcțiilor speciale de procesare și eventual prin adaptarea căutării distribuite în
funcție de necesități.
Pentru a ilustra aplicabilitatea practică a acestui sistem, dar și ușurința unei particularizări ale
sale, în acest capitol vom desrie modul în care sistemul distribuit prezentat și modelat anterior, a
fost adaptat pentru a rezolva sarcinile propuse de CLEF-IP 201013.
III.1 CLEF-IP 2010
CLEF-IP 2010 este o competiție lansat ă de Information Retrieval Facility & Matrixware în anul
2009 și continuată anul acesta printr-o nouă campanie. Ea își propune investigarea tehnicilor de
extragere a informațiilor din domeniul proprietații intelectuale.
Aceasta sarcină a fost aleasă pentru ilustrarea proprietăților sistemului deoarece își propune
procesarea unei colecții foarte mari de date, aproximativ 84 Gb, colecție formată din aproximativ
2.6 milioane de documente de patent reprezentând 1.6 milioane de patente ale Organizației
Europene de Patente14. Aceste documente sunt derivate din formatul EPO dezvoltat de organizația
mai sus numită, având o dimensiune mai mare de 1Mb și fiind editate în limbile engleză, franceză
și germană. Un exemplu al unui astfel de document poate fi consultat în Figura 14, aceasta
ilustrand principalele tag-uri din XML-ul corespunzator patentului de invenție EP-0010101-A1.
Participantă la cunoscuta campanie CLEF (Cross Language Evaluation Forum), CLEF-2010 își
13http://www.ir-facility.org/research/evaluation/clef-ip-10/overview
14http://www.epo.org/

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 35
Figura 14: Structura documentului corespunzător patentului EP-0010101-A1
propune următoarele două sarcini:
Sarcina de căutare „Prior Art”: Își propune găsirea tuturor patentelor, a căror informații
publice sunt conținute într-o aplicație dată pentru un nou patent. (aceasta sarcină a fost
propusă și în cadrul CLEF-IP 2009)
Sarcina de căutare: Își propune clasificarea unui patent dat după un anumit standard (IPC
sau/și ECLA15)
Sistemul particularizat în cadrul acestui capitol se va axa pe rezolvarea sarcinii de căutare „prior
art”, aceasta fiind un foarte bun exemplu de prelucrare și procesare a unei colecții de documente.
În cadrul soluțiile propuse în anul 2009 pentru Căutarea ”Prior Art” s-au folosit diverse tehnici în
filtrarea și indexarea fișierelor așa cum ar fi (Iftene, Ionescu et al, 2009):
Folosirea celei mai noi versiuni a fișierului xml
15http://www.wipo.int/ipcreclassification/documentation/ECLA_to_IPC_specification_20060512.txt

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 36
Folosirea indexarii Lemur
Crearea de meta-date pentru fiecare document
Lematizarea tuturor fișierelor și crearea unui index pentru acestea
Principala ustensilă pe care o vom folosi pentru prelucrarea datelor, dar și pentru operația de
căutare este Lucene .Net.
III.2 Lucene .Net
„Lucene .Net este un cod sursă de clasă-pe-clasă, API-pe-API și portul algoritmic de căutare al
motorului Java Lucene pentru C# și platforma .Net utilizând Framework-ul Microsoft .Net.
Lucene.Net rămane aproape de API-urile și clasele folosite în implementarea originală, în Java, a
Lucene.
Numele API-urilor, ca și numele claselor de altfel, sunt păstrate cu intenția de a da Lucene.net-
ului aspectul și senzația limbajului C# și a platformei .NET. De exemplu metoda Hits.legth() din
implementarea în Java este Hits.Length în versiunea C#. În plus fața de API-uri și clase,
algoritmul folosit în Java Lucene este folosit și în C# Lucene. Acest lucru înseamnă că un index
creat cu Java Lucene este compatibil cu unul creat cu C# Lucene, atât la scriere, cât și la citire sau
modificare. De fapt un index Lucene poate fi supus unor operații de căutare și modificare, în mod
concurent, de către procese ce folosesc și Java Lucene și C# Lucene.”16
Prelucrarea colecției de documente cu Lucene (Hatcher și Gospodnetic, 2005)oferă numeroase
avantaje așa cum ar fi: condensarea informațiilor ce ne interesează într-un spațiu mult mai mic,
stratificarea informațiilor în funcție de nivelul lor de interes, o accesibilitate deosebit de ridicată a
informațiilor utile în momentul utilizării acestora, diferite modalități de căutare în cadrul
indecșilor creați.
Pe langa avantajele enumerate mai sus există și o serie de dezavantaje ale utilizării Lucene-ului.
16http://lucene.apache.org/lucene.net/

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 37
De exemplu crearea unui index necesită un timp deosebit de mare în cadrul colecțiilor de
dimensiuni mari așa cum este colecția oferită de CLEF-IP 2010. Deasemenea atât rularea
procesului de indexare cât și desfașurarea operațiilor de căutare necesită resursele de nivel înalt.
Din aceste motive aplicațiile ce folosesc Lucene sunt adecvate pentru modificări dese, punând
probleme în cazul creerii de noi versiuni.
III.3 Adaptarea sistemului
Pentru a adapta sistemul general într-un scop anume trebuie avute în vedere toate cele trei module
principale și modalitatea în care comportamentul lor poate fi pliat sau modificat pentru a
îndeplini sarcinile dorite.
Structura modulului de conectare nu se întrepătrunde cu prelucrarea propriu-zisă a datelor, așa că
implementarea sa rămâne cea descrisă în cadrul capitolul I.4 și ilustrată în Figurile 3 și 4. În
cadrul conectării, fiecărui peer i s-a atribuit o parte proporțională din cele 2.6 milioane de
documente, date ce vor fi prelucrate de urmatoarele module.
Efectuând o analiză mai atentă asupra funcției prezentată în Figura 6, funcție ce este responsabilă
cu sincronizarea prelucrării datelor, se poate observa faptul că ridicările de nivel sunt efectuate
practic în momentul în care fiecare peer, identifică datele sale ca fiind de nivel minim. Astfel
pentru a atribui unei ridicări de nivel o anumită semnificație nu trebuie decât să implementam
separat funcționalitatea pe care dorim să o atribuim respectivei modificari de nivel, și în
momentul producerii sale să apelăm respectiva funcție.
De exemplu dorim ca trecerea de la nivelul 1 la nivelul 2 de prelucrarea a datelor să semnifice
ștergerea primului rând din cadrul documentelor din colecție. Nu ne rămâne de facut decât să
implementam o funcție care ia ca parametru un director, și parcurgând-ul șterge câte o linie din
fiecare fișier. Apoi, dupa ridicarea de nivel, efectuam o verificare, în cazul în care noul nivel este
2 apelăm funcția implementată anterior.

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 38
În cazul particularizării noastre, nu este nevoie decât de o singură operație și anume aceea de
indexare a fișierelor. Astfel putem asocia startul indexării datelor cu ultima ridicare de nivel,
pentru a acorda cât mai mult timp, altor eventuali peeri care doresc sa se conecteze la rețea.
Aceasta deoarece procedura de conectare dureaza mult mai puțin decât cea de indexare, un
eventual numar mai mare de membri ai rețelei fiind mai benefic din punct de vedere al timpului
consumat. Putem trage concluzia că, în cazul particularizărilor de sistem ce necesită mai multe
prelucrări de date a caror ordine de efectuare nu contează, cele ce necesită timpi mai mari de
execuție ar trebui asociați cu ultimele ridicări de nivel.
Indexarea colecției locale a peer-ului s-a realizat prin extragerea câmpurilor semnificative pentru
identificarea unui patent de invenție. Astfel s-a creat un index local, în interiorul căruia a fost
adăugat pentru fiecare fișier câte un document cu urmatoarele câmpuri:
number – Reprezintă numărul patentului. Acesta este unic, putând fi folosit pe post de
identificator
invention-title – Reprezită titlurile existente, acest câmp fiind cel mai important în cadrul
identificarii de compatibilităti.
abstract – Reprezintă o scurtă descriere care poate apare sau nu în text, ce conține în
majoritatea cazurilor cuvinte cheie.
description – Este o descriere de dimensiuni mai mari, care în cazurile în care câmpul
abstract există poate fi omisă.
claims – Acest câmp furnizează informații legate de drepturile de utilizare a invenției,
putându-ne ajută să identificăm eventualele incompatibilități.
În cazul ultimului modul sistemul de bază ne permite ca solicitantul să poată trimite un șir de
caractere care să reprezinte practic o interogare, iar peer-ul care execută interogarea să trimită
înapoi un șir de caractere care să reprezinte rezultatul. Aceste capabilități pot fi adaptate ușor
pentru a putea efectua o verificare ce să stabilească dacă o anumită aplicație de patent este validă
sau nu.
Încercarea de identificare dacă o anumită aplicație de patent este validă, se efectuează tot cu

Capitolul III – Particularizarea sistemului – CLEF-IP 2010 39
ajutorul bibliotecii Lucene. În momentul în care un anumit nod din rețea dorește să efectueze o
operație de căutare, el extrage cuvintele cheie din cadrul câmpurilor importante ale aplicației de
verificat, și realizează o interogare Lucene pe care o trimite apoi, nodurile aflate în vecinătate din
cadrul rețelei.
Dacă un peer recepționează la un moment dat o comandă de căutare, preia interogarea primită
prin intermediul cererii/comenzii și o efectuează pe indexul parțial deținut local. Asamblează
numarele patentelor obținute în urma interogării (dacă este cazul) după standardul final și trimite
rezultatul nodului ce a inițiat căutarea.
III.4 Concluzii
Adaptarea sistemului general, la un caz particular de sistem de procesare a datelor, se poate
efectua cu ușurință, fiind nevoie doar de crearea sau preluarea funcțiilor specifice de prelucrarea a
datelor și de adaptarea operațiilor de procesare astfel încât să fie compatibile cu sistemul de
comunicare dintre peeri – mesaj → răspuns.
În cazul sarcinii propuse de CLEF-IP 2010 s-a realizat un sistem compus din 20 de calculatoare
fiecare dintre ele deținând a parte din colecția de documente propusă. Prin conectarea lor, unul la
altul, s-a realizat inițial o structura arborescentă, structură în interiorul căreia s-a efectuat
procedura de indexare a datelor. În cadrul acesteia s-au preluat de la fiecare document cele mai
importante informații, fiecare nod al rețelei depunând aceste informații într-un index local.
Determinarea compatibilității unui patent de invenție cu toate documentele din colecție se poate
face dupa finalizarea procedurii de indexare de către orice nod din sistem.
Prin folosirea sistemului distribuit, timpul necesar indexării și căutarii a fost imbunătățit
semnificativ. Dacă în cadrul competiției CLEF-IP 2009 indexarea unei colecții de 35 de Gb pe un
singur calculator a consumat aproximativ 7 ore, prin intermediul sistemului distribuit timpul
procesarii unei colecții de 85 de Gb a fost redus la o ora și jumatate.

Concluzii 40
Concluzii și Posibilități de dezvoltare
Domeniul informaticii se confruntă în ultima perioadă de timp cu tot mai multe probleme în ceea
ce privește prelucrarea și procesarea de date. Resursele, de cele mai multe ori limitate, ale
calculatoarelor nu reușesc să satisfacă situațiile, din ce în ce mai dese, în care se impune lucrul cu
colecții foarte mari de documente.
În cadrul aceste lucrări este prezentată arhitectura și implementarea unui sistem distribuit de
prelucrarea și procesare a datelor. Structura sa este una generalizată cu scopul de a permite
viitoare dezvoltari dar și diverse particularizări efectuate în diverse scopuri de procesare.
Accentul este pus pe legăturile realizate în cadrul rețelei, și pe managerierea cât mai bună a
comunicațiilor întreprinse între nodurile sistemului. Deasemenea pentru a câștiga în eficiență, se
încearcă ca la fiecare moment, orice nod al rețelei să efectueze pe cât posibil aceeași operație, fie
ea de prelucrare sau procesare de date.
Sistemul este alcătuit din 3 module de bază: modul de conectare, modulul de prelucrarea a datelor
și modulul de procesare a datelor. Primul modul se ocupă de creerea legăturilor dintre peerii
membri ai rețelei, și de schimbul de informații necesar pentru rularea urmatoarelor module. Al
doilea modul se ocupă de prelucrarea sincronizată a datelor efectuată în cadrul rețelei. Astfel
sistemul gestionează execuțiile funcțiilor de prelucrarea, astfel încât la un moment dat aceași
funcție să fie rulată de toate calculatoarele membre ale rețelei. În cadrul celui de-al treilea modul
se execută diverse proceduri de procesare a datelor anterior prelucrate. O anumită operație poate
fi pornită de către orice nod al rețelei, celorlalte fiindu-le comunicat tipul operației, eventualii
parametri dar și emițătorul astfel încât acesta din urmă să primescă direct toate rezultatele
parțiale.
În urmatoare parte a lucrării este descris modelul realizat prin intermediul rețelelor Petri de tip P/
T pentru sistemul mai sus amintit. Prin simularile efectuate pe acest model se pot observa și

Concluzii 41
demonstra diverse caracteristici ale rețelei asa cum ar fi: imposibilitatea conectarii unui număr
mai mare de peeri decât cel specificat inițial, structura liniară a primelor două module, diferențele
de prelucrare în cele două cazuri ale naturii peerilor, capacitatea de efectuare într-un numar
multiplu al operațiilor de procesare.
Partea finală prezintă modalitatea în care sistemul poate fi particularizat pentru o problemă
specifică. Drept exemplu este aleasă sarcina de căutare „Priot Art” propusă de CLEF-IP 2010, în
cadrul competiției de evaluare a accesului multilingv și multimodal al informației – CLEF 2010.
Ca posibilități viitoare de dezvoltare ale sistemului, s-ar putea propune lărgirea orizonturilor în
ceea ce privește comunicarea în cadrul rețelei. Dacă în momentul de față, sistemul este ideal
pentru o rețea de calculatoare locală, diverse probleme ar putea apărea în cadrul realizării unei
rețele în care membrii ei să comunice de la distanțe mari. Ar trebui prevăzute, și tratate situații
cum ar fi deconectarea unui peer, din cauza unor probleme de comunicare apărute la un moment
dat sau transmiterea bucăților mari de informație prin protocoale specializate.
Deasemenea, diverse îmbunătățiri ar putea fi efectuate, la nivelul modulului de prelucrare a
datelor. În acest moment, fiecare nod al rețelei trebuie să aibă copiată, local, o parte a colecției de
documente. Pentru a elimina neplăcerile cauzate de eventualele dificultăți în timpul copierii
datelor, s-ar putea face o automatizare a acestui proces. De exemplu toată colecția este copiată pe
un server ftp, iar în momentul conectării unui peer, acestuia îi este dată adresa serverului de unde
își poate descărca singur o anumită parte de date.
În cazul procesărilor lingvistice, ar putea fi oferite diverse unelte pentru a ușura prelucrarea. De
exemplu ar putea fi realizat un sistem care oferă prin conectarea la internet și utilizarea API-urilor
Google Translate, traducerea unui șir de caractere. Sau ar putea fi oferită semnificația unui cuvânt
folosind diverse API-uri (Google, Wikipedia).
Domeniul sistemelor distribuite este unul de actualitate, reprezentând o direcție certă de
dezvoltare a procesării informației. Dezvoltarea în ritm accelerat atât a dimensiunilor datelor de

Concluzii 42
care suntem înconjurați cât și a dorinței de cunoaștere și comunicare a lor într-un timp cât mai
rapid, depășește din ce în ce mai mult progresul tehnologic. Dacă există un răspuns în rezolvarea
acestei probleme acesta este unul singur: folosirea sistemelor distribuite.

Contribuții 43
Contribuții
Contribuțiile personale aduse la prezenta lucrare de catre autorul său sunt urmatoarele:
Adaptarea arhitecturii peer-to-peer, cu scopul de a crea un suport ce să satisfacă nevoile
realizării unei rețele de procesare a datelor.
Crearea algoritmului distribuit necesar pentru implementarea sistemului distribuit.
Implementarea în limbaluj C# a sistemului general de prelucrare și procesare de date.
Modelarea sistemului cu ajutorul Rețelelor Petri de tip P/T.
Analizarea caracteristicilor sistemului rezultate în urma observațiilor întreprise în
simularea efectuată asupra modelului creat.
Adaptarea și particularizarea sistemului pentru a rezolva sarcina propusă în cadrul
competiției CLEF-IP 2010
În final ași dori să le multumesc colegilor mei din grupa 5A pentru tot ajutorul oferit în cadrul
proiectului CLEF-IP 2009. Deasemena îi mulțumesc Dm. Asist. Dr. Adrian Iftene pentru toate
sfaturile și ideile constructive, oferite de-a lungul colaborării noastre. Nu în ultimul rând îi
mulțumesc familiei mele pentru tot sprijinul oferit.

Bibliografie 44
Bibliografie
1.Andrews, Gregory R. (2000): Foundations of Multithreaded, Parallel, and Distributed
Programming, Addison–Wesley.
2.Arora, S.; Barak, B. (2009): Computational Complexity – A Modern Approach.
3.Cole, R.; Vishkin, U.(1986): Deterministic coin tossing with applications to optimal
parallel list ranking.
4.Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990): Introduction to
Algorithms (1st ed.).
5.Filman, R. E., Friedman D. P. (1984): Coordinated Computing: Tools and Techniques for
Distributed Software .
6.Godfrey, B(2002): A primer on distributed computing.
7.Goldreich, O. (2008): Computational Complexity: A Conceptual Perspective.
8.Hatcher, E. and Gospodnetic, O. (2005): Lucene in action. Manning Publications Co .
9.Herlihy, M. P.; Shavit, N. N. (2008): The Art of Multiprocessor Programming.
10.Iftene, A. (2007). Building a Computational Grid Using P2P Networks.
11.Iftene, A., Croitoru, C. (2006): Graph Coloring using Peer-to-Peer Networks.
12.Iftene, A., Ionescu, O., Oancea, G.R., Balmoș, A.D. (2009): UAIC: Participation in
CLEF-IP Track.
13.Jucan, T., Țiplea, F.L. (1995): Retele Petri.
14.Jucan, T., Țiplea, F.L. (1998): Retetele Petri. Teorie si aplicatii.
15.Lynch, Nancy A. (1996): Distributed Algorithms, Morgan Kaufmann .
16.Papadimitriou, C. H. (1994): Computational Complexity, Addison–Wesley.
17.Piroi, F., Roda, G., Zenz, V . (2009): CLEF-IP 2009 Evaluation Summary
18.Reisig, W. (1998): Elements of Distributed Algorithms. Modeling and Analysis with Petri
Nets.
19.Schollmeier R. (2002): A Definition of Peer-to-Peer Networking for the Classification of
Peer-to-Peer Architectures and Applications.
20.Taubenfeld, Gadi (2006): Synchronization Algorithms and Concurrent Programming.