Introduction to distributed computing

Distributed Graph Algorithms

for DISTRIBUTED SYSTEMS

Michel RAYNAL
Institut Universitaire de France
Academia Europaea
IRISA, Université de Rennes, France
Polytechnic University (PolyU), Hong Kong

c M. Raynal, Distributed Graph Algorithms 1

 WHY study Graph algorithms????

Because

• Graphs are inherent to distributed computing

• Distributed algorithms 6= sequential/parallel algorithms
• Nearly all distributed graph algo. cannot be obtained
by simple extensions of their sequential counterpart
• The principles used to solve distributed graph problems
are paradigmatic (can be re-used for other problems)
• They are not so difficult to understand and master!
• Algorithmics is at the core of informatics!

c M. Raynal, Distributed Graph Algorithms 2

Companion Book (1)

Distributed algorithms for

Message-passing systems
by Michel Raynal
Springer, 517 pages, 2013
ISBN 978-3-642-38122-5

c M. Raynal, Distributed Graph Algorithms 3

 Companion Book (2): content (six parts)

• Part 1: Distributed graph algorithms

(5 chap., pp. 1-118)
• Part 2: Logical time and global states
(4 chap., pp. 119-244)
• Part 3: Mutual exclusion and resource allocation
(2 chap., pp. 244-300)
• Part 4: High level communication abstractions
(2 chap., pp. 301-364)
• Part 5: Detection of properties of distributed executions
(2 chap., pp. 365-423)
• Part 6: Distributed shared memory
(2 chap., pp. 425-470)

c M. Raynal, Distributed Graph Algorithms 4

 Table of contents

• Base definitions and network traversals algorithms (these

slides)
• Basic distributed graph algorithms (these slides)
• An algorithmic framework to compute global functions
• Leader election algorithms
• Mobile objects navigating a network

c M. Raynal, Distributed Graph Algorithms 5

 Base definitions
and network traversals algorithms
(Chapter 1)

c M. Raynal, Distributed Graph Algorithms 6

 Base computation model: processes

• A distributed system is made up of a collection of com-

puting units, each one abstracted through the notion of
a process
• The processes are assumed to cooperate on a common
goal, which means that they exchange information in
one way or another
• The set of processes is static. It is composed of n
processes and denoted Π = {p1, ..., pn}
• Each process pi is sequential, i.e., it executes one step
at a time

c M. Raynal, Distributed Graph Algorithms 7

 Base computation model: communication channel

• The processes communicate by sending and receiving

messages through channels
• Each channel is assumed to be reliable (no message
creation, modification or duplication)
• A channel is FIFO (first in, first out) or not FIFO
• A channel is uni- or bidirectional
• A channel is assumed to have an infinite capacity

c M. Raynal, Distributed Graph Algorithms 8

Base computation model: communication structure

• Each process pi has a set of neighbors, denoted neighborsi

• According to the context, this set contains either the lo-
cal identities of the channels connecting pi to its neigh-
bor processes or the identities of these processes
• Examples of simple communication graphs:

Ring Tree Clique

c M. Raynal, Distributed Graph Algorithms 9

 Distributed algorithm

• A distributed algorithm is a collection of n automata,

one per process
• An automaton describes the sequence of steps executed
by the corresponding process
• In addition to the power of a Turing machine, an au-
tomaton is enriched with two communication opera-
tionswhich allows it to send a message on a channel
or receive a message on any channel

The operations are send() and receive()

c M. Raynal, Distributed Graph Algorithms 10

 Synchronous algorithm

• Progress of the algorithm is governed by an external

global clock,
• The processes execute collectively a sequence of rounds,
each round corresponding to a new value of the global
clock
• A round is made up of three phases

⋆ Send/broadcast phase
⋆ Receive phase
⋆ Local computation
∗ Let δ() be the automaton transition function
∗ new local state ← δ(local state, messages received)

c M. Raynal, Distributed Graph Algorithms 11

 Asynchronous algorithm

• Also called time-free system

• No notion of physical time
• No notion of bounded message transfer
• Each process progresses to its own speed, which can be
arbitrary and is never known by the other processes
• Message transfer delays are arbitrary, but finite
• If needed: as they are not given for free the notions of
logical time and round must to be built by the algo-
rithm itself

c M. Raynal, Distributed Graph Algorithms 12

 Representing a distributed execution

Notion of space-time diagram

Synchronous vs asynchronous

r=1 r=2 r=3

p1 p1

p2 p2

p3 p3

c M. Raynal, Distributed Graph Algorithms 13

 Initial knowledge of a process

Example:
to know the graph is a ring gives no information on n

• Of its identity: anonymous, homonymous, non-anonymous

• Of its neighbors: ports numbers vs process ids
• Of the communication graph
• Of the graph diameter, of the maximal degree, etc.
• Of an order on the identities
• of the value of n
• Etc.
The weaker the initial knowledge, the better

c M. Raynal, Distributed Graph Algorithms 14

 Introductory example: learn the graph

Initial knowledge: each process pi knows

• Its identity idi

• neighborsi = {ids of its neighbors}
• Each (bidirectionnal) channel is identified by the ids of
the processes it connects hidi, idj i

hidi, idj i and hidj , idii denote the same channel

c M. Raynal, Distributed Graph Algorithms 15

Basic of the algorithm: the Forward/discard principle

• position of a process pi is captured by the pair (idi, neighborsi )

• Each process initially sends its position in the graph to
its neighbors
• When a process pi receives the pair (idk , neighborsk ) (po-
sition of pk in the graph):
• First time: UPDATE & FORWARD:
⋆ pi updates its local representation of the comm. graph
⋆ and forwards this new pair to its neighbors

• Otherwise DISCARD:
pi knows the position of pk in the graph, it then dis-
cards the message

c M. Raynal, Distributed Graph Algorithms 16

 Local representation of the graph

• proc knowni = {all proc. whose position is known by pi}

Initially, proc knowni = {idi}
• channels knowni = {all the channels known by pi}
Initially,
channels knowni = {hidi, idj i such that idj ∈ neighborsi }

Aim of the algorithm:

enrich these local data structures at each process pi so
that eventually each of them learns the graph

c M. Raynal, Distributed Graph Algorithms 17

 Lauching the distributed algorithm

• Each process manages a local Boolean variable parti,

initialized to false
• When pi starts participating, it sets parti to true
• A process starts participating

⋆ Either when it receives an external message start()

⋆ Or an internal message position()

• Any number of processes may receive the message start()

• Required: at least one process receives start()

c M. Raynal, Distributed Graph Algorithms 18

 Learning the graph (1)

when start() received do

if (¬parti) then start() end if.

operation start() is
foreach idj ∈ neighborsi
do send position(idi, neighborsi ) to the neighbor idj
end for;
parti ← true
end operation.

c M. Raynal, Distributed Graph Algorithms 19

 Learning the graph (2)

when position(id, neighbors ) received from neighbor idx do

if (¬parti) then start() end if;
if (id ∈
/ proc knowni) then
proc knowni ← proc knowni ∪ {id};
channels knowni ←
channels knowni ∪ {hid, idk i | idk ∈ neighbors };
foreach idy ∈ neighborsi \ {idx}
do send position(id, neighbors ) to the neighbor idy
end for
****************************************
end if.

c M. Raynal, Distributed Graph Algorithms 20

 Two important questions

• Does the algorithm terminates?

• Does a process know that the algorithm terminated?

Reasonable assumption: the comm. graph is connected!

c M. Raynal, Distributed Graph Algorithms 21

 Does the algorithm terminates (correctly)?

• As soon as a process receives a message start(), it sends

its position to its neighbors
• If not yet done, its neighbors sends their position to
their neighbors which forwards them, and so on
• A process forwards a message position(id, neighbors) only
once
• n processes ∧ n messages position() ⇒ O(n2) msgs
• Hence, the algorithm terminates
• But, Does the algorithm terminate correctly, i.e., at
each process pi does the pair of local variables proc knowni
and channels knowni describe the communication graph?
Yes ⇐
from neighbor to neighbor, every pair (idk , neighborsk )
is eventually sent to each process

c M. Raynal, Distributed Graph Algorithms 22

 Does a process know the algorithm terminated?

• Can we state a predicate Pi() that becomes true when

pi knows the whole graph?
• the line “*******************” becomes
if Pi() then pi knows the graph and can stop end if
• Difference between
⋆ Static point of view:
We know the algorithm terminates (we = designer
of the algorithm)
⋆ Dynamic point of view:
A process pi knows it has terminated
⋆ Compare with sequential computing
Distributed computing 6= sequential computing
Distributed computing 6= parallel computing

c M. Raynal, Distributed Graph Algorithms 23

 Local termination predicate

• Assumption: the graph is connected

• How a process knows it has a received a message
position(idk , neighborsk ) from each other process pk ?
• Answer: transitive closure!
• Reminder: each channel is identified by the unordered
pair of the processes it connects hidj , idk i
def
• Pi() =
(∀ hidj , idk i ∈ channels knowni : {idj , idk } ⊆ proc knowni)
• Remark:
The appropriate local representation of the graph
at each process pi proc knowni and channels knowni

c M. Raynal, Distributed Graph Algorithms 24

Broadcast and convergecast

c M. Raynal, Distributed Graph Algorithms 25

 Definitions

• broadcast: one-to-many communication

an algorithm that allows a distinguished process pa to
disseminate information to the whole set of processes
• multicast: one-to-subset communication
The process subset can be statically or dynamically de-
fined at the time of the multicast invocation
• convergecast: all-to-one
• Applications: queries/answers

c M. Raynal, Distributed Graph Algorithms 26

 A (non-efficent) flooding algorithms

Starting from the distinguished process pa, propagation from neighbors to neighbors:

operation broadcast(data) is % issued pa %

for each j ∈ neighborsa do send go(data) to pj end for.

when go(data) is received from pk do

if (first reception of go(data)) then
for each j ∈ neighborsi \ {k} do send go(data) to pj end for
end if.

c M. Raynal, Distributed Graph Algorithms 27

Broadcast and convergecast on a spanning tree (1)

a b

c
i
j

k f
plain blue arrows: spanning tree
g dotted black segments: comm. graph

Two local variables at each pi: parenti and childreni

c M. Raynal, Distributed Graph Algorithms 28

 Broadcast and convergecast on a spanning tree (2)

============= Broadcast =========

when go(data) is received from pk do
for each j ∈ childreni do send go(data) to pj end for.

============= Convergecast ========

when back(val setj ) received

from each pj such
that j ∈ childreni do
val seti ← ∪j∈childreni val setj ∪ {(i, vi)};
let k = parenti;
if (k 6= i) then send back(val seti) to pk
else the root pi (= pa) can compute f (val seti)
end if.

c M. Raynal, Distributed Graph Algorithms 29

 Propagation of Information with
Feedback (PIF)
Implement broadcast and convergecast
Build a spanning tree

c M. Raynal, Distributed Graph Algorithms 30

 Assumptions and principles

• Assumptions

⋆ FIFO channels
⋆ Connected graph

• Underlying principles

⋆ Flooding from the root process

⋆ Notion of “first visit”: defines the parent of a process
⋆ Establishment of the relation: parent ↔ children

c M. Raynal, Distributed Graph Algorithms 31

 Example and Local variables

p2 p2
p4 p4

p1
p3 p1
p3

Communication graph A spanning tree rooted at p1

c M. Raynal, Distributed Graph Algorithms 32

 Local variables and message types

• Local variables

⋆ input: neighborsi at each process pi

⋆ output to be computed: parenti (init ⊥), childreni
⋆ root: dynamically defined by an external message
start(); will be such that parenti = i
⋆ expected msgi: auxiliary variable

• Message types implement a network traversal

⋆ messages go():
from the root to the leaves, define parenti
⋆ messages back():
from the leaves to the root, define childreni

c M. Raynal, Distributed Graph Algorithms 33

Once the tree is built

BACK

GO

c M. Raynal, Distributed Graph Algorithms 34

 Algorithm: processing messages start() and go()

when start() is received do % sent only to the root %

parenti ← i; childreni ← ∅; expected msgi ← |neighbors i|;
for each j ∈ neighborsi do send go(data) to pj end for.

when go(data) is received from pj do

if (parenti = ⊥)
then parenti ← j; childreni ← ∅;
expected msgi ← |neighbors i| − 1;
if (expected msgi = 0)
then send back({(i, vi)}) to pj
else for each k ∈ neighborsi \ {j}
do send go(data) to pk end for
end if
else send back(∅) to pj
end if.

c M. Raynal, Distributed Graph Algorithms 35

 Algorithm: processing messages back()

when back(val set) is received from pj do

expected msgi ← expected msgi − 1;
if (val set 6= ∅) then childreni ← childreni ∪ {j} end if;
if(expected msgi = 0) then
% a set val setx has been receivedfrom each child px%
let val set = ∪x∈childreni val setx ∪ {(i, vi)};
if (parenti 6= i)
then send back(val set) to pparenti % local term.
else pi (the root) can compute f (val set)% global term.
end if
end if.

c M. Raynal, Distributed Graph Algorithms 36

 Message cost

• #msgs back() = #msgs go()

• On each channels ∈
/ tree: two messages go()
• let e = # channels (edges of the graph)
• We have a total of 2(2e − (n − 1)) messages, namely

⋆ 2(n − 1) messages on the channels of tree and

⋆ 4(e − (n − 1)) messages on the other channels,

• Once the tree is built:

Broadcast/convergecast costs 2(n − 1) messages

c M. Raynal, Distributed Graph Algorithms 37

 Time cost

• Let D be the graph diameter

• Let each message transfer delay = one time unit
• Worst time complexity: 2D

c M. Raynal, Distributed Graph Algorithms 38

 Example

expected msg1 = 2 expected msg1 = 1 expected msg1 = 0

p1 back1,2()
go1,2() go2,1() back2,1()
p2
back2,3() back3,1()
go1,3() go3,2() expected msg3 = 1
p3
go3,4()
expected msg3 = 2 expected msg3 = 0
back3,4()
p4

c M. Raynal, Distributed Graph Algorithms 39

 Remarks

• On the parenthesized structure of the execution

• The case of non-FIFO channels
• A spanning tree per process
• Concurrent initiators for a single spanning tree

c M. Raynal, Distributed Graph Algorithms 40

Breadth-First Spanning Tree

c M. Raynal, Distributed Graph Algorithms 41

 Example

p1 p1 p1

p2 p2 p2
p3 p3 p3

p5 p5 p5
p4 p4 p4

Two different breadth-first spanning trees

built from the same communication graph

c M. Raynal, Distributed Graph Algorithms 42

 BF spanning tree with centralized control

• Distributed iteration controlled by the designated root

process pa
• Each iteration (wave)
• The iteration (wave) number d adds to the tree the
processes at distance d from the root
• The wave number d

⋆ Progresses from the root to processes at distance d

with msgs go(d)
⋆ returns from the processes at distance d to the root
with msgs back(d)

c M. Raynal, Distributed Graph Algorithms 43

 Successive waves launched by the root process pa

Distance d from the root pa

d=1 d=2 d
Wave number d

d=1

d=2

Direction of messages go(): →

Direction of messages back(): ←

c M. Raynal, Distributed Graph Algorithms 44

 Example: a communication graph

3 7
11

9
10
2

5 1 4

13 14
8
12

c M. Raynal, Distributed Graph Algorithms 45

 Example: p2 is the root: first wave

3 7
11

9
10
2

5 1 4

13 14
8
12

c M. Raynal, Distributed Graph Algorithms 46

 Example: seconf wave

3 7
11

9
10
2

5 1 4

13 14
8
12

c M. Raynal, Distributed Graph Algorithms 47

 Example: a communication graph

3 7
11

9
10
2

5 1 4

13 14
8
12

c M. Raynal, Distributed Graph Algorithms 48

 Local variables

• distancei:
write-once variable, will save the distance of pi to the
root
• to sendi:
set that once pi has been inserted in the spanning tree,
contains its neighbors to which it has to propagate the
next waves it will receives from the root
If pi is at distance d, these wave propagations will con-
cern waves whose number is greater than d
• waiting f romi:
set used by pi to manage the return of the current wave
to its parent in the tree

c M. Raynal, Distributed Graph Algorithms 49

 Launching by pa

when start() is received do

% the receiver becomes the root %
parenti ← i; childreni ← ∅;
distancei ← 0; to sendi ← neighborsi ;
for each k ∈ to sendi do send go(0) to pk end for;
waiting f romi ← neighborsi .

c M. Raynal, Distributed Graph Algorithms 50

 Processing of a message go(d)

when go(d) is received from pj do

if (parenti = ⊥)
then parenti ← j; childreni ← ∅;
distancei ← d + 1; to sendi ← neighborsi \ {j};
if (to sendi = ∅) then send back(stop) to pj
else send back(continue) to pj
end if
else if (parenti = j)
then for each k ∈ to sendi do
send go(distancei) to pk end for;
waiting f romi ← to sendi
else send back(no) to pj
end if
end if.

c M. Raynal, Distributed Graph Algorithms 51

 Processing of a message back(resp)

when back(resp) is received from pj do

waiting f romi ← waiting f romi \ {j};
if resp ∈ {continue, stop} then childreni ← childreni ∪ {j} end
if resp ∈ {stop, no} then to sendi ← to sendi \ {j} end if;
if (to sendi = ∅) % we have then waiting f romi = ∅ %
then if (parenti = i) then the root learns the tree is built
else send back(stop) to pparenti
end if
else if (waiting f romi = ∅)
then if (parenti = i)
then for each k ∈ to sendi do
send go(distancei) to pk end for;
waiting f romi ← to sendi
else send back(continue) to pparenti
end if end if end if.

c M. Raynal, Distributed Graph Algorithms 52

 Remarks

• On distributed synchronization
• Local versus global termination

c M. Raynal, Distributed Graph Algorithms 53

 Costs

• Messages:

⋆ e = number of channels
⋆ At most 2 messages go() travel each channel ∈ / tree
⇒ at most 2(e − (n − 1)) messages go() travel these
channels
⋆ The tree has (n − 1) channels, in the worst case there
are n waves
⇒ at most O(n2) messages go() travel the channels
of the tree
⋆ As e ≤ n2, the total nb of messages is O(n2)

• Time:
at most D waves ⇒ 2(1 + 2 + · · · + D), i.e., O(D 2)

c M. Raynal, Distributed Graph Algorithms 54

Distributed Shortest Paths

c M. Raynal, Distributed Graph Algorithms 55

 Ford-Bellman’s seq. algorithm: notation

• ℓgi[j], for j ∈ neighborsi : length associated with the chan-

nel hi, ji
• lengthi[1..n]: array such that lengthi[k] will contain the
length of the shortest path from pi to pk
Initially, lengthi[i] = 0 (and keeps that value forever)
while lengthi[j] = +∞ for j 6= i
routing toi[1..n]: when the algorithm terminates, for any
k ∈ [1..n], routing toi[k] = j means that pj is an optimal
neighbor when pi has to send information to pk

c M. Raynal, Distributed Graph Algorithms 56

 Ford-Bellman’s Dynamic Programming Principle

j1
ℓgi[j1] lengthj1 [k]

ℓgi[j2]
i j2 k
lengthj2 [k]
ℓgi[j3] lengthj3 [k]
j3

 
∀ i, k ∈ {1, ..., n} : lengthi[k] = min ℓgi[j]+lengthj [k] .
j∈neighborsi

c M. Raynal, Distributed Graph Algorithms 57

Adapting Ford-Bellman’s algorithm to distributed system

when start() is received do

for each j ∈ neighborsi do send update(lengthi) to pj end for.

when update(length) is received from pj do

updatedi ← false ;
for each k ∈ {1, ..., n} \ {i} do
if (lengthi[k] > ℓgi[j] + length[k])
then lengthi[k] ← ℓgi[j] + length[k];
routing toi[k] ← j;
updatedi ← true
end if
end for;
if (updatedi) then
for each j ∈ neighborsi do send update(lentoi) to pj end for
end if.

c M. Raynal, Distributed Graph Algorithms 58

 Remarks

• Asynchronous system
• Channels: not required to be FIFO
• Chaotic iterations (as in some parallel algorithms)
• The algorithm terminates (fixed point computation)
• But ...
no process knows when the algorithm has terminated!

c M. Raynal, Distributed Graph Algorithms 59

 Adding synchronization to learn termination

• Consider a synchronous system (round-based system)

• Assume the diameter D is known
• Execute a number of rounds equal to the diameter
• At round d ∈ [1..D], each process knows its d-neighborhood

c M. Raynal, Distributed Graph Algorithms 60

 Resulting algorithm

when r = 1, 2, ..., D do
begin synchronous round
for each j ∈ neighborsi do send update(lengthi) to pj end for;
for each j ∈ neighborsi do
receive update(lengthj ) from pj end for;
for each k ∈ {1, ..., n} \ {i} do  
let length ik = minj∈neighborsi ℓgi[j] + lengthj [k] ;
if (length ik < lengthi[k]) then
lengthi[k] ← length ik;
routing toi[k] ← a neighbor j realizing the previous min.
end if
end for
end synchronous round.

c M. Raynal, Distributed Graph Algorithms 61

 Invariant at the end of round r

• Invariant: (r ≤ D) ⇒
pi knows the shortest path from itself to any other
process pk , which is composed of at most r channels
(Hence, this length to pk is not necessarily the shortest
one)
• Termination at r = D, pi has computed
⋆ the shortest lengths from it to all the other processes
⋆ the corresponding appropriate routing neighbors

c M. Raynal, Distributed Graph Algorithms 62

 Main Question

• How to obtain an asynchronous algorithm in which each

process learns it has terminated?
• We will see later!

c M. Raynal, Distributed Graph Algorithms 63

 Vertex coloring and
Maximal independent set

c M. Raynal, Distributed Graph Algorithms 64

 Vertex coloring

• Problem: color the vertices (processes) of a graph (net-

work) such that

⋆ No two neighbors have the same color

⋆ The number of color is “as small as possible”

• Applications: resource allocation (e.g., sensors networks)

• In sequential computing: vertex coloring is NP-complete
• Hence, we are interested in (∆ + 1)-coloring (where ∆
is the maximal degree of the graph) which is not always
optimal

c M. Raynal, Distributed Graph Algorithms 65

 A simple sequential greedy algorithm

• n vertices, set of possible colors is {1, ..., ∆ + 1}

• COLOR [1..n] colors of the vertices, initialized to [⊥, ..., ⊥]

for i from 1 to n do
c ← 1;
while (COLOR [i] = ⊥) do
if ( j∈neighborsi COLOR [j] 6= c)
V

then COLOR [i] ← c

else c ← c + 1
end if
end while
end for.

∆ + 1 assumption ⇒ there are enough colors, not optimal

c M. Raynal, Distributed Graph Algorithms 66

 A “corresponding” distributed algorithm: basics

• Assume processes are initially colored with m > ∆ + 1

colors, with no conflicting color between neighbors
• This is always possible, e.g., taking m = n, the initial
color of pi being its identity/index i
• Local variable at each pi: array colori[neighborsi ∪ {i}],
with colori[i] = init color of pi
• Principle:
⋆ execute rounds from r = ∆ + 2 until r = m
⋆ the rounds are asynchronous
⋆ each message carries its round number
⋆ at round r, for any pj :
if colorj [j] = r, pj takes a free color in [1..∆ + 1]

c M. Raynal, Distributed Graph Algorithms 67

 Distributed (∆ + 1)-coloring: initial round

for each j ∈ neighborsi do send init(colori[i]) to pj end for;

for each j ∈ neighborsi do 
wait init(col j) received from pj ;
colori[j] ← col j
end for.

At the end of this round we have:

∀i : ∀j ∈ neighborsi : colori[j] = init color of pj

c M. Raynal, Distributed Graph Algorithms 68

 Distributed (∆ + 1)-coloring: algorithm

for ri from (∆ + 2) to m do
begin asynchronous round
if (colori[i] = ri)
then c ← smallest color in {1, ..., ∆ + 1}
such that ∀ j ∈ neighborsi : colori[j] 6= c;
colori[i] ← c
end if;
for each j ∈ neighborsi do send color(ri, colori[i]) to pj end for;
for each
j ∈ neighborsi do 
wait color(r, col j) with r = ri received from pj ;
colori[j] ← col j
end for
end asynchronous round
end for.

c M. Raynal, Distributed Graph Algorithms 69

 Distributed (∆ + 1)-coloring: remarks

• The round numbers (carried by messages) are use to

synchronize the whole progress
• Invariant: when round r terminates, the processes whose
initial colors were in {1, ...r}
⋆ have a color in the set {1, ..., ∆ + 1}, and
⋆ have a color different from their neighbors

• Cost:
⋆ time: m − (∆) rounds (with initial round)
⋆ message bit complexity: O(log2 m)
⋆ number of messages: 2e(m−∆) (2 msgs/channel/round)

c M. Raynal, Distributed Graph Algorithms 70

 On the behavior of the communication channels (1)

No assumption (except reliability) was done on the channels

pj starts round r + 1
rj = r rj = r + 1
pj

pi
ri = r
pi starts waiting for a round r message from its neighbor pj

c M. Raynal, Distributed Graph Algorithms 71

 On the behavior of the communication channels (2)

As a process is allowed to progress from round r to round

(r + 1) only after it has received a round r message from
ALL its neighbors, we have the following round invariant:

∀(i, j) : (pi and pj are neighbors ) ⇒ (0 ≤ |ri − rj | ≤ 1)

c M. Raynal, Distributed Graph Algorithms 72

 Consequence of the previous observation

• A message color() does not need to carry the value of

r but only a bit, namely the parity of r
• A process pi sends now: color(ri mod 2, colori[i]) to
each of its neighbors
• And on the reception side we have:
a process pi waits for a message color(b, colori[i]) from
each of its neighbors where b = (ri mod 2)
• Consequence: when the channels are FIFO:
neither round numbers, nor parity bits have to be carried
by messages

c M. Raynal, Distributed Graph Algorithms 73

Maximal independent set

c M. Raynal, Distributed Graph Algorithms 74

 Definitions

• Independent set:
a set of vertices (processes/nodes) such that no two
of them are neighbors
• Maximal independent set M :
No of its strict superset M ′ (i.e., M ⊂ M ′ and M 6= M ′)
is an independent set

4 7 3
3

1 8 2 1 4

2 5 6 5

c M. Raynal, Distributed Graph Algorithms 75

 M aximum versus maximal independent set

• A maximum independent set is an independent set with

maximal cardinality
• Previous examples
⋆ Left side: both {1, 4, 5, 8} and {2, 3, 6, 7} are maxi-
mum independent sets
⋆ Right side: only the set {2, 3, 4, 5} is maximum

• In sequential computing computing a

⋆ maximal independent set is an easy pb (greedy alg.)
⋆ maximum independent set is an hard pb NP-complete)

c M. Raynal, Distributed Graph Algorithms 76

 From m-coloring to a maximal independent set

• Classical reduction technique:

⋆ Assuming a solution to m-coloring (color with at most
m colors)
⋆ Design (on top of it) an algorithm that builds a max-
imal independent set

• How: we adopt an elimination-based greedy strategy

• Local variables at each pi:
an array selectedi[neighborsi ∪ {i}], initialized to [false , ..., false ]
• At the end of the algorithm:
selectedi[i] ⇔ pi belongs to the maximal ind. set

c M. Raynal, Distributed Graph Algorithms 77

 An m coloring-based algorithm for maximal ind. set

for ri from 1 to m do
begin asynchronous round
if (color
V i
= ri) then 
if j∈neighborsi (¬selectedi [j]) then selectedi[i] ← true end if;
end if;
for each j ∈ neighborsi do
send selected(ri, selectedi[i]) to pj end for
for each 
j ∈ neighborsi do 
wait selected(r, selected j) with r = ri received from pj ;
selectedi[j] ← selected j
end for
end asynchronous round
end for.
As before: the round numbers in messages can be elimi-
nated (use modulo 2)

c M. Raynal, Distributed Graph Algorithms 78

 Optimal coloring of a ring
Cole & Vishkin’s synchronous algorithm

c M. Raynal, Distributed Graph Algorithms 79

 Cole-Vishkin’s algorithm adapted to a ring

• Each process pi has a distinct identity idi, O(log n) bits

• Links are bi-directional (messages)
• Logical orientation: each process pi as a predecessor
predi and a successor nexti
• Properties:
⋆ Locality
⋆ Optimality wrt time complexity O(log∗ n + 3)
⋆ Determinism (the final color of a node depends only
of the ids of its log∗ n + 3 predecessors)

c M. Raynal, Distributed Graph Algorithms 80

 Meaning of the LOCALITY property

• An algorithm is local if, whatever its input, the number

of rounds is smaller than the diameter (or even is a
constant)
• CV86 requires each process to execute O(log∗ n) rounds
• What is log∗ n? (iterated logarithm)

⋆ Number of times you need to apply log2 to obtain a

value ≤ 1:

log2(log2(log2 ...(log2 n)....)) to obtain a value ≤ 1

⋆ Example log2(nb of atoms in the universe)= ?
⋆ This motivated the research ∗
to know which class of
pbs can be solved in O(log n) rounds!

c M. Raynal, Distributed Graph Algorithms 81

 Structure od CV86

• Phase 1: From n colors to six colors.

A clever bit-level technique is first used which allows the

processes to be properly colored with six colors. Start-
ing with colors encoded with log n bits (node identities),
a sequence of synchronous communication steps is exe-
cuted, such that in each step a process computes a new
proper color whose size in bits is exponentially smaller
than the previous one. This is repeated until attaining
at most six colors, which requires log∗ n communication
rounds
• Phase 2: From six colors to three colors.

The algorithm uses then a simple reduction technique

to reduce the number of colors from six to three. This
requires three additional rounds (each one eliminating a
color)

c M. Raynal, Distributed Graph Algorithms 82

Computation of a new color: from m bits to log m bits

• Initial color: identity of pi encoded on m bits

• let colori = bm, bm−1, ..., b1, b0
bit representation of the current color of pi
• let color p = cm, cm−1, ..., c1, c0
bit representation of the current color of predi
• Let x = first index where bx and cx differ
(starting from 0 at the right)
• New color of pi: bit string encoding

⋆ the value of x on log m bits

⋆ followed by the bit bx

• The new color uses log m +1 bits

c M. Raynal, Distributed Graph Algorithms 83

 Example

• m = 8 (log 8 = 3)
• colori = 1 0 0 1 1 0 0 1
• color p = 1 1 0 1 1 1 0 1
• x = 2, first index such that bx 6= cx
• new color of x = 0 1 0 bx = 0 1 0 0

Why pi and its predecessor cannot have the same new color?

c M. Raynal, Distributed Graph Algorithms 84

 Cole and Vishkin’s algorithm: Phase 1

Phase 1: reduction from n colors to 6 colors

colori ← bit string representing pi’s identity;

when r = 1, 2, ..., log∗ n do %
begin synchronous round
send color(colori) to nexti;
receive color(color p) from predi;
x = position (starting at 0 from the right)
where colori and color p differ;
colori ← bit string encoding the binary value of x
followed at its right by the bit bx
end synchronous round;
% Here colori ∈ {0, 1, · · · , 5}.

c M. Raynal, Distributed Graph Algorithms 85

 Cole and Vishkin’s algorithm: Phase 2

Phase 2: reduction from 6 colors to 3 colors

when r = log∗ n + 1, log∗ n + 2, log∗ n + 3 do

begin synchronous round
send color(colori) to predi and nexti;
receive color(color p) from predi
and color(color n) from nexti;
let k be r − log∗ n + 2; % k ∈ {3, 4, 5} %
if (colori = k) then
colori ← min({0, 1, 2} \ {color p, color n})
end if
end synchronous round; Here colori ∈ {0, 1, 2} %
return(colori).

c M. Raynal, Distributed Graph Algorithms 86

 Generalized coloring: distance-2 coloring

Investigate distance-2 coloring in networks such that

• No two processes at distance ≤ 2 have the same color

• synchronous: each message is received in the round in
which it was sent
• Arbitrary connected communication graph
• processes may communicate by broadcasting a message
to neighbors and receiving messages from neighbors
• But collisions and conflicts may occur
⋆ a collision occurs when a process receives messages
from two or more neighbors in the same round
⋆ a conflict occurs when, during the same round, two
neighbors send a message to each other

c M. Raynal, Distributed Graph Algorithms 87

 Tree network Structure and behavior

p1
p1
p2
p3
p2 p3 p4
p4
p5
p5 p6
p6
p7
p7

collision conflict

c M. Raynal, Distributed Graph Algorithms 88

 Results for TREE networks

∆ = maximal degree of the tree, d = depth of the tree

color-optimal: ∆ + 1 colors (distance-2 coloring)

• A color-optimal distributed algorithm (based on a depth-

first tree traversal) which uses 2(n − 1) broadcasts, and
has 2(n − 1) time complexity
• A color-optimal distributed algorithm (based on a par-
allel tree traversal) which uses O(2n − ∆) broadcasts,
and has O(d∆) time complexity

c M. Raynal, Distributed Graph Algorithms 89

 Examples of other important graph problems

• Compute the diameter (or the radius) of the graph

• Determine the process(es) center of the graph
• Detect cycles and knots (dead ends)
• Detect peripheral processes (nodes)
• Detect cut processes (vertices)

c M. Raynal, Distributed Graph Algorithms 90

CONCLUSION

c M. Raynal, Distributed Graph Algorithms 91

• A visit to network traversal algorithms
• A visit to a few distributed graph algorithms
• Presentation of algorithms based on various assump-
tions
• Notion of synchronous/asynchronous systems
• Distributed computing 6= sequential/parallel computing

c M. Raynal, Distributed Graph Algorithms 92

 Keywords associated with what has been learnt

• Asynchronous/synchronous system, Breadth-first traver-

sal, Broadcast, Convergecast, Depth-first traversal, Dis-
tributed algorithm, Forward/discard principle, Initial knowl-
edge, Local algorithm, Parallel traversal, Spanning tree,
Unidirectional logical ring
• Distributed graph algorithm, Graph coloring, Knot de-
tection, Maximal independent set, Problem reduction,
Shortest path computation

c M. Raynal, Distributed Graph Algorithms 93