Asynchronous Network Algorithms

Completely asynchronous distributed computational model

• No assumption for speed of processes.
• No assumption for transmission delay of communication links.
• No assumption for speed of local clocks.

Nondeterministic caused by asynchronous

(1) send m1 A (2) send m2

(3) receive m2
Which one is received B C
first, m1 or m2?
(4) send m2
 Model of Send/Receive System
• Let an n-node directed graph G=(V,E) represents an asynchronous
network, where nodes are processes and directed edges are
communication channels.
communication channel process i
process i process j output : send ( m )i , j

input : receive ( m ) j ,i
process k

communication channel Reliable FIFO channel: any message

received must have been sent at
some earlier time

input : send ( m)i , j output : receive ( m )i , j

 Problems 1 Leader Election in An asynchronous Ring
Assumption of the network
• Network graph G=(V,E) is a ring, where node set V={1,2,…,n} and edge set
E={(i,i+1), where i=1,2,…,n and i is counted mod n}.
• Each process has a unique distinct identifier (UID).
• Each node uses only unidirectional communication and knows only its UID (it
does not know the size of the ring and its neighbors).
• Only the leader performs an output.
AsychLCR algorithm (informal)
At each process there is a FIFO queue of UIDs, initially containing only its own UID.
(1) Each process removes and sends the first element of its FIFO queue.
(2) When a process receives an incoming identifier, it compares that identifier to its
own. If the incoming identifier is greater than its own, it add it into its FIFO queue;
if it is less than its own, it discards the incoming identifier; if it is equal to its own,
the process declares itself the leader.
Theorem AsynchLCR solves the leader-election problem.

Analysis of Complexity of AsychLCR Algorithm

• Communication complexity: O ( n 2 )
• Time complexity:
O(n 2(l  d)), where l is the time upper bound for each task of each process,
and d is the time upper bound to deliver the oldest message in each FIFO queue.
Problem2 Leader Election in a General asynchronous Network
Assumption of the network
• Undirected connected graph G=(V,E) having n node, where there is
bidirectional communication on all the edges.
• Processes do not know their indices, nor those of their neighbors, but
refer to their neighbors by local names.
• If a process i has the same process j for both incoming and outgoing
neighbor, then i knows that the two processes are the same.
AsychFloodMax algorithm (informal)
• Use FIFO queue for communicational channel.
• Simulation the rounds of the following synchronous algorithm:
Send a round r message to tag that message with its round number r.
The recipient waits to receive round r messages from all its neighbors
before performing its round r transition. By simulating diam (diameter
of the network) round, the algorithm can terminate correctly.
FloodMax algorithm (informal)
Suppose that each process has a unique distinct UID and it knows
diam, the diameter of network.
• Each process maintains a record of the maximum UID it has seen so
far (initially its own). At each round, each process propagates it
maximum on all of its outgoing edges.
• After diam rounds, if the maximum value seen is the process’s own
UID, the process elects itself the leader; otherwise, it is a non-leader.
Problem 3 Spanning Tree Construction
Assumption of the network
• Undirected and connected network digraph G=(V,E) having n nodes and a
distinguished source note s.
• Output is the structure of a spanning tree of the network graph with root s in a
distributed fashion: each process other than s should have a parent component
that gets set to indicate the node that is its parent in the tree.
• Processes know its neighbors’ indices. They have no knowledge of the size or
diameter of the network. No UIDs are needed.
AsynchBFS algorithms
Use FIFO queue for communicational channel
• At any point during execution, there is some set of processes that is “marked”,
initially just s.
• Process s sends out a search message, to all of its outgoing neighbors.
• If an unmarked process receives a search message, it marks itself and chooses
one of the processes from which the search has arrived as its parent, then it sends
a search message to all of its outgoing neighbors.
Application to Message Broadcast Problem
AsynchBFS algorithm can be used to Message Broadcast
problem: piggyback the message m on all search messages
during the formation of the spanning tree.
Problem 4: Clock of Asynchronous Distributed Systems and
Snapshot algorithms

Space and Time Diagram

send event time
p1

p2

p3

p4

space receive event

internal event
Causal Relation
e  E f : f is affected by e
 There is a e-f path in space/time diagram

send event time

p1

p2

p3

p4

space receive event

internal event
• Role of Clock
Determining a causal relation for events.
• Local Clock
No use for determining the order of the events of different processes.
• Two type of clocks: logical clock and vector clock.

Condition of Clock
Let C ( e) be the time assigned to event e.
e  E f  C ( e)  C ( f )
Lamport’s Logical Clock
LC p : value of the logical clock of process p.
1. Initial state : LC p 0.
2. State of executing event e :
(a) Internal event e, send event e :
LC p :LC p  1;
LC(e): LC p
( LC ( e) is the value of the logical clock assigned to e.)
(b) Receive event e (receiving message M ) :
LC p :max{LC p , LC ( M )}  1
( LC ( M ) : the value of the logical clock attached to M )
LC ( e) :LC p .
Property of Lamport’s logical clock
• Logical clock satisfies the condition of clock
e  E f  C ( e)  C ( f )
• Clock condition does not satisfy causal relation

C ( e)  C ( f )  e  E f

0 send event time

p1 1 2 3 4

0 1
p2 1 2 3 5

0 1 3 4
p3 1 4

0
p4 2 3 4

space receive event

internal event
Application of Lamport’s Logical Clock: Bank System
P1 $10 P2 $20 P3 $30
CountMoney algorithm
2 P1,2$1
Use a predetermined logical time t, assumed 3 1
to be known to all processes. $2
P3,1
1. For each process, determine the value
of money after all events with logical 4 P2,4
times less than or equal to t and before $3
7 8 5
all events with logical times greater P3,6$5
t=7.5
than t. $4 9 6
P1,10
10 11 P3,8
2. For each channel, determine the
amount of money in all the messages $1
12 8
sent at logical times less than or equal 11 P1,11
$1 9
to t but received at logical times strictly P2,12
greater than t. $2
11

$10-$1+$5=$14 $20+$1-$3+2=$20
$30-$2+$3-$5=$26
Problem 5: Global Configuration of Distribute
Systems and Snapshot Algorithms

Global Configuration of Distributed Systems:

states of processes (local memory), states of communication
links (message), which are used for
• Dead lock detection
• Termination detection
• Backup at some check point (for recovery from failures)

Snapshot Algorithms:
Distributed algorithms for finding global configuration
 Example: Snapshot at time t=7.5
How to take a snapshot
P1 $10 P2 $20 P3 $30
• Freeze all the processes and
collect the state of each process. 2 P1,2$1
3 1
---Inefficient! $2
P3,1
• Using global clock: broadcast the 4 P2,4
global time t and collect the state of $3
each process at time t. 7 8 5
P3,6$5
t=7.5
$4 9 6
--- Global clock may not exist! P1,10
10 11 P3,8
• Using logical clock. 12
$1
8
11 P1,11
$1 9
P2,12
$2
11
 Chandy and Lamport’s Snapshot Algorithm
The algorithm collects the state of each process and the state of each link (the
messages in communication)
1. One process finds its own state, then send message <mark> to each of its
neighbors.
2. For each process p
(a) if p receives <mark> first time, it finds its own state, and then send
<mark> to each of its neighbors.
(b) p continues to receive message <mark> from all its neighbors as follows:
Assuming that t(0) is the time p received the first <mark>, p collect all the
message from any neighbor q until p get message <mark> form q.

mark p p m1 p m1,m2 p m1,m2,m3

m1
Start process m2 m3 mark
mark
q q q q
mark

mark
Exercise
(1) Reconsider the banking system. Now suppose that the underlying banking
system A allows deposits and withdrawals (modeled as input actions at the
user interface of the system ) in addition to transfers. If we apply the same
Count Money transformation as before, what can be claimed about the output
of the resulting systems?