1
Sistemi Distribuiti
Corso di Laurea Magistrale in Informatica
Indirizzo Reti
Facoltà di Scienze Matematiche Fisiche e Natuali
Docente: Prof. Alberto Negro
Obiettivi Formativi
1.
In questo corso tratteremo alcuni dei concetti fondamentali alla
base dei moderni sistemi distribuiti.
2. Ci occuperemo dei fondamenti: problemi, protocolli, algoritmi e
limiti insormontabili.
3. Vedremo, anche nei dettagli, le idee usate nella costruzione dei
sistemi Peer-to-Peer (P2P).
4. Infine descriveremo una piattaforma per applicazioni P2P: JXTA.
3 e 4 sono mutuati dal corso di Sistemi P2P (3CFU).
2
3
Contenuti
• Parte A) Sistemi distribuiti: Fondamenti.
▫ Introduzione ai Sistemi Distribuiti
4
Contenuti
• Parte B) Sistemi P2P
▫ Introduzione alle Architetture Parallele L’Ipercubo, la
Butterfly (CCC e Benes), i grafi di de Bruijn.
▫ Introduzione ai sistemi P2P
▫ Reti P2P non strutturate: Random Graphs, Small-Worlds
and Scale-Free Networks
▫ Reti P2P strutturate
▫ Reti Uniformi e Reti Randomizzate
▫ Strategie di Routing
▫ Reti non Uniformi: Koorde
5
Contenuti
• Parte C) JXTA
▫
▫
▫
▫
▫
Introduzione a JXTA
Architettura di JXTA
Le componenti e i protocolli di JXTA
Comunicazione in JXTA: Pipe, BidiPipe e Socket
Esempi di utilizzo e Applicazioni
6
Testi
1. R.Steinmetz, K. Wehrle, Peer to Peer Systems
and Applications, LNCS. 3485, Springer
Verlag, 2005
2. F. Thompson Leighton, Introduction to Parallel
Algorithms and Architectures: Array Trees
Hypercubes.
3. Ajay D. Kshemkalyani and Mukesh Singhal.
Distributed Computing: Principles, Algorithms,
and Systems, Cambridge University Press,
2008. ISBN-13 978-0-521-87634-6.
4. JXTA Programmers guide.
7
Modalità di Esame
• Scritto + Orale (progetto JXTA facoltativo)
8
9
Introduzione ai Sistemi Distribuiti
Gennaro Cordasco
Dipartimento di Informatica - Università degli Studi di Salerno
cordasco[@]dia.unisa.it
cordasco+sd[@]gmail.com
http://www.dia.unisa.it/~cordasco
Laboratorio ISISLAB2
Sistema Distribuito
• Una collezione di dispositivi
autonomi che comunicano
attraverso una rete di
interconnessione
10
Caratteristiche dei SD
• I dispositivi non hanno un clock comune
• Non c’è una shared memory
• I dispositivi lavorano in maniera autonoma e
sono tipicamente eterogenei
• … sono separati geograficamente
11
I Sistemi distribuiti (SD) sono:
Incredibilmente flessibili
Incredibilmente efficienti
Difficili da mettere a punto…...
Hardware eterogeneo
Asincronia
Conoscenza locale limitata
Fallimenti
12
Gli Algoritmi Distribuiti:
Algoritmo Distribuito:
- Algoritmo per un Sistema Distribuito
Sono difficili da progettare:
Non c’è un modello accettato
Message passing vs shared memory
Timing
Failure
E’ difficile dimostrarne la correttezza
13
Gli Algoritmi Distribuiti:
Usano il numero totale dei messaggi spediti come
misura di complessità
Usano anche il tempo come misura di complessità
14
Perchè computazione distribuita?
• L’alternativa è un’architettura centralizzata
– un singolo mainframe con terminali stupidi
• Alcuni problemi:
– se il mainframe non è disponibile, nessuna
computazione è possibile
– consumo di banda sulla rete per dati (anche
per i dati locali ai terminali)
– costo e mantenimento alto del mainframe
– terminali stupidi con capacità di calcolo
notevoli
15
Motivazioni per il Calcolo Distribuito
• Utilizzo parallelo di risorse distribuite
– CPU
– Memoria
• Data Set difficilmente rilocabili vengono
processati localmente
• Fault-tolerance
• Scalabilità
• Modularità
• Rapporto Prestazioni/Prezzo
– attenzione alla manutenzione
16
Le prestazioni di un Sistema Distribuito
• La capacità di un sistema distribuito può facilmente
eccedere quella di un calcolatore a singolo processore:
• 5000 Pentium a 200 MIPS=1.000.000 MIPS
• Una singola CPU così veloce dovrebbe eseguire
una operazione ogni 10-12 secondi
• In 10-12 secondi alla velocità della luce si
coprono solo 0.3 millimetri
• Una CPU in 0.3 millimetri crea problemi di
surriscaldamento
17
Modello dei SD
18
Differenza con i Sistemi Paralleli
• Array processors (processori strettamente
accoppiati)
• Multiprocessori (con accesso diretto alla shared
memory UMA)
▫ Diversi tipi di interconnessione (bus, multistage switch,
come ad esempio butterfly oppure shuffle exchange
network)
• Multicomputer parallel systems (processori
omogenei con una propria memoria NUMA)
▫ Non c’è una memoria condivisa
▫ Utilizzano una specifica rete di interconnessione (ring,
mesh, ipercubo)
19
UMA vs NUMA Models
20
Butterfly and Hypercube networks
21
Tassonomia di Flynn
• SISD: Single Instruction Stream Single Data Stream
▫ Modello tradizionale
• SIMD: Single Instruction Stream Multiple Data Stream
▫ Applicazioni scientifiche su dati di grande dimensione
▫ vector processors, systolic arrays, Pentium/SSE, DSP chips
• MISD: Multiple Instruciton Stream Single Data Stream
▫ Meno usato
• MIMD: Multiple Instruction Stream Multiple Data
Stream
▫ Il modello più potente, ma anche il più complesso
▫ La maggior parte dei sistemi paralleli e distribuiti
22
Terminologia
• Accoppiamento (Coupling): livello di
interdipendenza fra i moduli di un SD
(tightly/loosely)
• Parallelismo o SpeedUp, T(1)/T(n): misura
l’accelerazione ottenuta usando n moduli invece di
1.
• Concorrenza: rapporto fra il tempo speso a fare
computazione ed il tempo totale speso (include
tempo di comunicazione, sincronizzazione)
• Granularità di un programma
23
Message Passing vs Shared memory
• Shared Memory: La comunicazione fra i
processori si basa su una zona di memoria
condivisa
▫ Tightly coupled multiprocessor
▫ Problema: gestione dei conflitti di accesso
concorrente alla memoria
• Message Passing: I computer comunicano
attraverso lo scambio di messaggi asincrono
▫ Loosely coupled systems
24
SD Obiettivi (Sistema)
• Diverse problematiche devono essere affrontate
nella realizzazione di un SD:
▫
▫
▫
▫
▫
▫
Comunicazione
Gestione dei processi
Naming
Synchronizzazione
Data Storage
Consistency and Replication
25
SD Obiettivi (Sistema)
▫
▫
▫
▫
▫
Fault-tolerance (nodi/link)
Security
Scalability
API
Trasparenza
26
SD Obiettivi (Algoritmi)
▫ Modello di esecuzione
 Interleaving
 Partial order
▫ Algoritmi distribuiti su grafi dinamici
 Topologia del sistema
 Algoritmi su grafi (permettono la comunicazione, la
sincronizzazione ecc.)
 Topologia dinamica
 Efficienza
▫ Timing
27
SD Obiettivi (Algoritmi)
▫ Sincronizzazione






Logical time
Leader Election
Mutual exclusion
Distributed deadlock detection and resolution
Distributed termination detection
Distributed garbage collection
28
SD Obiettivi (Algoritmi)
• Group communication, multicast, and ordered message
delivery
▫ Group: processi che condividono un contesto e/o che
collaborano
▫ joins, leaves, fails
▫ Invio concorrente dei messaggi: gestione della semantica
dell’ordine di arrrivo
• Monitoring distributed events and predicates
▫ Predicate: condition on global system state
▫ Debugging
• Progettazione dei programmi distribuiti e dei tool di
verifica
• Debugging di programmi distribuiti
29
SD Obiettivi (Algoritmi)
• Data replication, consistency models, and caching
▫ Fast, scalable access
▫ coordinate replica updates
▫ optimize replica placement
• Reliable and fault-tolerant distributed systems
▫ Failure detectors:
 Difficult to distinguish a "slow" process/message from a
failed process/ never sent message
 algorithms that "suspect" a process as having failed and
converge on a determination of its up/down status
30
SD Obiettivi (Algoritmi)
• Load Balancing
▫ Computation migration
▫ Data migration
▫ Distributed scheduling
• Come comparare gli algoritmi
▫ Metriche
31
SD Applicazioni
•
•
•
•
•
•
•
•
•
Mobile systems
Sensor networks
Ubiquitous and pervasive computing (domotica)
Peer to Peer computing
Publish and Subscribe content distribution
Distributed agents
Distributed data mining
Grid Computing
Security
32