Distributed Computing, COMP 4001 1
Mobile Agent Rendezvous
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Mobile Robots
Drones Vehicles
Agent
Distributed Computing, COMP 4001 2
• MA Model
• Tokens
• RV Algorithms
– Two MAs
– Time/Memory Tradeo↵s
– Rendezvous with Ddetection
Outline
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 3
MA Model
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001
4
Rendezvous
Leader
Election
D=
• RV (Rendezvous) means the MAs meet. It is a form of gathering and a very basic form of information exchange.
(• RVP (Rendezvous) Problem.
– Give an algorithm that enables the MAs to rendezvous
mte%mYYk
– The requirement is to cause rendezvous, if rendezvous is not possible rendezvous will never happen, and the algorithm will be running for ever!
I• RVD: Rendezvous Problem with Detection
– A rendezvous algorithm is required to detect whether or not
rendezvous is possible and if it is to cause rendezvous.
• Two Mobile Agents (MAs) initially located at arbitrary nodes
of a graph. MAs can move along edges.
.
regardless of their starting positions.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
–
same
speed
#*#
heeling Point
Graph
Mode
QD
Geometric O
Model
3D
Geometric
a
O b
Model
Distributed Computing, COMP 4001 5
Gathering
• For more than two agents in a graph the problem is also known (referred to) as Gathering.
• Gather(k) means that k MAs meet. • Gather(2) is the same as RV.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 6
MAs vs Message Passing
• So far, in distributed computations, we had messages that were being sent along vertices of a network.
– The nodes were the processors that enabled the distributed computation.
• This distributed setting remains, but now also
– we have autonomous, agents (or mobile code) moving on
vertices of a distributed network
– the agents are mobile; not only they can compute but also they can participate in distributed computations.
• The rendezvous problem can be stated for any topology.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 7
Where/How can you rendezvous?
• Exploit network assymetries
• Exploit topological (geometric) assymm:etries
• In a general graph the problem is quite complex!
FI
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 8
Special Topology: Ring
• We look only at ring topologies.
• Even in a ring the problem is quite complex!
• k MAs are initially located on k nodes of an n node ring.
• Assume a synchronous system with common sense of direction. • Will be restricted to the case of k = 2 MAs.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 9 Ring, Mob°ile Agents, and Tokens
• Each of the MAs has a token which it chooses to leave (or not to leave) at its starting position or elsewhere.
Every agent owns
itsown
tokenandcan releaseitat
any node;thetokensare endedgeishable
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
÷o÷÷
I 20-5–115
→
.
Distributed Computing, COMP 4001 10 Approaches to Rendezvous (1/2)
0=0
• In general, to solve the rendezvous problem, one must try to break the inherent symmetry of the problem.
1. If the MAs have unique IDs you can break symmetry and the problem becomes, sometimes, easier to solve!
2. If the MAs do not have unique IDs and the network nodes
are anonymous the resulting symmetry makes the problem
di cult and sometimes even impossible to solve!
:
÷.
• In principle, we have to break symmetry: – either deterministically, or
– using randomization.
• Sometimes we can use the underlying topology to break
symmetry.
⇐
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
.÷
Distributed Computing, COMP 4001 11
Approaches to Rendezvous (2/2)
• Mobile agents have identical (i.e., indistinguishable) tokens, one token per MA, that they can release at their starting position.
• We are interested in tradeo↵s among 1. number of tokens
2. knowledge
3. time
4. memory.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 12
The Model: Topology and the Nodes
• There are n identical nodes on which MAs may reside. T
• The topology is a ring.
• For example, in the ring above there are n = 8 nodes and the MAs can traverse its vertices and edges.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 13
The Model: Synchronicity/Orientation
• The characteristics of the topology will be used in the algorithms.
• Oriented means that there is a consistent sense of direction: either CW or CCW.
– As usual this is specified with ports.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 14
Where Can Rendezvous Occur?
• Can rendezvous for two agents occur at a node of the ring?
•I
t
• Can rendezvous for two agents occur at an edge of the ring? • Yes, to both questions!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
• ÷i÷.
Distributed Computing, COMP 4001 15
Model
• Anonymous, synchrono8us, and possibly oriented n node ring.
• A given node requires only enough memory to host a token.
• Each MA, owns a single identical stationary token,
– the tokens are indistinguishable and once they are
positioned in the ring, they cannot be moved.
• AtokenorMAatagivennodeisvisiblebyallMAsonthe same node
– The MAs follow the same deterministic algorithm and begin execution at the same time.
• Memory permitting, a MA can count the number of nodes visited, the number of nodes between tokens, or the total number of nodes in the network.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 16
Impossibility of RV
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 17 Impossibility of RVD
• Consider two identical, anonymous Mobile Agents in a ring of size n.
• The agents have constant memory and can leave a token at their starting position.
I
• Theorem 1 No deterministic algorithm exists such that the MAs always correctly detect if d = n and act appropriately,
–
–
animism and the other
.
.
If
2
robot
– .
I÷ ‘
i.e., stop if d = n and rendezvous otherwise.
one
. .
with speed 2!
,
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
2
Distributed Computing, COMP 4001 18
RV Algorithms (Two Agents)
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 19
Rendezvous for two MAs
• RVinaring
1. There are two identical MAs at distance d from each other. 2. The ring may or may not be oriented.
3. The ring has size n.
d
• There are a lot of (simple) subtleties!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
1. 2. 3. 4.
Distributed Computing, COMPQ4001 20 i1. Orientation Known, d Known
dEa?I +das
Release the token at starting position.
Walk around ring in a counterclockwise direction.
If a token found within d steps, continue in same direction. If no token found by d steps, reverse direction and continue.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 21
Correctness
• There are two “competing distances” measured by the MAs: – d and n d.
• Rendezvous is achieved if d < n/2. – Whatifd=n/2?
• How many steps does it take to rendezvous?
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 22 2. Orientation not Known, d Known
T
t I 13¥
s.d←
m a x FE, ¥1 2. Choose a direction and begin walking around the ring.
1. Release the token.
3. If a token is found within d steps, walk in the same direction.
4. If no token is found by d steps, reverse direction and continue. max {Metz, 3421, dz, 3¥}
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 23
Correctness
• Similar to previous algorithm except MAs may select either direction.
• There are two “competing distances” measured by the MAs: – d and n d.
• Rendezvous is achieved if d < n/2. – Whatifd=n/2?
• How many steps does it take to rendezvous?
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 24 3. Orientation not Known, n Known
⇐
1. Release the token. O
2. Choose a direction and begin walking around the ring.
3. If a token is found within n steps, continue in same direction. 2
4. Otherwise, reverse direction at n steps and continue. 2
d
d
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
+
II
Distributed Computing, COMP 4001 25
Correctness
• Here algorithm does not need to know the distance. – n/2 is being used as a threshold for rendezvous.
• How many steps does it take to rendezvous?
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 26
4. Orientation, d and n Are not Known. δ2
Oδ 1
Here the MAs must discover what is their distance!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 27
Time/Memory Tradeo↵s
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001
28
Assume O(log n) memory • Algprithm:
1. Release the token.
2. Choose a direction and begin walking around the ring.
3. Count # of steps to 1st token, 1, and continue. a 4. Count # of steps to 2nd token, 2.
/* The MA is back at its starting node.*/
5. If 1 < 2, continue walking in the same direction.
6. Otherwise, reverse direction and continue walking.
• MAs need memory O(log n).
• Under what conditions on 1, 2 does the algorithm work?
the sees Reisz) sissies fs@p
Azn Cri,⇐ . Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
82
€•÷ia.
Distributed Computing, COMP 4001 29 Improving on the Memory
• A question remains:
– can we improve on the memory O(log n)?
• Knowledge of n requires log n bits.
– Answer: Use modular arithmetic! cnn.at#mdic
• Previous algorithms were breaking symmetry by testing whether or not d < n d.
– We will find a way to carry out the same test, but we will generate prime numbers to do so!
– How can we test using less than log n bits.
– In fact, it will be a sequence of tests: in the end it will be confirmed which of d < n d or n d < d is valid.
:÷÷÷
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 30
Algorithm id
1. Release the token.
2. Set m = p1.
3. Choose a direction and begin travelling around the ring.
4. Count # of steps, modm, to the first token, 1, and continue
walking.
5. Count the number of steps, modm, to the second token, 2. /*
The MA is back at its starting node. */
6. If 1 modm= 2 modm,setm=pi+1 andrepeatfromstep4.
7. If 1 mod m < 2 mod m, continue travelling in same direction.
8. Else, reverse direction and continue travelling.
• All we are doing is trying to test whether or not d0< n d, but modulo consecutive primes!
• MAs need to generate: p1,...,pk first k primes s.t. Qki=1 pi > n
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
n-
d
@
°:
‘
° cites
I
° a, 80
dz (0,0) Cine )
) ”
O
Cop
@2 O p,
=
)
Cop 0000
(op
00. Y IM
(2,1
( 1,27
8 00%
O
•
”
)
( 1,11 can
)
.
÷.
,
1
”
‘
”
”
Prime building
numbers
the numbers
11,13 , Alexandria
atoms X,2,3, 5,7,
are of
Euclid There a re
ago )
-1-7,19 ( 2,000
infinitely
yrs many
!
primes.
Distributed Computing, COMP 4001 31
Memory O(log log n):
• Theorem 2 The previousOalgorithm requires Memory
) and accomplishes rende1
O(log log n) Clogn
zvous in time
OÅ ã
Ok
)
O
nlogn log log n
• Algorithm terminates after first k primes p1 , . . . , pk s.t.
Yk
pi > n
i=1
• To prove termination use the Chinese Remainder Theorem. • To prove time complexity use the Prime Number Theorem.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distribute:d Computing, COMP 4001 32 Using the Chinese Remainder Theorema
• If the ni are pairwise co-prime, and if a1,…,ak are any integers, then there exists an integer x such that
x⌘a1 modn1 x⌘a2 modn2
Ein
PgPs— Ph>n
and x is unique mod(n1n2 · · · nk).
• Inourcasen :=p,fori=1,2,…,k,andtherearethetwo
. .
x⌘ak modnk
I
solutions 1, 2. details ofthi. s
i i
aProblem with specific numbers, appears in the 3rd-century book Sunzi Suan-
.
jing by the Chinese mathematician Sunzi
mthiscl1
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
cannot do the 1
Distributed Computing, COMP 4001 33 Using the Prime Number Theorem
K• The worst case oiccurspwhen d = n/2 asince the max number k of prime numbers have to be checked.
• Resulting running time is O(kn), but we need to determine the value of k. Consider smallest k such that Qki=1 pi > n.
• This implies that Qk 1 pi n. Hence 2k(k 1)/2 n. Thus i=1
pk ⇡klnkQk2n.a
• Therefore ki=1 pi npk n2.
• By the prime number theorem we have that
n
k!8
2
2 Yk Yk i log pi k ⌦(k log k)
p
i=1 i=1
i8
aKnowledge of number theory is needed here!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
lu
Distributed Computing, COMP 4001 34
RV with Detection
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 35
Rendezvous with O(1) memory • The main question:
Can you solve the rendezvous problem if the MAs have constant memory?
• One way or the other you must change the rules of the game! – How about if you a¥re allowed to change the position of your
token?
.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 36
Movable Tokens and O(1) memory n, d, orientation unknown.
d
1. Release the token
2. Choose a direction and begin walking
3. Upon finding a token, reverse direction.
4. Move the token one node in the new direction 5. Continue walking in the new direction
6. Repeat from step 3 until rendezvous occurs
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 37
RVP vs RVD
• RVP: denotes the Rendezvous Problem
– The requirement is to cause rendezvous: if rendezvous is not possible then an algorithm may be running forever without termination, e.g., when the agents are initially placed at distance n/2.
• RVD: denotes the Rendezvous Problem with detection
– A rendezvous algorithm is required to detect whether or not rendezvous is possible and if it is to cause rendezvous, otherwise terminate the algorithm.
• NB. Previous algorithm solves RVP but not RVD.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 38
RVD with Two Movable Tokens
• Theorem 3 Rendezvous with detection (RVD) is solvable in a unidirectional ring for two mobile agents with constant memory and two indistinguishable movable tokens each, in time O(n2).
• This is based on an algorithm which at the cost of using two tokens per mobile agent detects the possibility of rendezvous and can eventually rendezvous when possible.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 39
1.
2. 3.
4. 5.
6.
7. 8.
RVD with Two Movable Tokens
Drop first token at your home base and second token to node located to the right.
repeat
Travel right and move every second token you meet one position to the right.
until agent detects two tokens on top of each other.
if two tokens are found on top of each other go around and check if other two tokens are also on top of each other.
if yes then rendezvous is not possible else agent waits at last position.
endif endif
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 40
RVD with Two Movable Tokens
• Each mobile agent drops one token to its home node and the other token to the node located to its right.
• Then it travels right and moves every second token one position to the right (note that this will keep the home node tokens at their original locations).
• The process is repeated until the agent detects two tokens on top of each other.
• When this happens, it goes around and checks to see if the other two tokens are also on top of each other.
• If they are, then the home nodes were n/2 away, the whole computation was symmetric and the agents can never rendezvous.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 41
RVD with Two Movable Tokens
• If the other tokens are not on top of each other, then the agent waits as the other agent will eventually come to meet it.
• Let us divide the whole computation into rounds of n time steps each – during one round each agent completes a cycle around the ring and both second tokens are moved two steps.
• As the initial distance of the second token from the first token of the next agent is at most d 1 n/2 1, the worst case running time of this algorithm is bound by n times the number of rounds plus n/2 for the final check, resulting in
n((n/2 1)/2) + n/2, which is in O(n2). • This completes the proof of Theorem 3.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 42
Detecting Rendezvous
Table 1: Time bounds for two mobile agents with constant memory to detect if rendezvous with detection is possible (RV D) and to ren- dezvous when input is asymmetric (RV P ) on an n node synchronous uni-, bi-directional ring with one or two tokens.
Conditions
Time Required for Rendezvous
# of Tokens
# of Directions
RVD
RVP
1
1
1
1
1
2
1
⇥(n2 )
2
1
⇥(n2 )
⇥(n2 )
2
2
⇥(n2 )
⇥(n2 )
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 43
Exercisesa
1. Give a rendezvous algorithm for two robots at a distinguished
node of the graph. What vertex would you choose?
2. Consider a geometric graph (nodes have coordinates). Can you show how to solve the rendezvous problem in a planar geometric graph (geometric means the nodes know their (x, y) coordinates)?
3. Consider a planar graph. Can you show how to solve the rendezvous problem in a planar graph if nodes have no
aDo not submit.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 44
knowledge of their (x, y) coordinates?
4. Prove Theorem 1 by showing that no algorithm exists such
that the MAs always correctly detect if d = n and act 2
appropriately, i.e., stop if d = n and rendezvous otherwise 2
5. Prove the following for two agents with tokens
Knowledge
n d orientation
Lower Bound
Upper Bound
Memory Requirement
YES
YES
YES
3d/4
3d/4
O(log d)
YES
YES
NO
3n/4
5n/6
O(log d)
YES
NO
YES
3n/4
3n/4
O(log n)
YES
NO
NO
3n/4
3n/4
O(log n)
NO
YES
YES
3n/4
3n/4
O(log d)
NO
YES
NO
3n/4
5n/6
O(log d)
NO
NO
YES
5n/4
5n/4
O(log n)
NO
NO
NO
5n/4
5n/4
O(log n)
6. Consider 4 Mobile Agents (MAs) located on 4 di↵erent nodes of an n node ring. They are equipped with indistinguishable tokens which they release at their starting poisions.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 45
its correctness. Let the intertoken distances be d1, d2, d3, d4. Give a rendezvous algorithm and determine conditions on the initial distances which ensure rendezvous.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 46
References
1. S. Alpern and S. Gal, Theory of Search Games and Rendezvous, 2003.
2. E. Kranakis, D. Krizanc, and E. Markou, The Mobile Agent Rendezvous Problem in the Ring, Morgan-Claypool, 2010.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 47
Appendix
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 48
Example: Triangle (3-Ring)
• Can two MAs rendezvous in a 3-Ring?
• In lefthand side rendezvous is possibe, but not in the righthand side!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 49
Example: Square (4-Ring)
• Consider two MAs rendezvous in a 4-ring
• Rendezvous is never possible on a vertex . . .
. . . but is possible on an edge!
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 50
Example: Square (4-Ring)
• Consider two MAs
• Algorithm must work in all situations as specified by the given conditions.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 51
A Solution: Rendezvous in an Edge
• If the system is synchronous and the two MAs start at di↵erent endpoints of the line they may never be able to rendezvous at a node.
• Assumption: rendezvous should be possible to occur either at a node or a link of the network!
– This simplifies algorithms, otherwise we have to mention the parity of n,
• In general, two di↵erent MAs could rendezvous on some node/edge of a network.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 52
The Model: Knowledge
• Knowledge refers to what the agents know about themselves, other agents, and the ring itself.
• Consider k MAs in a ring of n nodes.
– Do MAs know k (the total number of MAs in the network)? – Do MAs know n (the number of nodes in the network)?
– Do MAs know the topology (orientation)?
– Do MAs know their initial (inter)-distances?
– How much memory do the agents need to solve rendezvous? – Do the agents have tokens?
• All these characteristics may a↵ect the rendezvous algorithm.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)
Distributed Computing, COMP 4001 53
Lonely Runner Conjecture: Wills (1967) and Cusick (1973)
Suppose k runners having distinct constant speeds start at a common point and run laps on a unit length circular track. Then for any given runner i, there is a time at which runner i is distance at least 1/k away from every other runner.
This conjecture was verified for k < 6 by Cusick and Pomerance (1974) with the assistance of some electronic case checking.
Goddyn, Gvozdjak, Sebo, and Tarsi (1998) supplied an elementary proof of the case k = 5, and established a connection between this problem and a question concerning flows on graphs.
Recently Bohman, Holzman, and Kleitman (2001) have solved this problem for k = 6 runners.
Evangelos Kranakis, Carleton University, SCS (November 25, 2020)