Università degli studi di L’Aquila
Anno Accademico 2008/2009
Corso di: Algoritmi per Sistemi Distribuiti
Titolare: Prof. Guido Proietti
Orario:
Ricevimento:
Martedì:
Giovedì:
Martedì
15.15 – 17.00 – Aula 2.5
15.15 – 17.00 – Aula 2.5
17.00-19.00
Testi e Riferimenti: Dispense + Slide
http://www.di.univaq.it/~proietti/didattica.html
Distributed System
Set of computational devices connected by a communication network.
Old platform : Usually a number of WSs over a LAN
Now, ranges from a LAN to a sensor network to a mobile network
Each node in a DS :



is autonomous
communicates by messages
needs to synchronize with others to achieve a common goal (load
balancing, fault tolerance, an application..)
Modern Distributed Applications
Collaborative computing
Military command and control
Online strategy games
Massive computation



Distributed Real-time Systems
Process Control
Navigation systems, Airline Traffic Monitoring (ATM)


Mobile Ad hoc Networks
Rescue Operations, emergency operations, robotics
Wireless Sensor Networks
Habitat monitoring, intelligent farming
Grid
Stock market
…
The Internet
Some Issues in Building Distributed Applications
Reliability (connectivity)
Security (cryptography)
Consistency (mutual exclusion)
Cooperativeness (game theory)
Fault-tolerance (failures, recoveries…)
Scalability: How is the performance affected as the number of
nodes increase ?
Performance: What is the complexity of the designed
algorithm?
Distributed Algorithms: A Perspective (K. Erciyes 2007)
Struttura del corso
PRIMA PARTE: Algoritmi per sistemi distribuiti COOPERATIVI
1. Elezione del leader
2. Minimo albero ricoprente
SECONDA PARTE: Algoritmi per sistemi distribuiti INAFFIDABILI
1. Fallimenti benigni: Problema del consenso
2. Fallimenti bizantini: Problema del consenso
TERZA PARTE: Algoritmi per sistemi distribuiti CONCORRENTI
1. Problemi di condivisione risorse: Algoritmi di mutua esclusione
Prova parziale: Esame scritto Martedì 18 Novembre (?)
QUARTA PARTE: Sicurezza nei sistemi distribuiti
1. Elementi di crittografia
QUINTA PARTE: Algoritmi per sistemi distribuiti NON COOPERATIVI
1. Teoria degli equilibri strategici
2. Progettazione algoritmica di meccanismi
3. Meccanismi per problemi di ottimizzazione su grafi
SESTA PARTE (???): Algoritmi per RETI WIRELESS
Prova finale: Esame Orale (ristretto alla seconda metà del corso per gli
esonerati alla prova parziale)
Cooperative distributed
algorithms:
Message Passing System
A Formal Model
The System
 Topology: a network (connected undirected graph)
 Processors (nodes)
 Communication channels (edges)
 Degree of synchrony: asynchronous versus
synchronous (universal clock)
 Degree of symmetry: anonymous (processors are
indistinguishable) versus non-anonymous
 Degree of Uniformity: uniform (number of
processors is unknown) versus non-uniform
Local algorithm: the algorithm associated to a single
processor
Distributed algorithm: the “composition” of local
algorithms
Notation
 n processors: p0, p1, … , pn-1.
 Each processor knows nothing about the
network topology, except for its neighbors,
numbered from from 1 to r
 Communication takes place only through
message exchanges, using buffers
associated with each neighbor, namely
outbufi[k], inbufi[k], k=1,…,r.
 Qi : the state set for pi, containing a
distinguished initial state; each state
describes the internal status of the
processor and the status of the buffers
Configuration and events
System configuration: A vector
[q0,q1,…,qn-1] where qi is the state of pi
Events: Computation events (internal
computations plus sending of
messages), and message delivering
events
Execution
C0 1 C1 2 C2 3 … where
Ci : A configuration
i : An event
C0 : An initial configuration
Asynchronous Systems
No upper bound on delivering times
Admissible execution: each message
sent is eventually delivered
Synchronous Systems
 Each processor has a (common)
clock, and computation takes place
in rounds.
 At each round each processor:
1. Reads the incoming messages buffer
2. Makes some internal computations
3. Sends messages which will be read in
the next round.
Message Complexity
 The total number of messages sent
during any admissible execution of
the algorithm.
 In other words, the number of
delivery events.
Time Complexity
 Synchronous: The number of rounds
until termination.
Asynchronous: not really meaningful
• Example: Distributed Depth-First Search
– General overview
• Algorithm
– Begin at some source vertex, r0
– when reaching any vertex v
» if v has an unvisited neighbor, then visit it and proceed
from it
» otherwise, return to parent(v)
– when we reach the parent of some vertex v such that
parent(v) = NULL, then we terminate since v = r0
• DFS defines a tree, with r0 as the root, which
reaches all vertices in the graph
– “back edges” = graph edges not in tree
– sequential time complexity = O(|edges|)
• Distributed DFS (cont’d.)
– distributed version = token-based: the token
traverses the graph in a depth-first manner
using the algorithm described above
1. Start exploration (visit) at root r.
2. When v is visited for the first time:
2.1 Inform all neighbors of v that v has been visited.
2.2 Wait for acknowledgment from all neighbors.
2.3 Resume the DFS process.
– Message complexity is O(|E|) (lower bound of
(|edges|) to explore every edge)
» note that edges are not examined from both
endpoints; when edges (v,w) is examined by v, w
then knows that v has been visited
• Distributed DFS (cont’d.)
• Time complexity analysis
– time:
»ensure that vertices visited for the first
time know which of their neighbors
have/have not been visited; thus we make
no unnecessary vertex explorations
»algorithm: freeze the DFS process;
inform all neighbors of v that v has been
visited; get Ack messages from those
neighbors; restart DFS process
»additional cost each time a vertex is
first visited = O(1)
»only edges of the DFS tree are
traversed
»therefore, time complexity = O(n)