Distributed Computing, COMP 4001 1
Universal Traversals
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 2
Labeling Schemes
• How can we use port labeling schemes to improve communication?
• What role do port labeling schemes play in distributed computing?
• The execution of a distributed algorithm at a node depends on the sequence of port labels that must be followed by the distributed algorithm at that node.
• Can we solve a problem in a way that all nodes follow identical sequences at each node?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 3
• Probabilistic Method • Universal traversals
Outline
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 4
Probabilistic Method
• Using probability to prove the existence of a mathematical object is called the Probabilistic Method.
• It has many applications, especially in graph theory. • It uses the following principle:
If, in a given set of objects, the probability that a randomly chosen object does not have a certain property is less than 1 then then there must exist an object with this property.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 5
Union Form of the Probabilistic Method
• Consider n events A1, A2, . . . , An (not necessarily independent). • The union (or Boole) Inequality states that
nn
Pr Ai ≤Pr[Ai]
i=1 i=1 • Therefore if we want to prove that
n
(¬A)i ̸= ∅
i=1 it is enough to show that
n
Pr[Ai] < 1.
i=1
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 6
Expectation Form of the Probabilistic Method
• Consider an integer valued random variable X which takes only non-negative integer values.
• Observe that
Therefore
Pr[X >0]=Pr[X =k] k>0
≤ Pr k[X = k] k>0
= E[X]
Pr[X > 0] ≤ E[X] (1)
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 7
Expectation Form of the Probabilistic Method
• Equation (1) is a special cas of Markov’s inequality wchich states that
Pr[X > kE[X]] ≤ 1 k
• Therefore using Equation (1) if we want to prove that Pr[X =0]>0
it is enough to prove that
E[X] < 1.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 8
Traversals
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 9
Explorations
• Graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. E.g.,
– BFS – DFS
• Used in Search and Exploration.
• Each starting node is equipped with a program
– typically a sequence of port labels that it must follow from node to node) which is used to traverse the graph.
• However, the program used may depend on the starting node.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 10
Universal Traversals
• A sequence is universal for graphs with n vertices if for every graph and every start vertex, the walk defined by the (same) sequence will visit every vertex in the graph.
• Can you produce a universal traversal program that will work for every graph and every starting node of the graph?
• To produce a walk defined by a sequence, we need some notion of graph labeling.
– For each vertex u, label the edges adjacent to u (ports) from 1 to deg(u) (in fact any numbering will do).
– This is what we defined as port labelings!
• Then a sequence is a string of edge labels which determines some walk through the graph.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 11
Universal Traversals on Labyrinths
• A robot is placed in a labyrinth in a n × n square grid. • It runs a program: a sequence of commands of the form
N(orth), S(outh), E(ast), W(est),
• As an example consider the program NESWEW which is given to every node.
• A robot has the sequence “NESWEW” and starting at a node makes movements following the sequence of labels.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 12
Universal Traversals
• In addition to external walls on the whole perimeter, walls are also placed between cells.
• Executing each command, the robot moves in the prescribed direction if possible (and does nothing when there is a wall in this direction).
E.g., NESWEEEW
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 13
• We can show that
Universal Traversals
Theorem 1 (Universal Traversals) For any n, there exists a program that works correctly for all labyrinths of size at most n × n (independently of the positions of walls inside the square and the robot’s initial position).
• “Works correctly” means that the robot visits all reachable cells.
• To solve the traversal problem,
we prove that a sufficiently long random program will
work with positive probability.
• We will do this using the union bound.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 14
Preorder Traversals (1/2)
• For each n × n labyrinth, there is a program of size 4n4 that works for it, as each cell is reachable in at most 4n2 steps (round-trip) and there are at most n2 admissible cells.
• To prove this note that for each starting cell there is a
spanning tree reaching all the n2 cells of a given labyrinth,
think of it as a distributed network.
A
BC EFG
J
I
• Assign ports to each vertex (edge labels associated to the edges connected)
H
D
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 15
Preorder Traversals (2/2)
• Using a pre-order traversal of this spanning tree (which has length at most 4n2) every cell will be visited in at most 4n2 steps (round trip).
• Therefore, a random program of size N = 4n4 will work with probability at least ε = (1/4)4n4 and fail with probability at most 1 − ε.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 16
Universal Traversals
• Select among such programs of size N = 4n2 independently and uniformly at random.
• Now for each k concatenate k such programs: P1P2 ···Pk
– By independence, a random program of size 2N will fail with probability at most (1 − ε)2
– More generally, a random program of size kN will fail with probability at most (1 − ε)k.
• This probability is computed for a fixed labyrinth L.
• Let FL be the event that a program of size kN fails for the
labyrinth L.
• It follows from the above that Pr[FL] ≤ (1 − ε)k.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 17
Universal Traversals
• Now take the union L FL, where L runs over all labyrinths. As a consequence,
Pr FL ≤Pr[FL]
LL
≤ ln(1 − ε)k
where ln is the number of labyrinths in a n × n grid.
• However, we can choose k sufficiemtly large, so that
• So,
ln < 1 (2) (1−ε)k
PrFL <1 L
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 18
Universal Traversals
• In particular, for a k satisfying Inequality (2), we have that
Pr ¬FL =1−Pr FL LL
> 0.
• Therefore for k sufficiently large a random program of size kN
works for all labyrinths with positive probability. • Therefore such a program must exist!
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 19
Efficiency of Universal Traversals
• How about the length of the sequence of port labels?
– Can we construct a universal traversal sequence of polynomial length in polynomial time (in the size n of the graph)?
• How about efficiency?
– Can we give an algorithm to construct a universal traversal
sequence?
• Can we make the construction distributed?
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 20
Universal Traversals on Graphs
• The Universal Traversal theorem holds on graphs of a given size n.
• Instead of N,S,E,W used in n×n grids one now uses ports and port-labelings.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 21
Exercisesa
1. The traversal of the labyrinth was based on a sequence that was provided to the robot and which the robot must follow. Consider the situation where the robot constructs the sequence “on the fly”: looks at the surrounding environment and based on what it sees makes its next move according to some rule. This will be a local algorithm and the moves of the robot depend on the environment. Will such an algorithm perform a successful traversal?
2. (⋆) Use the probabilistic method to prove a Universal Traversal theorem on graphs of a given size.n. Hint: Instead of N,S,E,W used in n×n grids one now uses ports.
Consider a set of points in the plane. Form n sets
A1,A2,…,An on the plane each of which has k points.
aNot to submit.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 22
The sets are arbitrary and may share points. Assume that n < 2k. Show that If n < 2k then it is possible to color each point red or blue in such a way that every set Ai has both colors. Hint: Color each of the n points independently choosing red or blue with equal probability and use the probabilistic method.
3. A certain commodity is sold with two lottery tickets, a and b, for Prize A and Prize B, respectively. Suppose the winning probability for A and that for B are both 2/3. Show that there
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 23
must exist a commodity with two winning tickets.b
4. (⋆) The sets S1,S2,...,Sk are different subsets of a set S that has 2n elements. {S1, S2, . . . , Sk} is called a Sperner familyc if Si ̸⊆ Sj, for all i ̸= j. Use the probabilistic method to prove Spener’s theorem, namely “If {S1, S2, . . . , Sk} is a Sperner family then k ≤ 2n.” For the proof, follow the steps below.
n
(a) Consider the following process: We start with the emptyset and add random elements of S one by one until (after 2n steps) we get the whole set S. For a fixed subset A ⊂ S of size a show that A will appear during this process with probability Pr[A] = 1/2n.
a
(b) Consider k random variables X1, X2, . . . , Xk so that the
value of Xi is equal to 1 if the given set Si appears during
the process, otherwise, it is equal to 0. Show that the
bNote that the conclusion is derived without using event dependence. cSperner families have applications in Cryptography and elsewhere.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 24
expected value of Xi is 1/2n, where si is the number of si
elements in Si,
(c) Now, consider the random variable X = X1 +X2 +···+Xk. Show that this sum is less than 1 in expectation.
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)
Distributed Computing, COMP 4001 25
References
• Alon, N., Spencer, J. H. (2004). The probabilistic method. John Wiley & Sons.
• Hirokasu Iwasawa, Using Probability to Prove Existence, Mathematical Intelligencer, Volume 34, Number 3, 2012.
• Mathematical Intelligencer Volume 20, Number 4, 1998
• Aleliunas, R. Karp, R. Lipton, R. Lovasz, L. Rackoff, C. Random walks, universal traversal sequences, and the complexity of maze problems. 20th Annual Symposium on Foundations of Computer Science (FOCS 1979): 218?223
Evangelos Kranakis, Carleton University, SCS (October 31, 2020)