Drawing maps with advice☆
Highlights
► The tasks are not feasible without additional information, unless the graph is a tree. ► bits of advice are enough for both tasks and bits are not enough if . ► bits of advice are enough and necessary to recognize topology. ► bits of advice are necessary to construct a spanning tree. ► bits of advice are enough to construct a spanning tree.
Introduction
Knowing the topology of a network or at least a spanning tree of it is of significant help in organizing communication among nodes of the network and in accomplishing distributed tasks. It is well known that such tasks as, e.g., broadcasting or gossiping (information exchange) can be performed more efficiently when the topology of the network or a spanning tree of it are available to nodes, than when they have to be executed in an unknown network. One way of supplying this vital information to nodes is by means of exploration of the network, where a mobile agent has to traverse all links of the network and visit all its nodes. In fact, one of the main reasons to perform the well-studied task of graph exploration, see, e.g., [2], [4], [5], [14], [15], is to draw a faithful map of the graph that models the explored network. Provided that the agent has enough memory and computation power and that the exploration has been performed, drawing a map of the graph is easy, if nodes have distinct identities that can be perceived by the agent, or if the agent can leave marks at nodes when it visits them. However, neither of these assumptions is always satisfied. On the one hand, nodes may refuse to reveal their identities, e.g., for security reasons, or limited sensory capabilities of the agent may prevent it from perceiving these identities; on the other hand, nodes may not have facilities (whiteboards) allowing to leave marks, or such marks may be destructed between visits of the agent and thus unreliable. Thus it is important for the agent to be able to recognize the topology of the graph (draw a full map of the network) or construct its spanning tree (which is an important partial map of it) without relying on identities of the nodes and without marking them. In contrast, in order to allow the agent to move in the network, we have to assume that ports at every node are distinguishable for the agent. If an agent were unable to locally distinguish ports at a node, it may have even been unable to visit all neighbors of a node of degree at least 3. Indeed, after visiting the second neighbor, the agent cannot distinguish the port leading to the first visited neighbor from the port leading to the unvisited one. Thus an adversary may always force an agent to avoid all but two edges incident to such a node, thus effectively precluding exploration. Hence we assume that a node of degree has ports corresponding to the incident edges. Ports at each node can be perceived by an agent visiting this node, but there is no coherence assumed between port labelings at different nodes. We assume that when an agent reaches a node, it learns the port number by which it entered it.
We consider two map drawing tasks that have to be accomplished by a mobile agent executing a deterministic algorithm and walking in an unknown connected graph with unlabeled nodes and labeled ports. One is topology recognition which consists in returning an isomorphic copy of the graph with correctly numbered ports, and the other is spanning tree construction which consists in returning a spanning tree of the graph, again with correctly numbered ports. Both tasks have to be performed by an agent that starts in an arbitrary node of an unknown graph and is allowed to explore it. These tasks can be easily accomplished after exploration if the graph is a tree (and in this case they are obviously equivalent): after performing an Eulerian tour of the tree, the agent realizes this fact and can reconstruct the topology of the tree. (By an Eulerian tour we mean a closed walk of minimum length that visits each edge at least once. Note that for a tree, each edge will be visited exactly twice in such a tour). However, it turns out that unless the graph is a tree, none of these tasks can be accomplished without any additional information given to the agent.
Fig. 1 (cf. [35]) gives an example of two non-isomorphic graphs after whose exploration an agent will get identical information, and thus will not be able to distinguish them. Indeed, a stronger fact is true: for any graph that is not a tree, an agent that has explored the graph and has no additional information can neither recognize the topology of the graph, nor even construct its spanning tree. This yields the main problem that we study in this paper.
What is the minimum number of bits of a priori information required by an agent exploring a graph, in order to recognize its topology or to construct its spanning tree?
This way of stating the problem follows the paradigm of network algorithms with advice that has become recently popular (cf. the subsection “Related work”), and can be described as follows. An oracle knowing the entire network can give a string of bits (advice) to the mobile agent. (In other settings strings of bits are given to nodes that subsequently exchange messages). Then an algorithm is executed by the agent without knowing in which network it operates, using the provided advice. The total number of bits given by the oracle is the size of advice. Thus the framework of advice permits to quantify the amount of information needed to solve a network problem, regardless of the type of information that is provided.
Since for trees no additional information is needed, in the rest of the paper we assume that the explored graph is not a tree. It turns out that the size of advice needed to solve the two problems under investigation depends on three parameters: the number of nodes, the number of edges, and a crucial parameter called the multiplicity of the graph. Our multiplicity parameter is related to the symmetricity of a graph, defined in [35]. We define multiplicity for a graph with a particular port labeling, while is defined in [35] to be the maximum multiplicity over all port labelings of . This parameter depends on the notion of the view from a node. Intuitively, this is the infinite tree with labeled ports, rooted at the given node, that would be obtained by a complete infinite exploration of the graph, if each visited node were attached as a new node in the tree (see the formal definition in Section 2). Since nodes of the graph are not labeled and cannot be marked, and thus already visited nodes cannot be recognized on subsequent visits, the view from a node is the maximum information that can be obtained by an agent starting at this node and exploring the graph (cf. Proposition 2.2). It has been proved in [31] that if views of two nodes of a -node graph are different, then their views truncated to level are also different. Hence, knowing any upper bound on , the agent can learn in finite time which nodes have equal views and which do not. It is known (cf. [35]) that, for every node of a graph, the number of nodes from which the view is identical as that from is the same. This number is the multiplicity of the graph.
We give bounds on the minimum size of advice required by an agent both for the task of topology recognition and of spanning tree construction. (We focus on the feasibility of accomplishing these tasks and not on the complexity of their performance). For our bounds are asymptotically tight for both tasks and show that the minimum size of advice is very small: for an arbitrary function it suffices to give bits of advice to accomplish both tasks for -node graphs, and bits are not enough. For the minimum size of advice increases abruptly. In this case our bounds are asymptotically tight for topology recognition and asymptotically almost tight for spanning tree construction. We show that bits of advice are enough and necessary to recognize topology in the class of graphs with edges and multiplicity . For the second task we show that bits of advice are necessary and bits of advice are enough to construct a spanning tree in the class of graphs with nodes, edges and multiplicity . Thus in this case the gap between our bounds is always at most logarithmic, and the bounds are asymptotically tight, e.g., for multiplicity , where is any constant smaller than 1.
Our results imply the following, somewhat surprising comparison of the importance of graph exploration in accomplishing the two considered tasks. For the task of topology recognition, the fact that the agent can explore the graph has a small impact on the required size of advice, if . Indeed, for any , there are port-labeled non-isomorphic graphs with nodes, edges and multiplicity . Hence without any exploration it would be enough to give bits of advice to recognize topology (by giving the index of the graph in some ordered list of all such graphs), and with the help of exploration the number of bits is . Thus the capability to explore the graph is “worth” at most a logarithmic factor in the size of advice (the largest difference occurring when is constant). In other words, the fact that the agent can explore the graph decreases the size of advice needed for topology recognition only by a logarithmic factor, as compared to a motionless agent. By contrast, for the task of spanning tree construction, the possibility of exploring the graph may have a crucial impact on the required size of advice. Indeed, we prove that for any there are at least graphs with nodes and multiplicity , no pair of which has isomorphic spanning trees. Hence, without exploration, bits of advice would be necessary to solve the spanning tree construction problem. However, if the agent can explore the graph, only bits are sufficient to find a spanning tree. Thus, for any polylogarithmic in , the capability of exploring the graph is “worth” an exponential decrease of the size of advice required for spanning tree construction. In other words, an agent capable of exploring the graph requires exponentially smaller advice to solve the spanning tree construction problem, as compared with a motionless agent.
Network algorithms with advice were studied, e.g., in [16], [17], [18], [19], [20], [21], [24], [30]. When advice is given by the oracle to the nodes, rather than to a mobile agent, the advice paradigm becomes closely related to that of informative labeling schemes [1], [12], [22], [25], [26], [34]. In [12] it was shown that giving appropriate 2-bit labels to nodes of a graph allows an agent with a constant-size memory to explore all graphs, and that with 1-bit labels an agent can explore all graphs of bounded degree. In the advice paradigm the authors studied the minimum size of advice required for the solvability of the respective network problem or for its efficient solution. In [18] the authors compared the minimum size of advice required to solve two information dissemination problems using a linear number of messages. In [19] the authors established the size of advice given to a mobile agent, needed to break competitive ratio 2 of an exploration algorithm in trees. In [20] it was shown that advice of constant size permits to carry on the distributed construction of a minimum spanning tree in logarithmic time. In [17] the authors established lower bounds on the size of advice needed to beat time for 3-coloring of a cycle and to achieve time for 3-coloring of unoriented trees. It was also shown that, both for trees and for cycles, advice of size is needed to 3-color in constant time. In the case of [30] the issue was not efficiency but feasibility: it was shown that is the minimum size of advice required to perform monotone connected graph clearing, using the minimum number of searchers. In [24] the authors studied radio networks for which it is possible to perform centralized broadcasting in constant time by a distributed algorithm. They proved that bits of advice allow to obtain constant time in such networks, while bits are not enough. In [21] the trade-off between the size of advice and broadcasting time in trees was investigated, assuming that advice is given only to the source of broadcasting. In [16] the authors studied on-line computation with advice.
Computability in anonymous networks and feasibility of distributed tasks performed using message exchange in anonymous networks, without advice, have been studied, e.g., in [3], [8], [33], [35]. Rendezvous was considered in this context, e.g., in [13].
The concept of quotient graphs, which we use as defined in [35], has been studied extensively in different settings and under different names, such as minimum base. Boldi and Vigna provide a detailed description of fibrations, defined for the more general case of directed graphs [9]. In particular, they give a polynomial-time (off-line) algorithm that for a given graph computes its minimum base. Fibrations have been used e.g. in [7] for the leader election problem, which is a classical symmetry breaking problem, where it is assumed that the processors are indistinguishable and communicate over the network by exchanging messages. For some further work on the leader election problem and on the problem of assigning unique labels to the processors in a distributed system see [10], [23], [28]. The concept of quotient graph has been studied earlier in [3] using the notion of coverings, for the scenario of message passing systems. Both coverings and fibrations are often used to determine the situations where finding a solution to some problem is impossible due to the symmetry of the graph. Informally speaking, if a base graph or a graph covered by the graph that models the network map several nodes of the network into the same class, then all those nodes perform the same computation, and therefore they cannot be distinguished. In our case nodes are indistinguishable for an agent exploring the network. Our proof techniques have some similarities to the ones used in the above-mentioned papers, as proving such results usually reduces to the construction of two graphs in which the execution of the algorithm is identical. However, in this work we deal with graph exploration by an agent, rather than with message passing systems and hence symmetry breaking issues are sometimes different (in the presence of a single agent the leader election problem becomes trivial). Métivier et al. [29] proved that some additional knowledge (the size of the graph) must be provided to the nodes of the graph to make several computational tasks feasible in the message passing model.
Some of the techniques we apply, e.g. the idea of connecting independent isomorphic components with a cycle in order to obtain a graph of desired multiplicity (that we use in Lemma 4.1 and Proposition 5.1), are similar to those present in [6], [32].
Section snippets
Terminology and preliminaries
Networks are modeled as simple undirected connected graphs (without self-loops or multiple edges). Nodes of a graph are unlabeled and ports at a node of degree are arbitrarily labeled . Thus each edge has two labels, one at each extremity. We do not assume any coherence between port labelings at different nodes. Port labels are visible to an agent walking in the graph, that is, if the agent occupies a node , then it can recognize the port labels at for all edges incident to , and
Graphs with multiplicity 1
In this section we show that for graphs of multiplicity 1, bits of advice are enough to accomplish both the topology recognition and the spanning tree construction tasks (an arbitrarily slowly growing function of the size of the graph will do), but bits are not enough for either of these tasks.
Lemma 3.1 There exists no algorithm for an exploring agent that can find the number of nodes of the graph in the class of graphs of multiplicity 1, provided that bits of advice are given.
Proof The idea of
Topology recognition for graphs of multiplicity
In this section we establish asymptotically tight bounds on the size of advice needed for topology recognition in the class of graphs of any multiplicity .
Lemma 4.1 For any and there exist equivalent non-isomorphic graphs of multiplicity , where is a multiple of for and is arbitrary for .
Proof Fix the number of nodes , where . We define a graph with nodes. If , then is as in Fig. 4(a), while for the graph is given in Fig. 4(c). The quotient graph
Spanning tree construction for graphs of multiplicity
In this section we establish asymptotically almost tight bounds and on the size of advice needed for the spanning tree construction in the class of -node graphs of any multiplicity . These bounds differ by at most a logarithmic factor and are tight for multiplicity , where is any constant smaller than 1.
Lemma 5.1 For every and for every , where is an integer, there exists a collection of -node equivalent graphs with multiplicity , such that no
Conclusion
We established asymptotically tight bounds on the minimum size of advice required to solve the topology recognition problem. For the spanning tree construction problem, our bounds are asymptotically almost tight: and . Closing this (at most logarithmic) gap is a natural open problem. In this paper we focused only on the feasibility of these two map drawing tasks. Nevertheless, the cost of our algorithms, measured in terms of the number of edges traversed by the agent,
Acknowledgments
Thanks are due to the anonymous referees whose insightful and detailed comments helped us to improve the paper. This work was done during the visit of Dariusz Dereniowski at the Research Chair in Distributed Computing of the Université du Québec en Outaouais. The first author was partially supported by the MNiSW grant N N206 379337. The second author was partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
Dariusz Dereniowski is currently an Assistant Professor in the Department of Algorithms and System Modeling at the Gdansk University of Technology. He received his M.Sc. degree in Mathematics from the University of Gdansk and his Ph.D. in Computer Science from the Gdansk University of Technology. His research focuses on the problems of graph exploration, parallel scheduling and chromatic graph theory.
References (35)
- et al.
The power of a pebble: exploring and mapping directed graphs
Information and Computation
(2002) The classification of coverings of processor networks
Journal of Parallel and Distributed Computing
(1989)- et al.
Fibrations of graphs
Discrete Mathematics
(2002) - et al.
Optimal graph exploration without good maps
Theoretical Computer Science
(2004) - et al.
Tree exploration with advice
Information and Computation
(2008) - et al.
Distance labeling in graphs
Journal of Algorithms
(2004) - et al.
Fast radio broadcasting with advice
Theoretical Computer Science
(2010) Distributed enumeration
Information Processing Letters
(1997)- et al.
Graph searching with advice
Theoretical Computer Science
(2009) Universal covers of graphs: isomorphism to depth implies isomorphism to all depths
Discrete Applied Mathematics
(1995)
Compact labeling schemes for ancestor queries
SIAM Journal on Computing
Exploring unknown environments
SIAM Journal on Computing
Piecemeal learning of an unknown environment
Machine Learning
An efficient message passing election algorithm based on Mazurkiewicz’s algorithm
Fundamenta Informaticae
Cited by (47)
Finding the size and the diameter of a radio network using short labels
2021, Theoretical Computer ScienceCitation Excerpt :In some cases [3,15], the model without collision detection was used, in others [18,24], the collision detection capability was assumed. Providing nodes of a network, or mobile agents circulating in it, with information of arbitrary type (in the form of binary strings) that can be used by an algorithm to perform some network task, has been proposed in [1,4,6,8–13,17,21–23,25]. This approach was referred to as algorithms using informative labeling schemes, or equivalently, algorithms with advice.
Short labeling schemes for topology recognition in wireless tree networks
2021, Theoretical Computer ScienceCitation Excerpt :In some cases [2,13] the topology of the network was unknown, in others [14] nodes were assumed to have a labeled map of the network and could situate themselves in it. Providing nodes of a network or mobile agents circulating in it with information of arbitrary type (in the form of binary strings) that can be used either to perform network tasks otherwise infeasible, or to improve the efficiency of their solution, has been proposed in [1,3,4,6–11,15,18–20,23]. This approach was referred to as algorithms using informative labeling schemes, or equivalently, algorithms with advice.
Four shades of deterministic leader election in anonymous networks
2023, Distributed ComputingPebble guided Treasure Hunt in Plane
2023, arXivPebble Guided Treasure Hunt in Plane
2023, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Treasure Hunt in Graph using Pebbles
2022, arXiv
Dariusz Dereniowski is currently an Assistant Professor in the Department of Algorithms and System Modeling at the Gdansk University of Technology. He received his M.Sc. degree in Mathematics from the University of Gdansk and his Ph.D. in Computer Science from the Gdansk University of Technology. His research focuses on the problems of graph exploration, parallel scheduling and chromatic graph theory.
Andrzej Pelc got his M.Sc. and Ph.D. in Mathematics from the University of Warsaw, Poland, in 1977 and 1981, respectively. Since 1985 he has been Professor in the Department of Computer Science at the Université du Québec en Outaouais, in Canada. Since 2001 he has been Director of the Research Chair in Distributed Computing at this university. His main research interests include the construction and analysis of algorithms, distributed computing, communication algorithms in networks and fault-tolerance. He published over 250 journal and conference papers in Computer Science and Mathematics, and served on program committees of many international conferences. He was Program Committee Chair of the 21st International Symposium on Distributed Computing (DISC 2007) and Program Committee Co-Chair of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2005). He is currently Steering Committee Chair of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) and a member of editorial boards of three international journals. In 2003 he got the Research Excellence Prize of the Université du Québec en Outaouais.
- ☆
A preliminary version of this paper appeared in the Proc. 24th International Symposium on Distributed Computing (DISC 2010), LNCS 6343, 328–342.