10-09-2013, 04:20 PM
Basic Algorithms
Basic Algorithms.pdf (Size: 1,016.37 KB / Downloads: 289)
Formal Model of Message-Passing Systems
There are n processes in the
system: p0, .., pn-1
Each process is modeled as
a state machine.
The state of each process is
comprised by its local variables and a set of arrays.
For instance, for p0, the state includes six arrays:
inbuf0[1], ..., inbuf0[3]: contain messages that have been
sent to p0 by p1, p2 and p3, respectively, but p0 has not yet
processed.
outbuf0[1], ..., outbuf0[3]: messages that have been sent by
p0 to p1, p2, and p3, respectively, but have not yet been
delivered to them.
Formal Model of Message-Passing Systems
The state of process pi excluding the outbufi[l]
components, comprises the accessible state of pi.
Each process has an initial state in which all inbuf
arrays are empty.
At each step of a process, all messages stored in
the inbuf arrays of the process are processed, the
state of the process changes and a message to each
other neighboring process can be sent.
A configuration is a vector C = (q0, .., qn-1) where qi
represents the state of pi.
The states of the outbuf variables in a configuration
represent the messages that are in transit on the
communication channels.
In an initial configuration all processes are in initial states.
Formal Model of Message-Passing Systems
Complexity Measures
The message complexity of an algorithm for
either a synchronous or an asynchronous
message-passing system is the maximum,
over all executions of the algorithm, of the
total number of messages sent.
The time complexity of an algorithm for a
synchronous message-passing system is the
maximum number of rounds, in any
execution of the algorithm, until the
algorithm has terminated.
Broadcast on a Spanning Tree
A distinguished processor, pr, has a message <M> it wishes to send to
all other processors.
Copies of the message are to be sent along a tree which is rooted at
pr, and spans all the processors in the network.
The spanning tree is maintained in a distributed fashion:
Each processor has a distinguished channel that leads to its
parent, as well as a set of channels that lead to its children.
Broadcast on a spanning tree - Time Complexity
Synchronous System
Lemma: In every execution of the broadcast algorithm in
the synchronous model, every process at distance t from pr
in the spanning tree receives <M> in round t.
Proof: By induction on the distance t of a process from pr.
t = 1. Each child of pr receives <M> from pr in the first
round.
Assume that every process at distance t-1 ≥ 1 from pr
receives the message <Μ> in round t-1.
Let p be any process in distance t from pr. Let p’ be the
parent of p in the spanning tree. Since p’ is at distance t-1
from pr, by the induction hypothesis, p’ receives <M> in
round t-1. By the description of the algorithm, p receives
<M> from p’ in the next round.
Synchronous Systems
We define a directed spanning tree of a directed graph G = (V,E) to
be a rooted tree that consists entirely of directed edges in E, all
edges directed from parents to children in the tree, and that
contains every vertex of G.
A directed spanning tree of G with root node pr is breadth-first
provided that each node at distance d from pr in G appears at depth
d in the tree (that is at distance d from pr in the tree).
Every strongly connected digraph has a breadth-first directed
spanning tree.
Given that the G is a strongly connected directed graph and given
that we have a distinguished node pr, how can we design a
synchronous algorithm that computes the directed BFS tree?
How can a process learn which nodes are its children?
What is the communication complexity of the algorithm in this case?
What is the time complexity of the algorithm in this case?
How can pr learn that the construction of the spanning tree has
terminated?
The Leader Election Problem
Each process should eventually decide that it is
either the leader or it is not the leader.
Exactly one process should decide that it is the
leader.
The leader process may be responsible for
achieving synchronization in future activities of
the system:
token re-creation
recovery from deadlock
play the role of the root node in the construction
of a spanning tree, etc.