Calcolo distribuito: differenze tra le versioni

Versione delle 21:18, 1 mag 2012

Versione attuale delle 15:29, 30 dic 2024

(40 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 questa trattazione, le entità computazionali verranno 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 distribuitdistribuito: 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 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 ==

Riga 77 ⟶ 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 88 ⟶ 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 107 ⟶ 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 116 ⟶ 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 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 133 ⟶ 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 166 ⟶ 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 174 ⟶ 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:分布式计算]]