Calcolo distribuito: differenze tra le versioni

Versione delle 12:34, 11 feb 2012

Versione attuale delle 14:29, 30 dic 2024

(46 versioni intermedie di 30 utenti non mostrate)

Riga 1:

Il '''calcolo distribuito''' è un campo dell'[[informatica]] che studia i '''[[sistema distribuito|sistemi distribuiti]]'''., Unovvero sistemasistemi distribuitoche consisteconsistono in tanti ed autonominumerosi [[computer]] autonomi che interagiscono/comunicano tra loro attraverso una [[Rete di calcolatori|rete]]. I computer interagiscono tra loro al fine di raggiungere un obiettivo comune. Un(un [[software]] eseguito in un sistema distribuito è chiamatodetto '''programma distribuito''', e la '''programmazione distribuita''' è il processo di scrittura di tali software).

IlUn calcolotipico distribuitoesempio sidi riferisceapplicazione anchedel allcalcolo distribuito è l'uso di sistemi distribuiti per risolvere problemi computazionali. Neldi calcolouna distribuito,certa complessità: in tale ambito un problema è divisosuddiviso a sua volta in molti compitisottocompiti ognuno dei quali è risolto da un singolo [[computer]].

== Storia ==

L'uso di processi concorrenti che comunicano con il passaggio di messaggi ha le sue radici nelle architetture di [[Sistema operativo|sistemi operativi]] studiati negli anni 1960. Il primo sistema distribuito diffuso è stato il [[Local area network|local-area network]] come [[Ethernet]] che è stato inventato negli anni 1970.

[[ARPANET]], il predecessore di [[Internet]], è stato introdotto nei tardi anni 1960 e l'ARPANET e-mail è stata inventata nei primi anni 1970. La posta elettronica divenne l'applicazione di maggior successo di ARPANET ed è probabilmente il primo esempio di applicazione distribuita su larga scala. In aggiunta ad ARPANET ed al suo successore Internet, altre prime reti di computer in tutto il mondo sono state [[Usenet]] e [[Fidonet]] dagli anni 1980, entrambe le quali sono state utilizzate per sostenere sistemi distribuiti di discussione.

Lo studio del calcolo distribuito divenne propriamente branca dell'informatica nei tardi anni 1970 e primi 1980. La prima conferenza nel campo “Simposio dei principi del calcolo distribuito”, risale al 1980 e la sua controparte europea “Simposio internazionale sul calcolo distribuito” fu per la prima volta tenuta nel 1985.

== Descrizione ==

La parola distribuito in termini come “sistema distribuito”, “programmazione distribuita”, e “[[algoritmo distribuito]]” originariamente si riferiva a [[rete di computer|reti di computer]] dove singoli computer erano fisicamente distribuiti in certe aree geografiche. I termini sono oggi utilizzati in un più ampio senso, anche quando si riferiscono a [[Processo (informatica)|processi]] autonomi che sono eseguiti sullo stesso computer fisico ed interagiscono tra loro tramite il passaggio di messaggi.

== Introduzione ==

La parola distribuito in termini come “sistema distribuito”, “programmazione distribuita”, e [[Algoritmo distribuito|“algoritmo distribuito”]] originariamente si riferiva a reti di computer dove singoli computer erano fisicamente distribuiti in certe aree geografiche. I termini sono oggi utilizzati in un più ampio senso, anche quando si riferisce a [[Processo (informatica)|processi]] autonomi che sono eseguiti sullo stesso computer fisico ed interagiscono tra loro tramite il passaggio di messaggi.

Mentre non c'è una singola definizione di sistema distribuito, le seguenti proprietà sono comunemente usate:

* Ci sono molte autonome entità computazionali autonome, ognuna delle quali ha la propria [[Memoria (informatica)|memoria]] locale.

* Le entità comunicano tra loro con il [[passaggio di messaggi]].

In questoquesta articolotrattazione, le entità computazionali sonoverranno chiamate computer o [[Nodo (informaticatelecomunicazioni)|nodi]].

Un sistema distribuito può avere un obiettivo comune, come risolvere un grande problema computazionale. Alternativamente, ogni computer può avere il proprio utente con bisogni individuali, e lo scopo del sistema distribuito è di coordinare l'uso delle risorse condivise o fornire servizi di comunicazione all'utente.

Altre tipiche proprietà dei sistemi distribuiti sono ile seguenti:

* Il sistema tollera guasti a singoli computer.

* La struttura del sistema ([[topologia di rete]], latenza di rete, numero di computer) non è conosciuta in anticipo, il sistema può consistere in differenti tipi di computer e collegamenti di rete, e può cambiare durante l'esecuzione del programma distribuito.

* Ogni computer ha solamente una vista limitata ed incompleta del sistema. Ogni computer conosce solo una parte dell'input.

=== Calcolo parallelo o distribuito? ===

I termini “calcolo concorrente”, “[[calcolo parallelo]]”, e “calcolo distribuito” hanno molte sovrapposizioni, e non esiste nessuna chiara distinzione tra di loro. Lo stesso sistema può essere caratterizzato sia come “parallelo” sia come “distribuito”; i processori in un sistema distribuito tipico elaborano concorrentemente, in parallelo. Il calcolo parallelo può esser visto come una forma particolare strettamente unita al calcolo distribuito, ed il calcolo distribuito può esser visto come una forma particolare strettamente unita al calcolo parallelo. Tuttavia è possibile classificare sistemi concorrenti come “paralleli” o “distribuiti” tramite i seguenti criteri:

* Nel calcolo parallelo tutti i processori devono accedere ad una [[memoria condivisa]]. La memoria condivisa può essere usata per lo scambio di informazioni tra i processori.

* Nel calcolo distribuito ogni processore ha la propria memoria privata ([[memoria distribuita]]). Le informazioni sono scambiate grazie al passaggio di messaggi tra i processori.

L'immagine a destra illustra la differenza tra sistemi distribuiti e sistemi paralleli. [[ImmagineFile:Distributed-parallel.svg|thumb|(a)–(b) Sistema distribuito.

(c) Sistema parallelo.]] La figura (a) è la vista schematica di un tipico sistema distribuito; come al solito,: il sistema è rappresentato come un [[grafo]] in cui ogni nodo (vertex) è un computer ed ogni riga (linea tra due nodi) è un collegamento di comunicazione. La figura (b) mostra lo stesso sistema distribuito più in dettaglio: ogni computer ha la propria memoria locale, e le informazioni possono essere scambiate solamente grazie al passaggio di messaggi da un nodo ad un altro usando i nodi di comunicazione disponibili. La figura (c) mostra un sistema parallelo in cui ogni processore ha accesso diretto alla memoria condivisa.

La situazione è ulteriormente complicata dai tradizionali usi dei termini algoritmo parallelo e distribuito che non corrispondono alla definizione di sistemi paralleli e distribuiti. Tuttavia, come regola generale, il calcolo parallelo ad alte prestazioni con memoria condivisa multiprocessore usa algoritmi paralleli mentre per la coordinazione di sistemi distribuiti su larga scala si usano algoritmi distribuiti.

== Storia ==

L'uso di processi concorrenti che comunicano con il passaggio di messaggi ha le sue radici nelle architetture di [[Sistema operativo|sistemi operativi]] studiati negli anni 1960. Il primo sistema distribuito diffuso è stato il [[Local area network|local-area network]] come [[Ethernet]] che è stato inventato negli anni 1970.

[[Arpanet|ARPANET]], il predecessore di [[internet]], è stato introdotto nei tardi anni 1960 e l'ARPANET e-mail è stata inventata nei primi anni 1970. La posta elettronica divenne l'applicazione di maggior successo di ARPANET ed è probabilmente il primo esempio di applicazione distribuita su larga scala. In aggiunta ad ARPANET ed al suo successore Internet, altre prime reti di computer in tutto il mondo sono state [[Usenet]] e [[Fidonet|FidoNet]] dagli anni 1980, entrambe le quali sono state utilizzate per sostenere sistemi distribuiti di discussione.

Lo studio del calcolo distribuito divenne propriamente branca dell'informatica nei tardi anni 1970 e primi 1980. La prima conferenza nel campo “Simposio dei principi del calcolo distribuito”, risale al 1980 e la sua controparte europea “Simposio internazionale sul calcolo distribuito” fu per la prima volta tenuta nel 1985.

== Applicazioni ==

Ci sono due principali ragioni per usare sistemi distribuiti ed il calcolo distribuito. Primo, la vera natura dell'applicazione può richiedere l'uso di un network di comunicazione che collega più computer. Per esempio, i dati sono prodotti in una certa locazione fisica e servono in un'altra locazione.

Secondo, sono molti i casi in cui l'uso di un singolo computer sarebbe possibile in linea di principio, ma l'uso di un sistema distribuito è vantaggioso per motivi pratici. Per esempio, può essere più efficiente ottenere il livello prestazionale desiderato usando un [[Computer cluster|cluster]] di diversi computer di fascia bassa, in confronto con un sistema non distribuito e non ci sono single point of failure. Inoltre, un sistema distribuito può essere più facile da espandere e dirigere confronto ad un sistema uniprocessore monolitico.

Esempi di sistemi distribuiti ed applicazioni di calcolo distribuito sono inclusi di seguito:

* Reti di [[Telecomunicazione|telecomunicazioni]]:

** [[Rete telefonica|Reti telefoniche]] e reti cellulari

** Reti di computer come Internet

** [[Wireless sensor network|Reti di sensori senza fili]]

** Algoritmi di [[routing]]

* Applicazioni di rete:

** [[World wide web]] e reti peer-to-peer

** Giochi online multiplayer e comunità di realtà virtuale

** [[Database distribuiti|Databases distribuiti]] e sistemi di gestione di databases distribuiti

** [[File System|File systems]] di rete

** Sistemi di elaborazione di informazioni distribuite come sistemi bancari e sistemi di prenotazione delle compagnie aeree.

* Controllo in tempo reale:

** Sistemi di controllo aereo

** Sistemi di controllo industriali

* Calcolo parallelo:

** [[Calcolo scientifico]], incluso il cluster computing, il [[grid computing]] ed altri vari progetti di calcolo volontario; vedere la [[lista dei progetti di calcolo distribuito]].

** Rendering distribuito in computer grafica

== Fondamenti teorici ==

=== Modelli ===

Molti compiti che vorremmo automatizzare usando il computer sono di tipo domanda-risposta del tipo: vorremmo farefacciamo una domanda ed il computer dovrebbe dare la risposta. In informatica questi compiti sono chiamati problemi computazionali. Formalmente, un problema computazionale consiste in istanze, unitamente ad una soluzione per ogni istanza. Le istanze sono domande che possiamo porre e le soluzioni sono le risposte desiderate a queste domande.

L'informatica cerca di capire quali problemi computazionali si possono risolvere usando un computer ([[teoria della computabilità]]) e quanto efficientemente ([[teoria della complessità computazionale]]). Tradizionalmente è come dire che un problema può essere risolto usando un computer se possiamo scrivere un [[algoritmo]] che produce una soluzione corretta per qualsiasi istanza data. Un tale algoritmo può essere implementato come un software che viene eseguito su un generico computer: il programma legge l'istanza del problema da un [[input]], esegue dei calcoli, e produce la soluzione come output. Formalismi come macchine ad accesso casuale o [[Macchine di Turing|macchine universali di Turing]] possono essere usati come modelli astratti di un generico computer sequenziale che esegue un tale algoritmo.

Riga 66 ⟶ 43:

Il campo del calcolo concorrente e distribuito studia questioni simili nel caso di molti computer, o un computer che esegue una rete di processi interagenti: quali problemi computazionali possono essere risolti in una tale rete e con quale efficienza? Tuttavia non è così evidente cosa significhi risolvere un problema nel caso di sistemi concorrenti o distribuiti: per esempio, qual è il compito del progettista dell'algoritmo e qual è l'equivalente concorrente e/o distribuito per un generico computer?

La discussione sotto si concentra sul caso di molti computer, comunquema in ogni caso molte di queste questioni sono le stesse per i processi concorrenti eseguiti su un singolo computer.

Ci sono tre casi comunemente utilizzati:

'''Algoritmi paralleli in modelli a memoria condivisa'''

* Tutti i computer hanno accesso alla memoria condivisa. Il progettista dell'algoritmo sceglie il programma eseguito da ogni computer.

Riga 76 ⟶ 54:

'''Algoritmi paralleli nel modello a passaggio di messaggi'''

* Il progettista dell'algoritmo sceglie la struttura della rete nonché il programma eseguito da ogni computer

* Sono usati modelli come circuiti booleani e reti di ordinamento. Un [[Circuiti booleani|circuito booleano]] può esser visto come una rete di computer: ogni gate è un computer che esegue un programma estremamente semplice. Similmente, anche una rete di ordinamento può esser vista come una rete di computer: ogni comparatore è un computer.

'''Algoritmi distribuiti nel modello a passaggio di messaggi'''

* Il progettista dell'algoritmo sceglie solamente il programma. Tutti i computer eseguono lo stesso programma. Il sistema deve funzionare correttamente a prescindere dalla struttura della rete.

* Un modello comunemente usato è il grafo con ununa [[macchina a stati finiti]] per nodo.

Nel caso di algoritmi distribuiti i problemi computazionali sono tipicamente legati ai grafi. Spesso il grafo che descrive la struttura della rete di computer è l'istanza del problema. Questo caso è illustrato nel seguente esempio.

Riga 87 ⟶ 65:

'''Algoritmi centralizzati'''

* Il grafo G è codificato come una stringa, e la stringa è data come input ad un computer. Il programma trova una colorazione del grafo, codifica la colorazione come una stringa e dadà il risultato in output.

'''Algoritmi paralleli'''

Riga 106 ⟶ 84:

Negli algoritmi paralleli un'altra risorsa in aggiunta a tempo e spazio è il numero di computer. Infatti, spesso c'è un bilanciamento tra il tempo d'esecuzione ed il numero di computer: il problema può essere risolto velocemente se ci sono più computer che elaborano in parallelo. Se un problema decisionale può essere risolto in tempo polilogaritmico usando un numero polinomiale di processori allora il problema si dice che sia in classe NC. La classe NC si può definire altrettanto bene usando il formalismo PRAM o i circuiti booleani. Le macchine PRAM possono simulare efficientemente circuiti booleani e viceversa.

Nelle analisi degli algoritmi distribuiti è data solitamente più attenzione allalla comunicazione delle operazioni che ai passi computazionali. Forse il più semplice modello di calcolo distribuito è un sistema sincrono dove tutti i nodi operano in blocco. Durante ogni turno di comunicazione, tutti i nodi in parallelo (1) ricevono gli ultimi messaggi dai suoi vicini, (2) effettuano arbitrari calcoli locali e (3) mandano nuovi messaggi ai loro vicini. In tali sistemi, una misura di complessità centrale è il numero di turni di comunicazione sincroni richiesti per completare il compito.

Questa misura di complessità è strettamente collegata al diametro della rete. Sia D il diametro della rete. Da un lato, qualsiasi problema computazionale può essere risolto banalmente in un sistema sincrono distribuito in approssimatamenteapprossimativamente 2D turni di comunicazione: semplicemente per raccogliere tutte le informazioni in un unico punto (D turni), risolvere il problema, ed informare ogni nodo circa la soluzione (D turni).

Dall'altro lato, se il tempo d'esecuzione dell'algoritmo è molto inferiore a D turni di comunicazione, allora i nodi della rete devono produrre i loro risultati senza avere la possibilità di ottenere informazioni circa le parti lontane della rete. In altre parole, i nodi devono prendere decisioni a livello globale basate su informazioni che sono disponibili nei loro paraggi. Molti algoritmi distribuiti sono conosciuti con il tempo d'esecuzione molto più piccolo di D turni, e la comprensione di quali problemi possono essere risolti da tali algoritmi è uno degli obiettivi centrali della ricerca di questo campo.

Riga 115 ⟶ 93:

=== Altri problemi ===

I problemi computazionali sonogeneralmente nellaconsistono prospettivanel che noi facciamoporre una domanda, ad un computer (o ad un sistema distribuito), che elabora la domanda per un po', ed infine produce una risposta e si ferma. Tuttavia, ci sono anche problemi in cui noi non vogliamo che il sistema non si fermi mai. Esempi di tali problemi includono il [[problema del pranzo dei filosofi a cena]] ed altri simili problemi a [[mutua esclusione]]. In questi problemi il sistema distribuito dovrebbe coordinare costantemente l'uso delle risorse condivise senza la presenza di conflitti o [[Deadlock|stallo]].

Ci sono anche fondamentali sfide che sono uniche per il calcolo distribuito. Il primo esempio è la sfida riguardante il fault-tolerance. Esempi di problemi connessi includono problemi di consenso, Byzantine fault tolerance, e auto stabilizzazione.

Riga 132 ⟶ 110:

== Architetture ==

Per il calcolo distribuito sono usate varie architetture hardware e software. Ad unA basso livello è necessario interconnettere CPU multiple con una sorta di rete, indipendentemente dal fatto che la rete sia stampata su un circuito o composta da dispositivi e cavi. Ad alto livello è necessario invece interconnettere i processi eseguiti su quelle CPU con una sorta di sistema di comunicazione.

La programmazione distribuita di solito cade in uno dei numerosi elementi architettonici di base o categorie: Client-server, architettura 3-tier, architettura N-tier, oggetti distribuiti, loose coupling, tight coupling.

* [[Client server|Client-server]] – Il codice client contatta il server per i dati, che formatta e mostra all 'utente. Gli input dati al client sono spediti al server quando rappresentano un dato permanente.

* [[architettura three-tier|Architettura 3-tier]] – Il sistema 3-tier sposta l'intelligenza del client ad un livello intermedio in modo che il client senza stato possa essere utilizzato. Questo semplifica lo spostamento delle applicazioni. La maggior parte delle [[Applicazione web|applicazioni web]] è 3-Tier.

* [[Architettura Nn-tier]] – N-tier si riferisce solitamente ad applicazioni web che inviano le loro richieste alad altri servizi. Questo tipo di applicazione è una delle maggiori responsabili del successo delle applicazioni server.

* Tight coupled (clustered) – Si riferisce solitamente ad un cluster di macchine che lavorano insieme eseguendo un processo condiviso in parallelo. Il compito è suddiviso in parti che sono fattielaborate individualmente da ognuno e poi rispeditirispedite indietro insieme per comporre il risultato finale.

* [[Peer-to-peer]] – Un'architettura dove non sono presenti particolari macchine che forniscono un servizio o gestiscono le risorse di rete. Invece tutte le responsabilità sono uniformemente divise tra tutte le macchine conosciute come "peer". I peerspeer possono funzionare sia come client che come server.

* Space based  – Si riferisce ad una infrastruttura che crea l'illusione (virtualizzazione) di un singolo spazio di indirizzo. I dati sono trasparentemente replicati a seconda dei bisogni delle applicazioni.

Un altro aspetto basilare delle architetture di calcolo distribuito è il metodo di comunicazione ed i lavori di coordinamento tra processi concorrenti. Tramite vari protocolli di scambio messaggi, i processi possono comunicare direttamente con un altro, tipicamente con relazione master/slave. Alternativamente, un'architettura con database centrale potrebbe rendere il calcolo distribuito eseguito senza nessuna forma di comunicazione inter processo, utilizzando un database condiviso.

== Applicazioni ==

Ci sono due principali ragioni per usare sistemi distribuiti ed il calcolo distribuito. Primo, la natura dell'applicazione può richiedere l'uso di un network di comunicazione che collega più computer. Per esempio, i dati sono prodotti in una certa locazione fisica e servono in un'altra locazione.

Secondo, sono molti i casi in cui l'uso di un singolo computer sarebbe possibile in linea di principio, ma l'uso di un sistema distribuito è vantaggioso per motivi pratici. Per esempio, può essere più efficiente ottenere il livello prestazionale desiderato usando un [[Computer cluster|cluster]] di diversi computer di fascia bassa, in confronto con un sistema non distribuito e non ci sono single point of failure. Inoltre, un sistema distribuito può essere più facile da espandere e dirigere confronto ad un sistema uniprocessore monolitico.

Esempi di sistemi distribuiti ed applicazioni di calcolo distribuito sono inclusi di seguito:

* Reti di [[Telecomunicazione|telecomunicazioni]]:

** [[Rete telefonica|Reti telefoniche]] e reti cellulari

** Reti di computer come Internet

** [[Wireless sensor network|Reti di sensori senza fili]]

** Algoritmi di [[routing]]

* Applicazioni di rete:

** [[World wide web]] e reti peer-to-peer

** Giochi online multiplayer e comunità di realtà virtuale

** [[Database distribuiti]] e sistemi di gestione di database distribuiti

** [[File System|File systems]] di rete

** Sistemi di elaborazione di informazioni distribuite come sistemi bancari e sistemi di prenotazione delle compagnie aeree.

* Controllo in tempo reale:

** Sistemi di controllo aereo

** Sistemi di controllo industriali

* Calcolo parallelo:

** [[Calcolo scientifico]], incluso il cluster computing, il [[grid computing]] ed altri vari progetti di calcolo volontario; vedere la [[lista dei progetti di calcolo distribuito]].

** Rendering distribuito in computer grafica

== Note ==

Riga 165 ⟶ 167:

'''Siti web'''

* Godfrey, Bill (2002). [http://www.bacchae.co.uk/docs/dist.html A primer on distributed computing] {{Webarchive|url=https://web.archive.org/web/20100225154106/http://www.bacchae.co.uk/docs/dist.html |date=25 febbraio 2010 }}.

* Peter, Ian (2004). [http://www.nethistory.info/History%20of%20the%20Internet/ Ian Peter's History of the Internet]. Retrieved 2009-08-04.

Riga 173 ⟶ 175:

* [[Grid computing]]

* [[BOINC]]

* [[Distribuited thinking]]

* [[Algoritmo dello spaccone]]

== Altri progetti ==

{{interprogetto|commonspreposizione=Category:Distributed computingsul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Controllo di autorità}}

{{Portale|Telematica}}

[[Categoria:Calcolo distribuito| ]]

[[ar:حوسبة موزعة]]

[[be:Размеркаваныя вылічэнні]]

[[be-x-old:Разьмеркаваныя вылічэньні]]

[[bg:Разпределени изчислителни системи]]

[[bs:Distribuirano računarstvo]]

[[ca:Computació distribuïda]]

[[cs:Distribuovaný výpočet]]

[[da:Distribuerede beregninger]]

[[de:Verteiltes Rechnen]]

[[el:Παράλληλα και κατανεμημένα συστήματα]]

[[en:Distributed computing]]

[[eo:Disa komputado]]

[[es:Computación distribuida]]

[[et:Hajusarvutus]]

[[fa:رایانش توزیع‌شده]]

[[fi:Hajautetut järjestelmät]]

[[fr:Calcul distribué]]

[[he:חישוב מבוזר]]

[[hu:Elosztott számítások]]

[[id:Komputasi terdistribusi]]

[[ja:分散コンピューティング]]

[[kk:Мәліметтерді үлестіре өңдеу]]

[[ko:분산 컴퓨팅]]

[[lt:Paskirstytasis skaičiavimas]]

[[mk:Дистрибуиран компјутерски систем]]

[[ms:Pengkomputeran teragih]]

[[nl:Distributed computing]]

[[nn:Distribuert datahandsaming]]

[[pl:Obliczenia rozproszone]]

[[pt:Computação distribuída]]

[[ro:Calcul distribuit]]

[[ru:Распределённые вычисления]]

[[simple:Distributed computing]]

[[sk:Distribuovaný výpočet]]

[[sv:Distributed computing]]

[[ta:விரவல் கணினி செய்முறை]]

[[tr:Dağıtık hesaplama]]

[[uk:Розподілені обчислення]]

[[vi:Điện toán phân tán]]

[[zh:分布式计算]]