Deterministic rendezvous problem

Last updated March 19, 2024

The deterministic rendezvous problem is a variant of the rendezvous problem where the players, or robots, must find each other by following a deterministic sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for symmetry breaking. Typically, the robots act synchronously, though non-synchronous versions of the deterministic rendezvous problem exist.^[1]

Overview

In the synchronous version of the deterministic rendezvous problem, both robots are initially placed at arbitrary nodes in a finite, connected, undirected graph. The size and structure of the graph is unknown to the robots.

The information known by a robot is as follows:

T, the number of time steps since it has been activated
d, the degree of the node currently occupied by the robot
L, the label of the robot (typically taking the form of a bit string)

To solve the deterministic rendezvous problem, both robots must be given a sequence of deterministic instructions which allow the robots to use their known information to find each other. The robots are considered to have found each other if they are both occupying the same node in the graph during the same time step.^[1]

Solutions

A number of algorithms exist to solve the deterministic rendezvous problem. Some of the solutions are listed below:

Dessmark et al.

In 2006, Dessmark et al. presented a solution which solves the deterministic rendezvous problem in time proportional to ${\textstyle O\left(n^{5}{\sqrt {\tau l}}+n^{10}l\right)}$ , where:

n is the number of nodes in the graph
τ is the difference in activation time between the two robots
l is the length of the shorter of the labels of the robots

This solution is not ideal, since τ is an input parameter of the deterministic rendezvous problem and can therefore be arbitrarily large.^[2]

Kowalski and Malinowski

In 2008, Kowalski and Malinowski presented a solution which solves the problem in ${\textstyle O\left(n^{15}+l^{3}\right)}$ time.^[3] This is a significant improvement, since this time complexity is not dependent on τ. This solution has one major drawback, though. It makes use of backtracking, where the robots must keep track of each edge that they have traversed. This is a drawback because it places assumptions on the structure of the graph (namely, how it is labeled), and the robots' sensory and memory capabilities.

Ta-Shma and Zwick

The solution presented by Ta-Shma and Zwick in 2014 solves the problem in ${\textstyle O\left(n^{5}+l\right)}$ time. In addition to the reduced time complexity (which doesn't rely on τ), this solution also doesn't use backtracking. Instead, it uses the notion of universal traversal sequences to help solve the problem.^[1]

A universal traversal sequence is a sequence of instructions comprising a graph traversal for any regular graph with a set number of vertices and for any starting vertex.^[4] Since the robots may not be in a regular graph, a universal traversal sequence for n nodes and degree d is used, where d is the maximum degree of the graph. Any instructions in the chosen universal traversal sequence which specify that the robot travels to a neighbor of the current node which doesn't exist (i.e., the current node has degree < d) are ignored. By doing this, all nodes in the graph with degree less than d are treated as having enough self-loops to bring their total degree up to d, effectively allowing the graph to be treated as regular for the purpose of universal traversals.^[1]

The basic idea of Ta-Shma and Zwick's solution is that if one of the robots completes a complete traversal of the graph while the other robot remains idle, or rests, then the two robots are guaranteed to meet. Since the size of the graph is unknown, the robots run universal traversal sequences for increasing values of n, while periodically resting. Whether a robot rests before or after a traversal depends upon the value of its label.^[1]

For example, one of the robots could run the sequence:

U_{1}0^{u_{1}}U_{2}0^{u_{2}}U_{4}0^{u_{4}}U_{8}0^{u_{8}}...U_{2^{i}}0^{u_{2^{i}}}...

while the other robot runs the sequence:

0^{u_{1}}U_{1}0^{u_{2}}U_{2}0^{u_{4}}U_{4}0^{u_{8}}U_{8}...0^{u_{2^{i}}}U_{2^{i}}...

where U_i is a universal traversal sequence for a graph with i nodes, u_i is the number of steps in that universal traversal sequence, and 0^k represents k steps where the robot rests. The universal traversal sequence for the size of the actual graph will be run by one robot while the other rests for the number of steps in that traversal. However, this only works if the two robots are activated at the same time.^[1]

To cover the case where the robots are activated at different times, the sequence to run will include rest periods of length u_i after each step (in the traversal and the rest period). For example, one of the robots would run the sequence:

\sigma _{1}0^{u_{1}-1}\sigma _{2}0^{u_{1}-1}\sigma _{3}0^{u_{1}-1}...\sigma _{u_{1}}0^{u_{1}-1}0^{2u_{1}}\pi _{1}0^{u_{2}-1}\pi _{2}0^{u_{2}-1}\pi _{3}0^{u_{2}-1}...\pi _{u_{2}}0^{u_{2}-1}0^{2u_{2}}

where σ_i is the i^th step of U₁ and π_i is the i^th step of U₂.^[1]

In order to formally present the sequence that each robot will run, some additional notation is needed. Let:

σ^b = 0 if b = 0
σ^b = σ if b = 1
${\bar {L}}=1-L$
$\sigma ^{m_{1}..m_{k}}=\sigma _{1}^{m}...\sigma _{k}^{m}$
$D_{k}(\sigma _{1}...\sigma _{m})=\sigma _{1}0^{k}...\sigma _{m}0^{k}$

Assuming that one robot's label is 0 and that the other robot's label is 1, the sequence that each robot would run is:

D_{u_{1}-1}((U_{1}U_{1})^{L{\bar {L}}})D_{u_{2}-1}((U_{2}U_{2})^{L{\bar {L}}})...D_{u_{2^{k}}-1}((U_{2^{k}}U_{2^{k}})^{L{\bar {L}}})...

The sub-sequence ${\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L{\bar {L}}})}$ is known as a block and can be rewritten as ${\textstyle D_{u_{i}-1}((U_{i}U_{i})^{L}(U_{i}U_{i})^{\bar {L}})}$ .

If σ = U_i and m = u_i, the block can be further simplified to:

(\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{L}

(\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1})^{\bar {L}}

Both of the above lines are known as chunks. One chunk consists of a universal traversal sequence with interleaved rest periods, while the other chunk is a rest period of length 2m².

If the robot's label is 0, then each block it runs is equal to:

0^{2m^{2}}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}

If the label is 1, then each block it runs is equal to:

\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}\sigma _{1}0^{m-1}...\sigma _{m}0^{m-1}0^{2m^{2}}

Analysis

The sequence of instructions listed above will allow two robots with labels 0 and 1 to meet after O(n^2c) time steps.^[1]

Ta-Shma and Zwick show how to extend this solution to allow the robots to meet after only O(n^c) time steps and how to deal with arbitrary labels (which increases the time until the robots meet to O(n⁵+l) time steps).^[1]

Related Research Articles

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

<span class="mw-page-title-main">Navier–Stokes equations</span> Equations describing the motion of viscous fluid substances

The Navier–Stokes equations are partial differential equations which describe the motion of viscous fluid substances. They were named after French engineer and physicist Claude-Louis Navier and the Irish physicist and mathematician George Gabriel Stokes. They were developed over several decades of progressively building the theories, from 1822 (Navier) to 1842–1850 (Stokes).

<span class="mw-page-title-main">Breadth-first search</span> Algorithm to search the nodes of a graph

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

In physics, a Langevin equation is a stochastic differential equation describing how a system evolves when subjected to a combination of deterministic and fluctuating ("random") forces. The dependent variables in a Langevin equation typically are collective (macroscopic) variables changing only slowly in comparison to the other (microscopic) variables of the system. The fast (microscopic) variables are responsible for the stochastic nature of the Langevin equation. One application is to Brownian motion, which models the fluctuating motion of a small particle in a fluid.

The Feynman–Kac formula, named after Richard Feynman and Mark Kac, establishes a link between parabolic partial differential equations (PDEs) and stochastic processes. In 1947, when Kac and Feynman were both Cornell faculty, Kac attended a presentation of Feynman's and remarked that the two of them were working on the same thing from different directions. The Feynman–Kac formula resulted, which proves rigorously the real-valued case of Feynman's path integrals. The complex case, which occurs when a particle's spin is included, is still an open question.

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

In physics, the Hamilton–Jacobi equation, named after William Rowan Hamilton and Carl Gustav Jacob Jacobi, is an alternative formulation of classical mechanics, equivalent to other formulations such as Newton's laws of motion, Lagrangian mechanics and Hamiltonian mechanics.

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

<i>m</i>-ary tree Tree data structure in which each node has at most m children.

In graph theory, an m-ary tree is an arborescence in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.

In computer science, a longest common substring of two or more strings is a longest string that is a substring of all of them. There may be more than one longest common substring. Applications include data deduplication and plagiarism detection.

String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories. They are a prominent tool in applied category theory. When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation. This has led to the development of categorical quantum mechanics where the axioms of quantum theory are expressed in the language of monoidal categories.

In computational phylogenetics, tree alignment is a computational problem concerned with producing multiple sequence alignments, or alignments of three or more sequences of DNA, RNA, or protein. Sequences are arranged into a phylogenetic tree, modeling the evolutionary relationships between species or taxa. The edit distances between sequences are calculated for each of the tree's internal vertices, such that the sum of all edit distances within the tree is minimized. Tree alignment can be accomplished using one of several algorithms with various trade-offs between manageable tree size and computational effort.

Assortativity, or assortative mixing, is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree. The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

In mathematical physics, spacetime algebra (STA) is the application of Clifford algebra Cl_1,3(R), or equivalently the geometric algebra G(M⁴) to physics. Spacetime algebra provides a "unified, coordinate-free formulation for all of relativistic physics, including the Dirac equation, Maxwell equation and General Relativity" and "reduces the mathematical divide between classical, quantum and relativistic physics."

In mathematics and theoretical physics, Noether's second theorem relates symmetries of an action functional with a system of differential equations. The action S of a physical system is an integral of a so-called Lagrangian function L, from which the system's behavior can be determined by the principle of least action.

In computer science and mathematical logic, an infinite-tree automaton is a state machine that deals with infinite tree structures. It can be seen as an extension of top-down finite-tree automata to infinite trees or as an extension of infinite-word automata to infinite trees.

In artificial intelligence and related fields, an argumentation framework is a way to deal with contentious information and draw conclusions from it using formalized arguments.

In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:

A graph neural network (GNN) belongs to a class of artificial neural networks for processing data that can be represented as graphs.

References

1 2 3 4 5 6 7 8 9 Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12. doi:10.1145/2601068. S2CID 10718957.
↑ Dessmark, A.; Fraingnaud, P.; Kowalski, D.; Pelc, A. (2006). "Deterministic rendezvous in graphs". Algorithmica. 46 (1): 69–96. doi:10.1007/s00453-006-0074-2. S2CID 22236305.
↑ Kowalski, D.; Malinowski, A. (2008). "How to meet in anonymous network". Theoretical Computer Science. 399 (1–2): 144–156. doi: 10.1016/j.tcs.2008.02.010 .
↑ Aleliunas, R.; Karp, R.; Lipton, R.; Lovász, L.; Rackoff, C. (1979). "Random walks, universal traversal sequences, and the complexity of maze problems". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979): 218–223. doi:10.1109/SFCS.1979.34. S2CID 18719861.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Ta-Shma_2014-1] 1 2 3 4 5 6 7 8 9 Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12. doi:10.1145/2601068. S2CID 10718957.

[2] Dessmark, A.; Fraingnaud, P.; Kowalski, D.; Pelc, A. (2006). "Deterministic rendezvous in graphs". Algorithmica. 46 (1): 69–96. doi:10.1007/s00453-006-0074-2. S2CID 22236305.

[Kowalski_2008-3] Kowalski, D.; Malinowski, A. (2008). "How to meet in anonymous network". Theoretical Computer Science. 399 (1–2): 144–156. doi: 10.1016/j.tcs.2008.02.010 .

[Aleliunas_1979-4] Aleliunas, R.; Karp, R.; Lipton, R.; Lovász, L.; Rackoff, C. (1979). "Random walks, universal traversal sequences, and the complexity of maze problems". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979): 218–223. doi:10.1109/SFCS.1979.34. S2CID 18719861.

[1]

[2]

[3]

[4]