756 pág.

Distributed Computing (2008)

DisciplinaAlgorítimos Distribuídos28 materiais272 seguidores
Pré-visualização50 páginas
```then
(2e) send ACCEPT(myroot) to j; terminate. // leaf node
(2f) else send REJECT(newroot) to j.
// if newroot =myroot then parent is already identified.
// if newroot < myroot ignore the QUERY. j will update its root
// when it receives QUERY(myroot).
(3) When ACCEPT(newroot) arrives from j:
(3a) if newroot =myroot then
(3b) Children\u2190\u2212 Children\u222a 	j\ufffd;
(3c) if \ufffdChildren\u222aUnrelated\ufffd= \ufffdNeighbors/	parent\ufffd\ufffd then
(3d) if i=myroot then
(3e) terminate.
(3f) else send ACCEPT(myroot) to parent.
// if newroot < myroot then ignore the message. newroot > myroot
// will never occur.
(4) When REJECT(newroot) arrives from j:
(4a) if newroot =myroot then
(4b) Unrelated\u2190\u2212 Unrelated\u222a 	j\ufffd;
(4c) if \ufffdChildren\u222aUnrelated\ufffd= \ufffdNeighbors/	parent\ufffd\ufffd then
(4d) if i=myroot then
(4e) terminate.
(4f) else send ACCEPT(myroot) to parent.
// if newroot < myroot then ignore the message. newroot > myroot
// will never occur.
Algorithm 5.3 Spanning tree algorithm (asynchronous) without assuming a designated root. Initiators
use flooding to start the algorithm. The code shown is for processor Pi , 1\u2264 i \u2264 n.
145 5.5 Elementary graph algorithms
Figure 5.4 Example execution
of the asynchronous
flooding-based concurrent
initiator spanning tree
algorithm (Algorithm 5.3).
A
C
D
B
E F
JIHG
Interestingly, even if there are just two initiations, the two partially com-
puted trees may \u201cmeet\u201d along multiple edges in the graph, and care must be
taken not to introduce cycles during the merger of the trees.
Design 2
Suppress the instance initiated by one root and continue the instance initiated
by the other root, based on some rule such as tie-breaking using the processor
identifier. Again, it must be ensured that the rule is correct.
Example In Figure 5.4, if A\u2019s initiation is suppressed due to the conflict
detected along BD, G\u2019s initiation is suppressed due to the conflict detected
along HI, and J\u2019s initiation is suppressed due to the conflict detected along
CF, the algorithm hangs.
Algorithm 5.3 uses the second design option, allowing only the algorithm
initiated by the root with the higher processor identifier to continue. To
implement this, the messages need to be enhanced with a parameter that
indicates the root node which initiated that instance of the algorithm. It is
relatively more difficult to use the first option to merge partially computed
spanning trees.
When a QUERY(newroot) from j arrives at i, there are three possibilities:
newroot > myroot: Process i should suppress its current execution due to
its lower priority. It reinitializes the data structures and joins j\u2019s subtree
with newroot as the root.
newroot =myroot: j\u2019s execution is initiated by the same root as i\u2019s initia-
tion, and i has already identified its parent. Hence a REJECT is sent to j.
newroot < myroot: j\u2019s root has a lower priority and hence i does not
join j\u2019s subtree. i sends a REJECT. j will eventually receive a
QUERY(myroot) from i; and abandon its current execution in favour of
i\u2019s myroot (or a larger value).
146 Terminology and basic algorithms
When an ACCEPT(newroot) from j arrives at i, there are three possibilities:
newroot =myroot: The ACCEPT is in response to a QUERY sent by i.
The ACCEPT is processed normally.
newroot < myroot: The ACCEPT is in response to a QUERY i had sent
to j earlier, but i has updated its myroot to a higher value since then.
Ignore the ACCEPT message.
newroot > myroot: The ACCEPT is in response to a QUERY i had sent
earlier. But i never updates its myroot to a lower value. So this case
cannot arise.
The three possibilities when a REJECT(newroot) from j arrives at i are the
same as for the ACCEPT message.
Termination
A serious drawback of the algorithm is that only the root knows when its
algorithm has terminated. To inform the other nodes, the root can send a
special message along the newly constructed spanning tree edges.
Complexity
The time complexity of the algorithm is O\ufffdl\ufffd messages, and the number of
messages is O\ufffdnl\ufffd.
5.5.4 Asynchronous concurrent-initiator depth first search spanning tree algorithm
As in Algorithm 5.3, this algorithm assumes that any node may spontaneously
initiate the spanning tree algorithm provided it has not already been invoked
locally due to the receipt of a QUERY message. It differs from Algorithm 5.3
in that it is based on a depth-first search (DFS) of the graph to identify the
spanning tree. The algorithm should handle concurrent initiations (when two
or more processes that are not yet participating in the algorithm initiate the
algorithm concurrently). The pseudo-code for each process Pi is shown in
Algorithm 5.4. The parent of each node is that node from which a QUERY
is first received; an ACCEPT message is sent in response to such a QUERY.
Other QUERY messages received are replied to by a REJECT message.
The actions to execute when a QUERY, ACCEPT, or REJECT arrives are
nontrivial and the analysis for the various cases (newroot <\ufffd=\ufffd> myroot)
are similar to the analysis of these cases for Algorithm 5.3.
Termination
The analysis is the same as for Algorithm 5.3.
Complexity
The time complexity of the algorithm is O\ufffdl\ufffd messages, and the number of
messages is O\ufffdnl\ufffd.
147 5.5 Elementary graph algorithms
(local variables)
int parent\ufffdmyroot\u2190\u2212\u22a5
set of int Children\u2190\u2212\u2205
set of int Neighbors\ufffdUnknown\u2190\u2212 set of neighbors
(message types)
QUERY, ACCEPT, REJECT
(1) When the node wants to initiate the algorithm as a root:
(1a) if (parent =\u22a5) then
(1b) send QUERY(i) to i (itself).
(2) When QUERY(newroot) arrives from j:
(2a) if myroot < newroot then
(2b) parent\u2190\u2212 j; myroot\u2190\u2212 newroot; Unknown\u2190\u2212 set of
neighbors;
(2c) Unknown\u2190 Unknown/	j\ufffd;
(2d) if Unknown \ufffd= \u2205 then
(2e) delete some x from Unknown;
(2f) send QUERY(myroot) to x;
(2g) else send ACCEPT(myroot) to j;
(2h) else if myroot = newroot then
(2i) send REJECT to j. // if newroot < myroot ignore the query.
// j will update its root to a higher root identifier when it receives its
// QUERY.
(3) When ACCEPT(newroot) or REJECT(newroot) arrives from j:
(3a) if newroot =myroot then
(3b) if ACCEPT message arrived then
(3c) Children\u2190\u2212 Children\u222a 	j\ufffd;
(3d) if Unknown= \u2205 then
(3e) if parent \ufffd= i then
(3f) send ACCEPT(myroot) to parent;
(3g) else set i as the root; terminate.
(3h) else
(3i) delete some x from Unknown;
(3j) send QUERY(myroot) to x.
// if newroot < myroot ignore the query. Since sending QUERY to j, i
// has updated its myroot.
// j will update its myroot to a higher root identifier when it receives a
// QUERY initiated by it.
// newroot > myroot will never occur.
Algorithm 5.4 Spanning tree algorithm (DFS, asynchronous). The code shown is for processor Pi ,
1\u2264 i \u2264 n.
148 Terminology and basic algorithms
Figure 5.5 A generic spanning
tree on a graph. The broadcast
and convergecast operations
are indicated.
B
ro
ad
ca
st
Co
nv
er
ge
ca
st
in
iti
at
ed
b
y
le
av
es
Root
in
iti
at
ed
b
y
ro
ot
Tree edge
Cross-edge Back-edge
5.5.5 Broadcast and convergecast on a tree
A spanning tree is useful for distributing (via a broadcast) and collecting (via
a convergecast) information to/from all the nodes. A generic graph with a
spanning tree, and the convergecast and broadcast operations are illustrated
in Figure 5.5.
A broadcast algorithm on a spanning tree can be specified by two rules:
BC1: The root sends the information to be broadcast to all its children.
Terminate.
BC2: When a (nonroot) node receives information from its parent, it copies
it and forwards it to its children. Terminate.
A convergecast algorithm collects information from all the nodes at the
root node in order to compute some global function. It is initiated by the leaf
nodes of the tree, usually in response to receiving a request sent by the root
using a broadcast. The algorithm```