2013

Arhitecturi si modele ale SD

Capitolul 2

2013

Tipuri de modele

• Modele fizice

– Descriu componentele hardware ale unui SD in termenii dispozitivelor de calcul (calculatoare, telefoane mobile, etc.) si retelelor deinterconectare.

• Modele arhitecturale

– Simplifica si abstractizeaza tipurile componentelor si a functiilor lor.

– Defineste componentele SD, modul in care ele interactioneaza (roluri functionale si sabloane de comunicare / interactiune) si modul lor de mapare pe reteaua de comunicatie a unui SD

• Modele fundamentale

– Modele de interactiune

– Modele ale erorilor

– Modele de securitate

2013

Generatii de SD I

• Model fizic de baza:

– Infrastructura de retea

– Comunicare prin mesaje

• SD timpurii:

– Aparute ca raspuns la dezvoltarea tehnologiei LAN

– Gama redusa de servicii: partajare imprimanta, fisiere; email; transfer de fisiere

– Opereaza la nivel intra-organizational

– Calitatea serviciului in stadiu embrionar

2013

SD in Internet• Aparute la inceputul anilor ’90 prin raspandirea Internet-ului ca retea de retele.

• Ofera servicii la nivel global, inter-organizational

• Eterogenitatea este mare => s-au dezvoltat standardele (ex. Servicii Web)

• S-a urmarit asigurarea calitatii serviciilor

• Internet-ul este o multime de retele(sisteme) autonome interconectate printr-o retea de baza – core network saubackbone.

• In telecomunicatii retelele autonome se mai numesc retele de acces – access networks.

• Retelele autonome se conecteaza la reteaua de baza prin porti externe –exterior gateway.

• Retelele aotonome se interconecteazaintre ele prin porti interne – interior gateways.

2013

SD contemporane

• Noi tendinte datorate raspandirii calcului mobil (dispozitive portabile), calculului ubicuu (raspandirea resurselor de calcul cu costuri din ce in ce mai scazute), calculului in cloud (utility computing si virtualizare) si a arhitecturilor cluster.

• Ex. Internet of Things: obiecte identificabile si reprezentarile lor virtuale.

2013

Sumar al generatiilor de SD

2013

Sisteme de SD

• In 2006 Linda Northrop a propus intr-un raport al SEI – Software Engineering Institute termenul de ULSS – Ultra-Large-Scale System.

• ULSS au urmatoarele caracteristici:– Compuse din sisteme independente dpdv operational si

– administrativ

– Dezvoltate printr-un proces evolutiv

– Au comportament emergent (de exemplu facilitati de

autonomie, autoconfigurare si autoorganizare – proprietati self-*)

– Distinctia intre utilizatorii si sistem este estompata, oamenii devenind componente desistem si furnizori de servicii, putand influenta comportamentul emergent al sistemului (ex. – actor-agent systems, human-based computation, crowdsourcing).

• Exemplu: sistem de management al mediului si predictie a dezastrelor naturale (ex. inundatii). Integreaza:– Sisteme de senzori pentru monitorizarea diversilor parametrii ai mediului (de

exemplu debitul raurilor, cantitatea de precipitatii, etc.)

– Sisteme de simulare pentru predictia unor evenimente neasteptate (cantitati mari de precipitatii, topirea masiva a zapezii, etc.)

– Sisteme de avertizare timpurie a populatiei

2013

Modele arhitecturale

• Cele trei fatete ale unui model arhitectural:

– Elementele arhitecturale de baza ale unui SD

– Sabloane arhitecturale (engl. architectural patterns) utilizate separat sau in combinatie pentru dezvoltarea SD

– Platforme middleware disponibile pentru diverse stiluri de programare a SD

2013

Elemente arhitecturale

• Elementele arhitecturale:

– Entitatile comunicante din care este compus un SD.

– Paradigmele de comunicareale entitatilor unui SD.

– Rolurile si responsibilitatile(statice sau dinamice) entitatilor unui SD.

– Maparea entitatilor pe infrastructura fizica distribuita a SD (plasamentul lor).

2013

Entitati comunicante

• Din perspectiva sistemica, entitatile comunicante intr-un SD sunt procese.

• Exista doua exceptii de la aceasta regula:

– In medii cu capabilitati de calcul restranse, cum sunt retelele de senzori, SO si / sau software-ul de baza nu suporta conceptul de proces, caz in care entitatile comunicante sunt noduri.

– In majoritatea SD moderne, conceptul de proces este suplimentat cu conceptul de fir (engl. thread), acesta reprezentand de fapt un punct final al unei interactiuni.

• Din perspectiva programatica, entitatile comunicante ale unui SD pot fi:

– Obiecte

– Componente

– Servicii

2013

Obiecte

• Obiecte:

– Un SD este format dintr-o multime de obiecte distribuite interactive.

– Ele sunt accesate prin intermediul unor interfete definite printr-un IDL – Interface Definition Language.

• Exemplu: interfata Remote din Java RMI.

• Codul obiectelor se distribuie prin intermediul claselor.

• Crearea unui obiect prin refolosirea unei biblioteci de clasepresupune:

– programare (coding)

– compilare

2013

Componente

• Componente: – O componenta specifica (in plus fata de interfete)

dependentele fata de componentele si interfetele ce trebuie sa fie prezente pentru ca ea sa-si poata realiza functia.

– Au un grad mai mare de reutilizabilitate decat obiectele. Este posibila construirea unei aplicatii din componente existente (prefabricate), similar cu modul in care un inginer construieste un ansamblu folosind module prefabricate.

– Sunt conforme unui model de componenta ce defineste modul lor de interactiune, compunere, configurare, implementare, documentare si instalare (engl. deployment).

– Ex: EJB – Enterprise Java Beans, COM+ (.NET), CORBA, FIPA si JADE (agenti software), Open Services Gateway initiative (OSGi, Equinox Eclipse project).

2013

Servicii

• Servicii:

– Se bazeaza pe i) abstractizarea comportamentului si ii) accesul printr-o interfata.

– Serviciile se bazeaza pe protocoale standard de interactiune si de descoperire.

– Incurajeaza dezvoltarea aplicatiilor prin cuplaj slab ce pot depasi granitele unei singure organizatii. Obiectele si componentele se folosesc pentru dezvoltarea de aplicatii cu cuplaj strans, uzual in cadrul aceleiasi organizatii.

• Exemple:

– Serviciile Web, bazate pe standardele Web: HTTP si XML.

– Arhitectura orientata pe servicii – service oriented architecture, SOA.

2013

Paradigme de comunicare

• Trei paradigme:

– comunicare intre procese,

– invocare la distanta,

– comunicare indirecta.

• Comunicare intre procese:

– Suport pentru comunicare intre procese intr-un SD.

– Primitive pentru transfer de mesaje

– API pentru acces la primitivele de comunicare intre procese (ex. comunicare prin socluri)

Entitate A Entitate B?

2013

Invocare la distanta

• Invocare la distanta:

– Protocoale cerere – raspuns (engl. Request-Reply). Reprezinta o tehnica de comunicare prin schimb de mesaje in arhitecturile client – server. Un exemplu este protocolul HTTP pentru aplicatiile Web.

– Apel de proceduri la distanta (engl. Remote Procedure Call – RPC). Presupune apelul de proceduri aflate in alt spatiu de adrese decat apelantul (in alt proces) similar cu apeluri locale.

– Invocare de metode la distanta (engl. Remote Method Invocation – RMI). Este extensia RPC pentru programarea orientata pe obiect.

2013

Comunicare indirecta I

• Comunicarea indirecta decupleaza expeditorul de receptor:– Decuplare spatiala

– Decuplare temporala

• Exista o multime de paradigme pt comunicare indirecta.

• Comunicatie de grup– Permite livrarea unui mesaj de la un expeditor la o multime de expeditori, adica

avem un sablon de comunicare unu-multi.

– Se bazeaza pe existenta abstractiei de grup. Un grup este reprezentat printr-un identificator de grup.

– Receptorii se pot inscrie sau pot parasi dinamic un grup.

– Grupul este responsabil cu gestiunea membrilor sai.

• Publicare-inscriere (engl. Publish-subscribe)– Numeroase sisteme (cel din domeniul financiar) disemineaza informatie.

– Intr-un astfel de sistem, un numar mare de producatori (engl. publishers) ce distribuie elemente informationale, numite si evenimente catre un numar mare de consumatori (engl. subscriber).

– Acest mod de comunicare permite livrarea efeicienta a informatiei de la producatori catre consumatorii interesati.

2013

Comunicare indirecta II

• Cozi de mesaje– Ofera un serviciu punct-la-punct (engl. point-to-point).

– Expeditorii trimit mesaje catre o coada de mesaje, in timp ce receptorii sunt instiintati ori de cate ori un mesaj este depus in coada respectiva.

– Receptorii au facilitatea de filtrare explicita a mesajelor de interes din coada folosind sabloane (engl. patterns). Se poate filtra atat dupa continut, cat si dupa expeditor.

• Spatii de tuple– Mesajele sunt reprezentate prin date structurate numite tuple.

– Comunicarea intre procese se realizeaza indirect prin spatii persistente de tuple.

– Procesele pot depune tuple in spatiul de tuple, iar alte procese le pot citi sau elimina folosind filtre sau sabloane.

– In inteligenta artificiala se cunoaste modelul blackboard, ce reprezinta o baza de cunostinte partajata folosita pentru rezolvarea colaborativa de probleme, similar unui proces de brainstroming.

• Memorie partajata distribuita– Se bazeaza pe furnizarea unei abstractii a conceptului de memorie partajata (sau

comuna, engl. shared).

– Procesele pot scrie respectiv citi din memoria partajata ca si cum aceasta ar fi parte a spatiului lor de adrese.

2013

Roluri si responsabilitati

• Procesele unui SD interactioneaza si se coordoneaza pentru realizarea unor activitati complexe.

• Adoptand o metafora organizationala, procesele unui SD indeplinesc diverse roluri si responsabilitati predefinite, ce impreuna definesc stilul arhitectural al SD.

• In functie de rolurile proceselor componente, deosebim doua mari stiluri arhitecturale ale SD:

– Modelul client-server

– Modelul proceselor de acelasi rang (engl. peer-to-peer – P2P).

2013

Modelul client/server

• Cel mai citat in literatura SD, cel mai important dpdv istoric si cel mai folosit.

• Exemple:

– Un server Web poate fi client al unui server local de fisiere

– Serverele Web si alte servicii Internet sunt clienti pentru un serviciu de DNS care traduce numele de domenii Internet in adrese de IP

– Un motor de cautare (engl.search engine) permite utilizatorilor sa caute informatii despre paginile Web intr-un index local, construit cu ajutorul unui program robot numit Web crawler. Astfel motorul este in acelasi timp server pentru utilizatorii care-l consulta si client ce foloseste HTTP sa-si construiasca indexul prin intermediul Web crwaler-ului.

• Critica a modelului client/server:

– Distinctia server ≠ client da un grad de centralizare. Server-ul este punct de strangulare in SD.

Server

Client

Client

invocation

result

Serverinvocation

result

Process:Key:

Computer:

2013

Procese de acelasi rang (pereche, engl.peer)

• O aplicatie P2P este compusa dintr-un numar mare de procese peer ce comunica conform cerintelor aplicatiei.

• Procesele au roluri identice (nu exista distinctia client ≠ server) si coopereaza pt a realiza distribuit o sarcina. Fiecare proces este responsabil cu mentinerea consistentei resurselor aplicatiei si cu sincronizarea.

• O aplicatie P2P contine obiecte partajate si replicate astfel incat sa se eficientizeze procesarea si comunicarea.

• Modelul P2P foloseste o retea la nivel de aplicatie (engl. overlay network) construita peste o retea de calculatoare existenta.

• Se foloseste in contextul globalizarii economice, oferind companiilor metode noi de a-si imbunatati puterea de calcul cu investitii minime in resurse hard si soft.

• Exemplu: Sistemul BitTorrent pentru partajarea distribuita a fisierelor.

2013

Plasament

• Defineste plasamentul entitatilor (procese, obiecte, servicii) in cadrul infrastructurii fizice a unui SD.

• Plasamentul este o problema de proiectare si va lua in calcul:

– Sabloanele de interactiune ale entitatilor SD

– Fiabilitatea masinilor si nivelul lor de incarcare

– Calitatea liniilor de comunicatie

• Plasamentul depinde si de aplicatie. Exista cateva reguli generale care pot conduce la solutii bune.

– Maparea serviciilor pe servere multiple

– Caching

– Mobilitate (cod mobil si agenti mobili)

2013

Servicii furnizate de servere multiple

• Web-ul este un exemplu de partitionare a datelor a.i. fiecare server de Web isi gestioneaza o multime proprie de pagini Web.

• Un serviciu distribuit de directoare permite cautarea unor entitati dupa nume intr-o retea. Exemple: DNS, LDAP, etc. Un astfel de serviciu consta dintr-o multime de servere interconectate si un protocol de comunicare al clientilor cu serverele.

Server

Server

Server

Service

Client

Client

• Serviciile pot fi implementate sub forma unei multimi de procese server ce ruleaza pe diverse calculatoare gazda si interactioneaza corespunzator

• Procesele server pot sa:– partitioneze multimea obiectelor pe

care se bazeaza serviciul si sa le distribuie intre ele sau

– sa mentina copii replicate ale acestora pe mai multe calculatoare gazda.

2013

Servere proxy si memorii cache

• O memorie cache stocheaza datele recent folosite, mai aproape (spatial sau temporal) de procesul client care le-a folosit decat locul unde sunt ele stocate in mod normal. Cand un nou obiect este receptionat el va fi stocat in cache, posibil inlocuind alte obiecte existente. Cand un obiect este cerut de un client el va fi intai cautat in cache de serviciul de cache si furnizat de acolo in cazul existentei unei copii actualizate. Altfel se va extrage o copie actualizata de la sursa normala. Memoriile cache pot fi alocate fiecarui client in parte sau pot fi alocate in servere proxy partajate de mai multi clienti.

• Exemple:

– Navigatoarele Web mentin o memorie cache a paginilor recent vizitate si a altor resurse Web, in sistemul de fisiere al clientului. Se foloseste o cerere speciala HTTP pentru a cauta o pagina in cache inainte de a o aduce de pe Web. Un server Web proxy furnizeaza o memorie cachepentru clientii dintr-un site sau mai multe site-uri.

– Un server proxy poate avea si alte roluri, de exemplu accesul la Web print-un firewall.

Client

Proxy

Web

server

Web

server

serverClient

2013

Cod mobil - 1

• Conceptele de baza privind codul mobil sunt discutat foarte clar in lucrarea: Alfonso Fuggeta, Gian Pietro Picco, Understanding Code Mobility, IEEE Transaction on Software Engineering, vol.24, no.5, pp.342-361, 1998.

• Autorii au identificat 4 paradigme de baza pentru codul mobil: – i) client/server,

– ii) evaluare la distanta (engl. Remote Evaluation)

– iii) cod la cerere (engl. Code on Demand)

– iv) agent mobil (engl. Mobile Agent)

• Exemplu: Luiza si Cristina prepara o prajitura.

• Client/server: Luiza doreste prajitura dar nu stie sa o prepare, nu are ingrediente si nici cuptor unde sa o coaca. Din fericire ea stie ca prietena sa Cristina stie reteta prajiturii si are o bucatarie corespunzatoare (cuptor si ingrediente). Luiza ii cere Cristinei sa-i faca prajitura. Aceasta o prepara si o livreaza Luizei.

2013

Cod mobil - 2

• Evaluare la distanta: Luiza doreste prajitura, stie reteta, dar nu are nici cuptor, nici ingrediente. Cristina are la ea acasa atat cuptor cat si ingrediente, dar nu cunoaste reteta. Din fericire Luiza stie ca prietena sa Cristina este bucuroasa sa incerce noi retete. Astfel ii da telefon Cristinei si ii spune reteta. Cristina foloseste reteta sa prepare prajitura si apoi o livreaza Luizei.

• Cod la cerere: Luiza doreste sa prepare prajitura, are la ea acasa atat ingrediente cat si cuptor, dar nu stie reteta. Din fericire Luiza stie ca prietena sa Cristina stie reteta prajiturii pe care a imprumutat-o deja la numerosi prieteni. Luiza ii telefoneaza Cristinei pentru a-i imprumuta reteta. Cristina ii spune reteta Luizei, iar Luiza prepara prajitura la ea acasa.

• Agent mobil: Luiza doreste sa prepare prajitura, stie reteta, are ingredientele, dar nu are cuptor. Din fericire Luiza stie ca prietena sa Cristina are la ea acasa un cuptor pe care este bucuroasa sa-l imprumute. Astfel Luiza prepara coca prajiturii si apoi merge la Cristina acasa pentru a coace prajitura.

2013

Cod la cerere - exemplu

2013

Variatii ale modelului client/server

• Miniaplicatiile (engl.applet) sunt exemple de cod mobil. Ele sunt descarcate de pe un server Web si rulate in programul navigator. Sunt utille atunci cand interactiunea client-server trebuie initiata de server (engl.push model), cum este cazul informarii automate a clientilor despre schimbarile din sursele de informatie de pe server.

• Exemplu: un agent de bursa poate furniza un serviciu de informare a clientilor sai despre modificarile preturilor.

a) client request results in the downloading of applet code

ClientWeb

serverApplet

Web

serverApplet code

Client

b) client interacts with the applet

2013

Sabloane arhitecturale

• Reprezinta schema unei structuri compusa din elemente arhitecturale care este utila in proiectare in diverse situatii.

• Stratificare (engl. layering)

• Multi-nivel (engl. multi-tier sau tiered)

• Clienti “subtiri” (engl. thin clients)

• Alte sabloane arhitecturale:

– Delegat (engl. proxy)• Se foloseste pentru a realiza transparenta locatiei in apelurile la distanta. In acest

caz pentru un obiect la distanta se creaza un obiect proxy cu o interfata similara cu cea a obiectului la distanta in spatiul local de adrese al apelantului.

– Intermediar (engl. broker)

– Reflexie (engl. reflection)• Permite descoperirea si configurarea dinamica a proprietatilor, structurii si

comportamentului unui sistem, la nivelul interfetelor si componentelor sale. Este un sablon util pentru configurarea dinamica a unei arhitecturi middleware.

2013

Stratificare

• Un sistem complex este partitionat sub forma unui numar de straturi(engl. layer). Fiecare strat realizeaza un anumit nivel de abstractizare.

• Fiecare strat foloseste serviciile oferite de stratul inferior. Astfel ca un strat ofera o abstractizare software, ascuzand detaliile de implementare straturilor superioare.

Applications, services

Computer and network hardware

Platform

Operating system

Middleware

2013

Multi-nivel

• Spre deosebire de stratificare, ce presupune organizarea pe verticala a unui SD sub forma unei multimi de straturi, o arhitectura multi-nivel este o modalitate complementara de organizare functionala a unui strat. Functionalitatile sunt asignate unor servere si eventual unor noduri fizice.

• La nivel conceptual o aplicatie se poate descompune functional din trei nivele logice:

– Logica prezentarii

– Logica aplicatiei

– Logica datelor

client

logica prezentarii

logica datelor

logica aplicatiei

s istem d

i st ribiut

2013

SD multi-nivel

Logica prezentarii

Logica aplicatiei

Logica datelor

Suport pentru clienti multipli

Separarea logicii aplicatiei Combinatie arbitrara

Distribuirea si replicarea datelor

2013

SD cu doua nivele

2013

SD cu trei nivele

2013

Clienti “subtiri”

• Tendinta in SD este de mutare a complexitatii de la dispozitivul utilizatorului catre servicii din Internet – vezi cloud computing.

• Conceptul de thin client se refera la un nivel software de implementare a unei interfeteutilizator bazata pe ferestre pe un calculator local, in timp ce partea mai consistenta a aplicatiei se executa pe un calculator la distanta. Aplicatia nu se descarca local, ci se ruleaza pe server. Avantajul este ca dispozitive cu capabilitati restranse pot fi imbunatatite cu servicii de retea. Dezavantajul este ca in aplicatiile puternic interactive timpul de raspuns va creste datorita volumului mare de informatii transmise intre client si server. Este important nivelul de separare intre client si server.

• Acest concept a condus la aparitia virtual network computing – VNC. Un client VNCinteractioneaza cu un server VNC prin intermediul protocolului VNC ce opereaza la nivel de primitive grafice. Abordarea garanteaza independednta fata de sistemul de operare.

2013

Alte sabloane - broker

• Suporta interoperabilitatea in SD complexe prin identificarea dinamica a unui serviciu solicitant (engl. service requester) cu un serviciu furnizat (engl. service provider) cu ajutorul unui servicu de intermediere (engl. service broker).

• Se foloseste in serviciile Web, RMI, CORBA, FIPA, etc.

2013

Platforme middleware

FIPA, http://www.fipa.org/Standard IEEEMulti-Agent

JADE, http://jade.tilab.com/Platforma Multi-Agent

BitTorrent, http://www.bittorrent.com/Aplicatie pentru partajare

de fisiere

Chimera, http://current.cs.ucsb.edu/projects/chimera/Routing overlay

Pastry, http://www.freepastry.org/Routing overlayP2P

Globus ToolkitServicii Grid

Apache AxisServicii WebServicii

Java Message Service, JMS-Cozi de mesaje

CORBA Event Service-

Java Message Service, JMS-Publicare-

inscriere

CORBA Component Model, CCMComponente pentru server

Enterprise JavaBeans, EJBComponente pentru server

(engl. server-side)

Fractal, http://fractal.ow2.org/Model de componenteComponente

distribuite

Java RMIPlatforma

Common Object Request Broker Architecture, CORBAstandard OMG si platforma

Reference Model of Open Distributed Processing, RM-ODPStandard ISO Obiecte distribuite

2013

Modele fundamentale ale SD I

• Modelele fundamentale ale SD se ocupa cu descrierea formala a proprietatilor comune tuturor modelelor arhitecturale, oferind o viziune abstracta asupra acelor caracteristici ale SD care afecteaza:

– Corectitudinea

– Fiabilitatea

– Securitatea

sistemelor distribuite.

• Modelul de interactiune

• Modelul defectelor

• Modelul de securitate

2013

Modele fundamentale ale SD II

• Modelul de interactiune

• Procesele unui SD interactioneaza prin mesaje in scopul realizarii comunicarii si coordonarii. Livrarile mesajelor si pasii de calcul pot fi afectate de intarzieri considerabile. Aceste intarzieri conduc la dificultatea mentinerii unui timp global si limiteaza acuratetea cu care procesele pot fi coordonate. Se bazeaza pe algoritmi distribuiti.

• Modelul defectelor

• Este o descriere a defectelor ce pot aparea in cadrul proceselor si canalelor de comunicatie ale unui SD. Acest model ofera o baza pentru analiza efectelor potentiale ale acestor defecte si pentru proiectarea unor SD capabile sa tolereze aceste defecte, astfel incat sa isi poata continua functionarea corecta.

• Modelul de securitate

• Prezinta amenintarile posibile asupra proceselor si canalelor de comunicatie. El ofera o baza pentru analiza acestor amenintari si pentru proiectarea SD capabile sa reziste la ele.

2013

Modelul de interactiune

• Un SD se compune dintr-o multime de procese ce ruleaza independent, posibil pe calculatoare diferite si interactioneaza in maniera complexa.

• Comportamentul unui SD se descrie printr-un algoritm distribuit. El defineste multimea pasilor care se executa de fiecare proces al SD in parte, incluzand si schimburile de mesaje dintre acestea.

• Caracteristic unui SD sunt: – i) ratele de executie ale fiecarui proces in parte si timpii necesari transmisiei de

mesaje nu sunt in general predictibili fiind afectati de incertitudini;

– ii) descrierea tututuror starilor posibile este dificila deoarece ar trebui luate in considerare toate erorile din cadrul proceselor de calcul si a canalelor de comunicatie.

• Factori de incertitudine ce influenteaza interactiunea proceselor unui SD: – i) performanta limitata a comunicatiei;

– ii) imposibilitatea mentinerii unui ceas global unic.

2013

Performanta canalelor de comunicatie

• Comunicatia in reteaua de calculatoare a unui SD se caracterizeaza prin:

– latenta (engl.latency)

– largime de banda sau capacitate (engl.bandwidth sau throughput) si

– variatie temporala (engl.jitter).

2013

Latenta

• Latenta = intarzierera dintre trimiterea unui mesaj de catre un proces expeditor si receptionarea sa de catre procesul receptor. Latenta include:

– Intarzierea intrinseca a canalului de comunicatie, datorata limitarilor sale fizice.

– Intarziererea cauzata de accesul la retea; creste cu cat reteaua este mai incarcata.

– Timpul de acces la serviciile de comunicatie ale sistemelor de operare expeditor si receptor; creste cu cat sistemele sunt mai incarcate.

2013

Largimea de banda

• Largimea de banda = cantitatea totala de informatie utila ce poate fi transmisa in unitatea de timp.

• Daca mai multe canale de comunicatie partajeaza o aceeasi legatura de comunicatie, ele vor partaja de asemenea si largimea de banda a canalului respectiv

2013

Variatia temporala

• Variatia temporala = variatia in timpul necesar transmiterii unei secvente de mesaje.

• Aceasta variatie este relevanta pentru transmisia datelor multimedia.

• De exemplu, daca o secventa de esantioane de date audio sunt redate cu cuante de timp diferite atunci sunetul rezultat va fi puternic distorsionat.

2013

Ceasuri

• Fiecare calculator al unui SD are un ceas local. Procesele ce ruleaza pe calculatoare diferite vor asocia marcaje de timp evenimentelor pe baza ceasurilor locale. Chiar daca citirea ceasurilor locale s-ar face in acelasi moment de timp, se vor obtine valori diferite, deoarece:

– Fiecare ceas are un decalaj (engl.drift) fata de ceasul real

– Decalajele ceasurilor sunt diferite

• Rata de deplasare a unui ceas (engl.clock drift rate) reprezinta deplasamentul relativ al ceasului fata de un ceas de referinta perfect. Chiar daca toate ceasurile unui SD ar fi setate la aceleasi valori initiale, ele pot varia in timp, fiind necesare corectii regulate.

2013

Corectia ceasurilor

• Corectia ceasurilor se poate realiza prin citirea periodica a timpului curent prin radio sau de la un sistem global de pozitionare (engl.Global Positioning System – GPS) cu o acuratete de aproximativ 1 µs. Dar GPS-urile nu pot functiona in cladiri si sunt costisitoare.

• Alternativa este ca un calculator cu acces la un GPS sa trimita regulat mesaje de timp celorlalte calculatoare din retea. Insa aceste valori vor fi desigur afectate de intarzierile de livrare a mesajelor in retea.

• SD furnizeaza servicii de timp necesare pentru sincronizare in timp, in anumite limite de acuratete. Un exemplu este NTP –Network Time Protocol.

2013

Variante ale modelului de interactiune

• Exista doua variante:

– SD sincrone

– SD asincrone

• Distinctia intre sincron si asincron se face dupa doua coordonate:

– Existenta / inexistenta ceasului global

– Predictibilitatea / nepredictibilitatea intarzierilor de comunicatie.

2013

SD sincrone

• SD sincrone se caracterizeaza prin:

– Timpul necesar executiei unui pas de calcul in cadrul fiecarui proces are limite inferioara si superioara cunoscute.

– Intarzierile de transmitere a mesajelor sunt marginite si limita lor superiara este cunoscuta.

– Fiecare proces are un ceas local a carei rata de deplasare fata de o referinta standard este cunoscuta.

• Este dificil sa se obtina valori precise ale limitelor de timp dintr-un sistem sincron, desi acestea exista in SD reale.

• Se poate face o modelare a unui algoritm ca un sistem sincron pentru a-i studia comportamentul cat mai aproape de realitate.

• In practica necunoasterea limitelor se poate rezolva folosind tehnica limitarii timpului (engl.timeout).

2013

SD asincrone

• SD asincrone se caracterizeaza prin:

– Timpul necesar executiei unui pas de calcul in fiecare proces are o valoare finita arbitrara.

– Intarzierile de transmitere a mesajelor sunt finite si arbitrare.

– Deplasamentele ceasurilor locale fata de o referinta standard sunt finite si arbitrare.

• Orice sistem sincron este in acelasi timp si asincron. Astfel ca rezolvand o problema pe cazul asincron se asigura universalitatea solutiei. Din pacate insa nu orice problema se poate rezolva in ipoteza asincrona.

2013

Acord in SD I

• Doua divizii ale armatei Pepperland: D si R sunt asezate pevarfurile a doua dealuri invecinate.

• De-alungul vaii care separa dealurile se gasesc invadatorii H.

• D si R sunt in siguranta daca raman in taberele lor.

• D si R pot comunica fiabil trimitand mesageri care sa se strecoare prin vale.

• D si R trebuie sa ajunga la un acord (consens) privind un atacasupra invadatorilor H: (i) cine sa conduca atacul? si (ii) candsa fie pornit atacul?

• Pentru a decide cine va conduce atacul, D si R schimba mesajeprivind forta fiecarei divizii. Cea mai puternica divizie vaconduce atacul, iar in caz de egalitate va conduce divizia D. Decizia se poate lua si intr-un scenariu asincron

2013

Acord in SD II

• Intr-un SD asincron, S si D nu vor putea decide cand sa atacedeoarece interschimbul de mesaje poate dura nelimitat.

• Sa presupunem un SD sincron in care un schimb de mesajedureaza intre min si max unitati de timp.

• Divizia cea mai puternica va trimite un mesaj ‘Atacam’ catrecealalta divizie, asteapta min unitati de timp si ataca.

• Divizia cea mai putin puternica primeste mesajul de atac, asteapta o unitate de timp si ataca.

• Acest algoritm garantreaza ca divizia cea mai puternica vaataca sigur prima, iar divizia cea mai puternica va ataca la celputin max-min+1 unitati de timp dupa ea.

• Problema se complica in prezenta erorilor: ce se intampla dacamesagerii sunt interceptati de invadatori?

2013

Entitati intr-un SD

• Un SD este compus dintr-o multime finita de entitati de calcul E.

• Orice entitate x ∈ E este inzestrata cu o memorie locala nepartajata Mx.

• Memoria locala este compusa dintr-o multime finita de registre pentru fiecare entitate (cu valori initiale precizate) incluzand: – Un registru de stare status(x) cu valori intr-o multime finita de stari S cum ar fi

spre exemplu: processing, idle, waiting, etc.

– Un registru de intrare value(x)

• Fiecare entitate contine un ceas local (temporizator, alarm clock) care poate fi setat sau resetat.

• Capabilitatile entitatii x includ patru tipuri de operatii:– Stocare si procesare locala

– Interactiunea cu alte entitati: pregatirea, transmiterea si receptionarea mesajelor

– (Re)setarea temporizatorului (un tip “special” de procesare locala)

– Schimbarea valorii registrului de stare (un tip “special” de procesare locala)

2013

Evenimente

• Comportamentul unei entitati x ∈ E este reactiv: x raspunde la stimuli externi, numiti evenimente. In absenta evenimentelor. entitatea x este inerta, nu realizeaza nici o activitate.

• Exista trei tipuri de evenimente:– Primirea unui mesaj (trimis de o alta entitate)

– Declansarea temporizatorului

– Impuls spontan

• Primirea unui mesaj si respectiv declansarea temporizatorului sunt evenimente provenite din exteriorul entitatii, dar din cadrul SD.

• Un impuls spontan este declansat de forte externe SD. Exemple: – intr-un sistem bancar entitatile sunt serverele de baze de date si automatele bancare.

Un eveniment de extragere de numerar de catre un client al bancii reprezinta un impuls spontan.

• Evenimentele corespunzatoare impulsurilor spontane apar pentru sistem ca “acte externe” ce declanseaza calculul si comunicatia dintr-un SD.

2013

Actiuni

• Actiune: o secventa finita, indivizibila si terminabila de operatii pe care o entitate x ∈ E le executa ca reactie la un eveniment e. O actiune este:

– Indivizibila (atomica): nu poate fi intrerupta, odata inceputa trebuie terminata

– Terminabila: executia sa dureaza un timp finit.

• Actiunea nula nil desemneaza lipsa de reactie la un eveniment.

2013

Comportamentul unei entitati

• Actiunea realizata de o entitate depinde de evenimentul e si de starea s = status(x) a entitatii x. Schema unei actiuni este: S × EV→ A si se numeste regula, metoda sau productie.

• O regula s × e→ a se numeste activata de (s,e).

• Comportamentul entitatii x consta din multimea B(x) a regulilor sale. Aceasta multime trebuie sa fie completa si neambigua (precisa), adica pentru orice pereche (s,e) sa existe o singura regula activata de (s,e).

• Multimea B(x) se mai numeste protocolul sau algoritmulentitatii x.

2013

Comportamentul unui SD

• Comportamentul colectiv B(E) al unui SD compus dintr-o multime de entitati E este B(E) = {B(x): x ∈ E}.

• Un comportament colectiv se numeste omogen daca toate entitatile au acelasi comportament, adica pentru orice x,y ∈ Eavem B(x) = B(y).

• Propozitie: Orice comportament colectiv se poate transforma intr-un comportament colectiv omogen.

• Justificare: Fiecarei entitati i se asociaza un registru roleinitializat cu rolul entitatii respective in SD. Se construieste o regula unica care selecteaza actiunea corecta in functie de valoarea registrului role.

2013

Comunicare in SD

• Entitatile unui SD comunica prin mesaje.

• Se noteaza cu Nout(x) ⊆ E multimea entitatilor catre care entitatea x poate transmite mesaje si Nin(x) ⊆ E multimea

entitatilor de la care entitatea x poate primi mesaje. Obs: y ∈Nout(x) dnd x ∈ Nin(y).

• Multimile Nout(x) si Nin(x) definesc un graf orientat G = ⟨V,E⟩a.i. V = E si (x,y) ∈ E dnd y ∈ Nout(x) sau echivalent x ∈ Nin(y).

• Graful G defineste topologia de comunicare in SD. Se noteaza cu n(G), m(G) si d(G) numarul de varfuri, arce respectiv diametrul lui G (lungimea maxima a celei mai scurte cai intre oricare doua varfuri ale grafului).

• Nodurile lui G se numesc: noduri, varfuri, entitati sau site-uri. Arcele lui G se mai numesc legaturi.

2013

Presupuneri in SD

• Definitia SD include doua presupuneri de baza numite axiome. Ele se refera la: i) intarzierile de comunicatie si ii) orientarea locala a entitatilor.

• Orice presupunere suplimentara se numeste restrictie.

• Axiomele se refera la:

– Intarzierile de comunicatie

– Orientarea legaturilor

• Restrictiile se pot referi la:

– Comunicare

– Fiabilitate

– Topologie

– Timp

2013

Axiome - intarzieri

• Intarzierile de comunicatie: transmiterea unui mesaj implica o serie de activitati:

– pregatire,

– transmisie,

– receptie,

– …

• Totalitatea intarzierilor cauzate de aceste activitati se numeste intarzierea de comunicatie a mesajului. Aceasta intarziere este inpredictibila.

• Axioma (intarziere finita): In absenta erorilor, intarzierea de comunicatie este finita.

2013

Axiome - orientare

• Orientarea locala: O entitate poate comunica direct cu o submultime a entitatilor sistemului, numite vecinii entitatii respective.

• Axioma (orientare locala): Orice entitate poate distinge intre vecinii sai de intrare si respectiv intre vecinii sai de iesire. Astfel: – o entitate poate transmite un mesaj doar catre unul din vecinii sai de iesire (fara a

transmite mesajul si celorlalti vecini de iesire) si

– o entitate poate distinge vecinul de intrare de la care a primit un mesaj.

• Orice entitate x dispune de o functie locala de etichetare λx care asociaza etichete numite numere de porturi legaturilor incidente (numite si porturi). Functia λx este injectiva. Pentru orice legatura (x,y) ∈ E avem doua etichete: λx(x,y) locala lui x si λy(x,y) locala lui y.

2013

Restrictii de comunicare

• Aceste restrictii se refera la legaturile de comunicatiesi includ:

– Disciplina de servire

– Proprietatile legaturilor de comunicatie

2013

Disciplina de servire

• Disciplina de servire: o legatura (x,y) reprezinta un canal de comunicare sau coada. Expedierea unui mesaj de catre x lui y reprezinta adaugarea sa in coada, iar receptia unui mesaj de catre y de la x reprezinta extragerea sa din coada. Se pot impune diverse discipline de acces la coada.

• Ordonarea: in absenta erorilor, o politica FIFO de adaugare / extragere a mesajelor din coada inseamna ca mesajele expediate de o aceeasi entitate la un vecin de iesire vor fi receptionate in ordinea expedierii lor.

2013

Proprietatile legaturilor de comunicatie

• Proprietatile legaturilor de comunicatie depind de capabilitatile legaturilor fizice corespunzatoare:

– Simplex: cf. modelului general in care legaturile sunt orientate, adicadaca x poate transmite lui y (y ∈ Nout(x)) nu inseamna ca si y poate transmite lui x (x ∈ Nout(y))

– Duplex: presupune doua legaturi simplex, cate una pe fiecare directie

– Full-duplex: o legatura pe care se poate transmite simultan in ambele directii (spre deosebire de half-duplex)

• Comunicare reciproca ∀x∈V , Nin(x) = Nout(x) ceea ce

inseamna ca daca (x,y) ∈ E atunci si (y,x) ∈ E. Dar porturile pe care x trimite lui y (λx(x,y)) si x primeste de la y (λx(y,x)) nu sunt neaparat identice (duplex)

• Cazul bidirectional ∀x∈V Nin(x) = Nout(x) si λx(x,y) = λx(y,x) (full-duplex)

2013

Legaturi bidirectionale

• In cazul bidirectional graful SD este neorientat, adicaG = (V,E) si ∀(x,y) ∈ E avem (x,y) = (y,x).

• ∀x∈V multimea N(x) = Nin(x) = Nout(x) se numestemultimea vecinilor entitatii x.

• In plus m(G) = |E| = 2|E|

2013

Restrictii de fiabilitate

• Arata cum aspecte ale modelului defectelor se pot include in modelul de interactiune.

• Detectia caderilor componentelor:– Detectarea caderilor legaturilor: ∀ (x,y) ∈ E, atat x cat si y pot

detecta daca legatura (x,y) este defecta si daca a fost reactivata.

– Detectarea caderilor entitatilor: ∀x ∈ V , toti vecinii de intrare si de iesire ai lui x pot detecta daca x este defecta si daca a fost reactivata.

• Tipuri restrictive de defecte:– Garantarea livrarii: orice mesaj transmis va fi receptionat fara

coruperea continutului. Cu o astfel de restrictie, protocoalele nu vor trebui sa ia in considerare omisiunea si coruperea mesajelor.

– Fiabilitate partiala: Nu vor aparea erori. Cu o astfel de restrictie, protocoalele nu vor trebui sa ia in considerare posibilele erori. Aceasta ipoteza nu exclude insa situatia in care erori ar fi putut apare inaintea executiei protocolului.

– Fiabilitate totala: Nu au aparut si nu vor aparea erori.

2013

Restrictii de topologie si timp

• Restrictii de topologie:

– Conectivitate: Graful de comunicatie G este tare conex. Acest lucru inseamna ca orice entitate poate transmite direct sau indirect catre orice alta entitate din sistem. Restrictia de conectivitate impreuna cu restrictia legaturilor bidirectionale inseamna ca graful G este neorientat si conex.

• Restrictii de timp:

– Intarzieri marginite de comunicatie: exista o constanta de timp ∆astfel incat, in absenta erorilor, intarzierea de comunicatie a oricarui mesaj transmis pe orice legatura este cel mult ∆.

– Intarzieri de comunicatie unitare: In absenta erorilor, orice mesaj este transmis intr-o unitate de timp.

– Ceasuri sincronizate: toate ceasurile de timp locale sunt incrementate simultan cu o unitate de timp si intervalul de timp dintre doua incrementari succesive este constant.

2013

Costul de comunicare

• Eficienta unui protocol descris prin modelul abstract introdus se va face folosind doua masuri: i) volumul de activitati de comunicare (cat de mult trafic va genera protocolul?); ii) timpul de calcul (cat de ocupat va fi sistemul?).

• Activitatea de comunicare de baza este expedierea unui mesaj printr-un port de iesire catre un vecin; se va lua in calcul si cazul in care un mesaj expediat nu a fost receptionat.

• Volumul de activitati de comunicare se va estima prin numarul de mesaje expediate M = costul mesajelor.

• Incarcarea unei entitati (engl.entity workload) Lnode = M/|V| reprezinta numarul mediu de mesaje expediate pe entitate.

• Incarcarea transmisiei (engl.transmission load) Llink = M/|E| reprezinta numarul mediu de mesaje expediate pe legatura.

• Daca se considera costul mesajelor estimat prin numarul de biti transmisi B rezulta incarcarile la nivel de bit pe entitate si pe legatura: Lbnode = B/|V| si Lblink = B/|E|.

2013

Costul de calcul

• O masura a eficientei si complexitatii o reprezinta timpul total de executie scurs din momentul in care prima entitate incepe executia pana cand ultima entitate termina executia.

• Deoarece in modelul general nu se poate face nici o presupunere privind intarzierea maxima de expediere a unui mesaj, rezulta ca timpul total de executie este inpredictibil putandu-se schimba major de la o executie la alta a sistemului.

• Se poate insa estima timpul unei executii ideale T, considerandu-se restrictiile: intarzieri de transmisie unitare si ceasuri sincronizate.

• O alta masura este complexitatea de timp cauzal Tcausal definita prin lungimea celui mai lung sir de expedieri de mesaje corelate cauzal, din multimea tuturor executiilor posibile.

2013

Modelul defectelor

• In SD se pot defecta atat procesele cat si canalele de

comunicatie

• Defect = orice abatere de la comportamentul corect

dorit. Modelul defectelor defineste tipurile si

manifestarile defectelor in scopul intelegerii efectelor

lor.

• Exista trei mari categorii de defecte: defecte prin

omitere, defecte arbitrare si defecte de timp.

• Defectele prin omitere se refera la cazurile in care un

proces sau canal de comunicatie nu reuseste sa

efectueaze actiunile pe care trebuie sa le faca.

• Defectele arbitrare (bizantine) descriu situatiile cele

2013

Defecte prin omitere ale proceselor

• Caderea unui proces (engl. crash) inseamna ca procesul se opreste (engl. halts) si nu mai executa nici un pas de calcul

• Detectarea unei caderi a unui proces se poate realiza prin impunerea unei limite a timpului de raspuns (engl. timeout). Daca un proces nu mai raspunde la invocari intr-un timp prestabilit inseamna ca este posibil sa se fi produs o cadere a procesului.

• Metoda limitarii timpului de raspuns functioneaza cu certitudine absoluta doar pentru sistemele sincrone. Intr-un sistem asincron faptul ca procesul nu raspunde poate insemna fie o cadere, fie faptul ca procesul ruleaza foarte incet.

• O cadere detectabila a unui proces (de exemplu prin impunerea unor limite de timp in SD sincrone) se numeste fail-stop.

2013

Defecte prin omitere ale canalelor de comunicatie

• Apare cand canalul nu reuseste sa transmita un mesaj din tamponul de iesire al procesului p catre tamponul de intrare al procesului q.

• Daca eroarea apare intre procesul expeditor p si tamponul sau de iesire atunci ea se numeste send-omission failure.

• Daca eroarea apare intre tamponul de intrare al procesului receptor q si proces atunci ea se numeste receive-omission failure.

• Daca eroarea apare intre tamponul de iesire al procesului expeditor p si tamponul de intrare al procesului destinatar q atunci ea se numeste channel-omission failure.

Proces p Proces q

Canal de comunicatie

send m

Tampon de iesire pentru mesaje Tampon de intrare pentru mesaje

receive

2013

Defecte arbitrare

• Descriu situatiile cele mai “rele” in care poate sa apara orice tip de eroare.

• Procesele se pot defecta arbitrar: – prin executia unor actiuni eronate (posibil intentionat), de exemplu de asignare a

unor valori eronate sau prin returnarea unor valori eronate

– Prin omiterea unor pasi de calcul sau prin inserarea intentionata a unor pasi de calcul neprevazuti

• Defectele arbirare ale proceselor nu pot fi detectate prin observarea raspunsului procesului la invocari.

• Canalele de comunicatie se pot defecta arbitrar prin coruperea sau intarzierea mesajelor, sau prin multiplicarea sau inserarea arbitrara de mesaje. O comunicatie fiabila presupune proprietatile de validitate si integritate.

• Erorile arbitrare ale canalelor de comunicatie sunt destul de rare deoarece software-ul de comunicatie poate recunoaste si rejecta mesajele corupte prin sume de control, respectiv nelivrarea sau duplicarea unor mesaje prin numere de secventa.

2013

Defecte de omitere si defecte arbitrare

Class of failure Affects Description

Fail-stop Process Process halts and remains halted. Other processes maydetect this state.

Crash Process Process halts and remains halted. Other processes maynot be able to detect this state.

Omission Channel A message inserted in an outgoing message buffer neverarrives at the other end’s incoming message buffer.

Send-omission Process A process completes a send,but the message is not putin its outgoing message buffer.

Receive-omission Process A message is put in a process’s incoming messagebuffer, but that process does not receive it.

Arbitrary(Byzantine)

Process orchannel

Process/channel exhibits arbitrary behaviour: it maysend/transmit arbitrary messages at arbitrary times,commit omissions; a process may stop or take anincorrect step.

2013

Defecte de timp

Class of Failure Affects Description

Clock Process Process’s local clock exceeds the bounds on itsrate of drift from real time.

Performance Process Process exceeds the bounds on the intervalbetween two steps.

Performance Channel A message’s transmission takes longer than thestated bound.

2013

Modelul de securitate

• SD sunt motivate si de partajarea resurselor. Acestea sunt incapsulate sub forma de obiecte, componente sau servicii in cadrul proceselor SD. Accesul la ele este furnizat prin interactiuni intre procese.

• Securizarea SD se poate realiza prin securizarea proceselor (a accesului la anumite operatii, controlul executiei proceselor), a canalelor de comunicatie si prin protejarea obiectelor impotriva acceselor neautorizate.

• Modelul de securitate are in vedere:

– Protectia obiectelor

– Protectia proceselor si a interactiunilor dintre ele

– Modelarea si dejucarea pericolelor (atacurilor) de securitate (engl. security threats)

2013

Protectia obiectelor

• Obiectele se utilizeaza in mod diferit de catre utilizatori diferiti. Trebuie folosite metode pentru controlul accesului.

• Se definesc drepturile de acces (engl. access rights) care stabilesc operatiile permise asupra unui obiect de catre fiecare tip de utilizatori.

• Pentru includerea utilizatorilor in acest model, se asociaza fiecarei invocari si fiecarui rezultat autoritatea generatoare. Aceasta autoritate se numeste principal si ea poate fi un utilizator (ex. invocare) sau proces (ex. rezultat).

• Serverul verifica identitatea principalului si faptul ca acesta are suficiente drepturi sa realizeze operatia ceruta asupra obiectului tinta. Clientul verifica identitatea principalului din spatele serverului pentru a stabili ca rezultatul provine de la serverul corect.

Network

invocation

result

ClientServer

Principal (user) Principal (server)

ObjectAccess rights

2013

Securizarea proceselor si interactiunilor

• Procesele interactioneaza prin schimb de mesaje.

• Mesajele sunt expuse atacurilor deoarece in general serviciile de comunicatie ale retelelor sunt deschise pentru a permite interactiuni dinamice intre procese.

• Serverele si procesele peer isi expun interfetele pentru invocare din partea oricarui alt proces.

• Natura aplicatiilor SD, spre exemplu din domeniul financiar-bancar, predispune SD la confruntarea cu utilizatori ostili.

• Secretizarea si integritatea informatiei gestionata de astfel de SD este cruciala.

2013

Pericole de securitate

• Modelarea pericolelor (atacurilor) de securitate presupune existenta unui inamic sau adversar sa trimita mesaje unor procese, respectiv sa citeasca, copieze si sa altereze mesajele schimbate de procese.

• Doua tipuri de pericole:

– Pericole asupra proceselor

– Percole asupra canalelor de comunicatie

Communication channel

Copy of m

Process p Process qm

The enemym’

2013

Pericole asupra proceselor

• Un proces poate primi mesaje intr-un SD de la orice alt proces. Trebuie determinata identiatea expeditorului. Protocoalele IP includ adresa IP a expeditorului in fiecare mesaj, insa aceasta adresa este usor de falsificat.

• Lipsa de cunoastere sigura a sursei expeditorului afecteaza clientii si serverele astfel:

– Un server, necunoscand identitatea expeditorului, nu stie cand sa accepte sau sa interzica o anumita invocare din partea unui client. De exemplu, invocarea poate cere citirea unui anumit mesaj de postaelectronica, aceasta actiune necesitand cunoasterea cu certitudine a identitatii clientului.

– Cand un client primeste rezultatul invocarii de la un server nu poate identifica cu certitudine expeditorul rezultatului. In exemplul cu citirea postei electronice, rezultatul poate fi returnat de un server implicat intr-un atac de spoofing asupra serverului de posta electronica.

2013

Pericole asupra canalelor de comunicatie

• Un inamic poate copia, altera, injecta sau elimina mesaje intr-o retea. Aceste actiuni pericliteaza integritatea si secretizarea (engl. privacy) informatiei continuta in mesaje.

• Aceste atacuri pot fi prevenite prin implementarea conceptului de canal sigur (engl. secure channel) folosind:

– Tehnici criptografice pentru codificarea si respectiv decodificarea mesajelor cu ajutorul unor chei.

– Tehnici de autentificare bazate pe criptarea identitatii expeditorilor mesajelor.

• Un canal sigur ne asigura:

– Fiecare proces cunoaste identitatea autoritatilor principale alecelorlalte procese ce executa invocari asupra sa.

– Integritatea si secretizarea informatiei din mesaje.

– Eliminarea mesajelor duplicate si refacerea ordinii mesajelor prin marcaje de timp si/sau de secventa.

2013

Exemplu de algoritm distribuit: Broadcasting

• Se considera un SD in care o entitate detine o informatie si doreste sa o transmita tuturor celorlalte entitati din SD.

• Fie E multimea entitatilor si G topologia SD. Presupunem ca legaturile sunt bidirectionale si ca fiabilitatea este totala (nu exista erori).

• Daca G nu este conex anumite entitati nu vor putea receptiona informatia. Asa ca vom presupune ca G este un graf conex.

• O singura entitate, ce contine informatia de transmis, va initia procesul de transmisie – presupunerea de initiator unic.

• O strategie simpla de rezolvare a problemei: “daca o entitate cunoaste informatia atunci o va face cunoscuta si vecinilor”

• Pentru a distinge intre entitatea initiator (ce detine initial informatia de transmis I) si celelalte entitati introducem doua stari: initiator si idle. Procesul va fi pornit de initiator.

2013

Protocol pentru Broadcasting (I)

• Protocolul pentru Broadcasting se mai numeste si protocol de inundare (engl.flooding).

• Se considera protocolul B(x) pentru toate entitatile x ∈ E.

1. initiator × ı→ { send(I) to N(x) }

2. idle × Receiving(I) → { process(I); send(I) to N(x) }

3. initiator × Receiving(I) → nil

4. idle × ı→ nil

• unde ı desemneaza un impuls spontan si nil desemneaza actiunea vida.

• Datorita conectivitatii si fiabilitatii totale, fiecare entitate va primi informatia. Problema acestui protocol este insa ca nu se termina.

• Spre exemplu daca avem 3 entitati x, y si z astfel incat x este initiator, iar y si z sunt idle, atunci y si z isi vor trimite la infinit informatia atat unul altuia, cat si lui x.

2013

Protocol pentru Broadcasting (II)

• Pentru a se asigura terminarea protocolului trebuie ca fiecare entitate sa transmita informatia vecinilor o singura data. Introducem trei stari: initiator, idle si done.

1. initiator × ı→ { send(I) to N(x); become done }

2. idle × Receiving(I) → { process(I); become done; send(I) to N(x) }

3. initiator × Receiving(I) → nil

4. idle × ı→ nil

5. done × Receiving(I) → nil

6. done × ı→ nil

• Protocolul se termina deoarece fiecare entitate va ajunge in timp finit in starea done. Corectitudinea rezulta din faptul ca orice entitate ce ajunge in starea done va contine informatia initiala.

• Este posibil ca unele entitati sa se termine (in starea done) fara ca alte entitati sa fi inceput inca prelucrarile. Astfel ca trebuie sa distingem intre terminarea locala a unei entitati si terminarea globala a intregului SD.

• Pentru acest protocol, nici o entitate nu stie cand procesul de transmisie sa terminat. Aceasta este problema detectarii terminarii.

2013

Costul de comunicatie pentru Broadcasting

• Fiecare entitate va transmite informatia tuturor vecinilor sai. Astfel ca numarul total de mesaje transmise va fi:

∑x∈E |N(x)| = 2 |E| = 2 m.

• Acest cost poate fi redus. Astfel, cand o entitate idle primeste informatia, ea va transmite informatia tuturor vecinilor, excluzand entitatea de la care a primit-o – acest lucru este posibil din axioma de orientare locala ce afirma ca o entitate intre vecinii sai. Astfel, la primirea unui mesaj ea poate identifica portul pe care a primit mesajul astfel incat sa evite retransmiterea sa pe acel port.1. initiator × ı→ { send(I) to N(x); become done }

2. idle × Receiving(I) → { process(I); become done; send(I) to N(x)-{sender} }

3. initiator × Receiving(I) → nil

4. idle × ı→ nil

5. done × Receiving(I) → nil

6. done × ı→ nil

unde sender este vecinul care a transmis mesajul curent.

• Se poate arata ca acest algoritm necesita M = 2 m – n + 1 mesaje.

2013

Costul de calcul pentru Broadcasting

• Fie d(x,y) lungimea celei mai scurte cai intre nodurile x si y ale grafului G.

• Informatia transmisa de initiator va trebui sa ajunga si la cea mai indepartata entitate de initiator.

• Daca x este entitatea initiator atunci complexitatea ideala de calcul va fi:

r(x) = maxy∈E{ d(x,y) }

• Valoarea r(x) se numeste excentricitatea sau raza lui x in graful G.

• In cazul cel mai defavorabil, complexitatea ideala va fi:

d(G) = maxx∈E{ r(x) }

• Valoarea d(G) se numeste diametrul grafului G. Cu alte cuvinte putem concluziona ca: T ≤ d(G).

2013

Pseudocod

• Regulile protocolului se grupeaza pe stari

• Daca actiunea pentru o pereche (s,e) este nil atunci regula corespunzatoare se va omite. Rezulta ca pentru orice pereche (s,e) pentru care nu exista nici o regula asociata, se va considera implicit regula ce realizeaza actiunea vida nil.

• Daca o actiune specifica schimbarea starii curente atunci aceasta operatie va fi ultima inainte de terminarea actiunii.

• Multimea starilor, starilor initiale, starilor terminale si a restrictiilor protocolului vor fi specificate explicit la inceputul protocolului.

• Evenimentele externe sunt: Spontan (impuls spontan), Receiving (receptionarea unui mesaj) si When (declansarea temporizatorului). Ordinea de procesare a acestor evenimente respecta urmatoarea precedenta: Spontan > When > Receiving.

• La orice moment de timp o entitate poate avea: (i) cel mult un eveniment de timp; (ii) cel mult un impuls spontan; (iii) oricate evenimente de receptionare de mesaje (ele vor fi tratate secvential, intr-o ordine arbitrara)

• Comanda send(M) toW va realiza copierea mesajului M pe toate porturile de iesire din multimea W.

• Cand un mesaj M este trimis pe un port de iesire I, el va fi receptionat dupa un timp finit de entitatea corespunzatoare portului I, generand un eveniment Receiving(M), moment in caare variabila sender primeste valoarea I.

2013

Protocolul de inundare in pseudocod

PROTOCOL Inundare

Stari: S = {INITIATOR, IDLE, DONE};

Stari initiale SINIT = {INITIATOR, IDLE};

Stari terminale STERM = {DONE};

Restrictii: legaturi bidrectionale, fiabilitate totala, conectivitate, initiator unic

INITIATOR

Spontan

begin

send(I) to N(x)

become DONE

end

IDLE

Receiving(I)

begin

Proceseaza(I)

send(I) to N(x) – {sender}

become DONE

end