Chapter 19
Distributed Network Algorithms
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Lecture Notes
Overview
In Chapter 19 we introduce distributed network algorithms. We assume that we are
working with a network of processors where a given processor only can send messages
directly to its neighbors in the network, and messages to other processors must be
forwarded using flooding or other methods of broadcasting. While each processor knows
its neighbors, the number of processors and the global topology of the network are
typically not assumed to be known. Thus we design and analyzed distributed algorithms
to determine global properties of the topology of the network, such as shortest paths,
diameter, minimum spanning tree, and so forth.
Chapter Objectives
After completing the chapter the student will know:
Solutions to Selected Exercises
Section 19.1 Leader Election
19.1 It is clear that after the first n rounds, the processor r with the maximum UID will
have received its own UID from his counterclockwise neighbor. After processor r
19.2 We prove by induction on the number of rounds k that each node within a distance k
of the node r having the maximum UID = r:UID will have updated their value of
MaxUID to that maximum.
19.3 The communication complexity of LeaderElection can be improved by adding a
variable v:flag initialized to .true., and updated during each round depending on whether
or not the variable v:MaxUID is updated during that round. A given node v will only
send its current value of v:MaxUID to all its neighbors if v:MaxUID was updated in the
previous round. The pseudocode for this updated version LeaderElection2 follows.
forall v do
if v:flag = .true. then
send v:MaxUID to all neighbors in Nv
v:flag ← .false.
endif
v:LeaderStatus ← Leader
else
v:LeaderStatus ← Not Leader
endif
endforall
19.4
UID
Parent
Child List
Round 1
Round 2
Round 3
Round 4
1047
3692
1964
*
1085
none
{1711,3217,3222,3692}
1415
1711
{}
*
1711
1085
{1415,1937}
*
1933
1937
{}
*
1937
1711
{}
*
1938
4123
{}
*
1955
1964
{}
*
1962
1964
{}
*
1964
1047
{1955,1962}
*
3211
3217
{}
*
3217
1085
{3211,4123,4294}
*
3222
1085
{}
*
3692
1085
{1047}
*
4123
3217
{1938}
*
4294
3217
{}
*
* =
receive
broadcast
19.5
UID
Round 1
Round 2
Round 3
Round 4
1047
1964
1085
3222
1711, 3217
3692
1415
1711
1415
1937
1933
1937
1933
1938
1955
1962
1964
1955, 1962
3211
3217
3211, 4294
4123
3222
3692
1047
4123
1938
4294
19.6
UID
Degree
Round 1
Round 2
Round 3
Round 4
1047
2
7
1085
4
5
21
30
1415
1
1711
3
4
7
1933
1
1937
1
3
1938
1
1955
1
1962
1
1964
3
5
3211
1
3217
4
6
9
3222
1
3692
2
9
4123
2
3
4294
1
19.7 We first show by induction on the number of rounds that all nodes of distance k
from the root node s are added to the breadth-first search tree in round k.
Basis step: k = 0. Trivial, since s is added to the tree by the first two initialization
statements.
19.9 Using induction on k, we prove the after k rounds, v:Dist is no greater than the
length of a shortest path from s to v using at most k edges.
Basis step: k = 0. Trivial.
19.10 FloydDistributed makes n passes (rounds), and during each pass a broadcast to all
nodes performed. Since the broadcast takes O(n) rounds, and during each round of the
19.11 The following is a high-level description of the pseudocode for MSTDistributed.
procedure MSTDistributed(G)
Model: A weighted distributed network G, with
Input: each node knows its weighted adjacency list
Output: each node knows its children list in the minimum spanning tree
delete uv from List of Children
endif
endif
if v:LeaderStatus = .true. then
v:Leader ← v:UID
minimum cost edges from all nodes in their tree, and then compute minimum
cost edge amongst all minimum cost edges received.
if v:LeaderStatus = .true. then
if no minimum cost edge received then
finnished ← .true.
19.12 As discussed in the text, MSTDistributed terminates after at most O(logn) stages,
since the number of supervertices is a least halved during each stage. Moreover, the
19.13 Note: For convenience, we take the UID of each node to be its index. In the first
printing of the text, we took the UID to be one more than the index, but changed it to be
the index itself in subsequent printings for greater clarity.
PHASE 1
PHASE 2
PHASE 3
UID
Tree Adjac.
List
Child
List
Leader
Added
Adjac.
Child
List
Leader
Added
Adjac.
Child
List
Leader
0
{1}
{}
1
{}
8
{}
9
1
{1,3,5,6}
{0,2,3,4}
1
{0,2}
8
{0,2}
9
2
{1,3}
{3}
1
{3}
8
{}
9
3
{2}
{}
1
{}
8
{}
9
4
{1}
{}
1
5,8
{1,5}
8
{1,5}
9
5
{15}
{}
15
4
{15}
8
{}
9
6
{10}
{}
10
{}
13
{}
9
7
{8}
{}
8
{}
8
{}
9
8
{7}
{7}
8
4
{4,7}
8
9
{4,7}
9
9
{13,14}
{14}
13
{15}
13
8
{8,13,14}
9
10
{6}
{6}
10
11
{7}
13
{6}
9
11
{12}
{}
12
10
{11}
13
{10}
9
12
{11}
{11}
12
13
{12}
13
{11}
9
13
{9}
{}
13
12
{9,12}
13
{12}
9
14
{9}
{10}
13
{}
13
{}
9
15
{5}
{5}
15
{}
13
{}
9