Università degli Studi dell’Aquila
Academic Year 2010/2011 Course: Algorithms for Distributed Systems
Instructor: Prof. Guido Proietti
Time: Monday: 11.45 – 13.15 – Room 2.5
Wednesday: 11.45 – 13.15 – Room 2.5
Questions?: Wednesday 16.00-17.00
Slides plus other infos:
http://www.di.univaq.it/~proietti/didattica.html
Università degli Studi dell’Aquila
Academic Year 2010/2011 Course: Algorithms for Distributed Systems
Instructor: Prof. Guido Proietti
Time: Monday: 11.45 – 13.15 – Room 2.5
Wednesday: 11.45 – 13.15 – Room 2.5
Questions?: Wednesday 16.00-17.00
Slides plus other infos:
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…)
Performance: What is the efficiency of the designed algorithm?
Scalability: How is the performance affected as the number of processors increase ?
Course structure FIRST PART: Algorithms for COOPERATIVE DS
Leader Election
Minimum spanning tree
Maximal independent set
SECOND PART: Algorithms for UNRELIABLE DS
Benign failures: consensus problem
Byzantin failures: consensus problem
THIRD PART: Algorithms for CONCURRENT DS
Mutual exclusion
Mid-term Written Examination: Last week of November
FOURTH PART: DS SECURITY
Elements of cryptography
FIFTH PART: Algorithms for NON COOPERATIVE (STRATEGIC) DS
Strategic equilbria theory
Algorithmic mechanism design (AMD)
AMD for Graph optimization problems
SIXTH PART (???): Algorithms for WIRELESS DS
Final Oral Examination: depending of the mid-term rate
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], i=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:
Reads the incoming messages buffer
Makes some internal computations
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).
However, the size of a message will count as well…
Time Complexity Synchronous: The number of rounds until termination.
Asynchronous: not really meaningful
Example: Distributed Depth-First Search
General overview of a sequential 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|+|nodes|)
DFS: an example (1/2)
DFS: an example (2/2)
Distributed DFS (cont’d.)
Distributed version (token-based): the token traverses the graph in a depth-first manner using the algorithm described above
Start exploration (visit) at a waking-up node (root) r.
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.
2.4 If no undiscovered node exists, then pass token to the parent node
Message complexity is O(|E|) (optimal, because of the 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 (sync. DS)
We 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 constant number of rounds (i.e., 2) for each new discovered node
only O(n) nodes are discovered time complexity = O(n)
Comments