Title: How much memory is needed for leader election
Authors: E. Fusco, A. Pelc
Abstract:
We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state ``unfeasible'' otherwise, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for leader election in the class of arbitrary connected graphs. Weak LE can be achieved with O(log n) bits of memory for all connected graphs with at most n nodes and strong LE can be achieved with O(log n) bits of memory for all connected graphs with exactly n nodes (these assumptions cannot be removed). On the other hand, we show that Omega(log n) bits of memory are necessary to enable leader election even for the class of rings. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Delta using only O(loglog Delta) bits of memory, without any additional information. This proves an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs. Moreover, we prove that no automaton can solve the leader election problem for all trees, even in the weak form.
Title: Distributed tree comparison with nodes of limited memory
Authors: E. Fusco, A. Pelc
Abstract:
We consider the task of comparing two rooted trees with port labelings. Roots of the trees are joined by an edge and the comparison has to be carried out distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES, otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and of the other - label 1. Nodes are modeled as identical automata, and our goal is to establish trade-offs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario we are concerned with memory vs. time trade-offs. We show that if the automaton has x bits of memory, where x \geq c log n, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h>1 is Theta (max(h,n/x)). For the asynchronous scenario we study memory vs. number of messages trade-offs. We show that if the automaton has x bits of memory, where n \geq x \geq c log Delta, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n and of maximum degree at most Delta is Theta (n^2/x).
Title: Delays induce an exponential memory gap for rendezvous in trees
Authors: P. Fraigniaud, A. Pelc
Abstract:
Rendezvous in a graph is the task of meeting two mobile agents at some node of an unknown anonymous connected graph. The two identical agents start from arbitrary nodes in the graph and move from node to node with the goal of meeting. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Omega(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound O(log n) bits for rendezvous in arbitrary trees of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number l of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log l + loglog n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most l leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Omega(log l + loglog n) bits of memory is required for rendezvous, even in the class of trees with degrees bounded by 3.
Title: Same game, new tricks: What makes a good strategy in the Prisoner's Dilemma?
Authors: A. Pelc, K.J. Pelc
Abstract:
The aim of this paper is to distinguish between strategies in the Iterated Prisoner's Dilemma on the basis of their relative performance in a given population set. We first define a natural order on such strategies which disregards isolated disturbances, by using the limit of time-average payoffs. This order allows us to consider one strategy as strictly better than another in some population of strategies. We then determine a strategy sigma to be ``robust", if in any population consisting of copies of two types of strategies, sigma itself and some other strategy tau, the strategy sigma is never worse than tau. We present a large class of such robust strategies. Strikingly, robustness can accommodate an arbitrary level of generosity, conditional on the strength of subsequent retaliation; and it does not require symmetric retaliation. Taken together, these findings allow us to design strategies that significantly lessen the problem of noise, without forsaking performance. Finally, we show that no strategy exhibits robustness in all population sets of three or more strategy types.
Title: Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
Authors: J. Czyzowicz, A. Kosowski, A. Pelc
Abstract:
Two mobile agents modeled as points starting at different locations of an unknown terrain have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and epsilon-RV, when these points have to get at distance less than epsilon in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g., speed up or slow down the agent. Agents have bounded memory: their computational power is that of finite state machines. Our aim is to compare feasibility of exact and of epsilon-RV when agents are anonymous vs. when they are labeled. We first describe our results for exact RV. It turns out that for anonymous agents, RV is impossible even in many classes of simple terrains such as equilateral triangles. Moreover, we show that for a known terrain, a pair of anonymous agents accomplishing exact RV can be constructed, if and only if the terrain does not have non-trivial rotational symmetries. Labeled agents turn out to be much more powerful, however significant limitations apply in this case as well. Even labeled agents cannot solve the exact RV problem for the class of regular polygons with arbitrarily many vertices. It turns out that restricting the number of vertices of polygons helps. We show that, for any fixed integer k, labeled agents can solve exact RV in the class of all polygons with at most k vertices, even with an arbitrary number of triangular holes. Surprisingly, the restriction to triangular holes is necessary. Indeed, we prove that exact RV is unfeasible even for the class of triangles with quadrangular holes. If the terrain is known, rendezvous of labeled agents is always feasible. Allowing approximate meeting changes the situation drastically. For anonymous agents, epsilon-RV is possible for the class of regular polygons of bounded diameter (in contrast to exact RV). However, in the larger class of regular polygons of unbounded diameter, epsilon-RV of anonymous agents turns out to be impossible. On the other hand, when the agents are labeled, epsilon-RV is feasible even for the class of regular polygons with unbounded diameter.
Title: Consensus and mutual exclusion in a multiple access channel
Authors: J. Czyzowicz, L. Gasieniec, D. Kowalski, A. Pelc
Abstract:
We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availablity of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on $n$ and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(log^2 n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log^2 n).
Title: How to meet asynchronously (almost) everywhere
Authors: J. Czyzowicz, A. Labourel, A. Pelc
Abstract:
Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.
Title: Feasibility and complexity of
broadcasting with random transmission failures
Authors : A. Pelc, D. Peleg
Abstract:
We consider fault-tolerant broadcasting in the message passing and radio models under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p<1, and failures are independent. We study both omission and Byzantine transmission failures. Our goal is to establish conditions on feasibility and to estimate the complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n for n-node graphs and for sufficiently large n) under these scenarios.
Title: Asynchronous deterministic rendezvous in graphs
Authors: G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro
Abstract:
Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved.
Title: Oracle size: a new measure of difficulty for communication problems
Authors : P. Fraigniaud, D. Ilcinkas, A. Pelc
Abstract:
We study the problem of the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. While previous results about communication in networks used particular partial information available to nodes, such as the knowledge of the neighborhood or the knowledge of the network topology within some radius, our approach is quantitative: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes in order to perform efficient communication. It turns out that the minimum size of advice for which a distributed task can be accomplished efficiently can serve as a measure of the difficulty of this task. We use this measure to make a quantitative distinction between the difficulty of two apparently similar fundamental communication primitives: the broadcast and the wakeup. In both of them a distinguished node, called the source, has a message, which has to be transmitted to all other nodes of the network. In the wakeup, only nodes that already got the source message (i.e., are awake) can send messages to their neighbors, thus waking them up. In the broadcast, all nodes can send control messages even before getting the source message, thus potentially facilitating its future dissemination. In both cases we are interested in accomplishing the communication task with optimal message complexity, i.e., using a number of messages linear in the number of nodes. We show that the minimum size of advice permitting the wakeup with a linear number of messages in a n-node network, is Theta (n log n), while the broadcast with a linear number of messages can be achieved with advice of size O(n). We also show that the latter size of advice is almost optimal: no advice of size o(n) can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
Title : Tree exploration with an oracle
Authors : P. Fraigniaud, D. Ilcinkas, A. Pelc
Abstract :
We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (bits of advice) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of advice that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold number of bits of advice that turns out to be roughly log log D, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using at most log log D - c bits of advice, and we show that every algorithm using log log D - g(D) bits of advice, for any function g unbounded from above, has competitive ratio at least 2.
Title: Waking up anonymous ad hoc radio networks
Author: A. Pelc
Abstract:
We consider the task of waking up an anonymous ad hoc radio network from a single source, by a deterministic algorithm. In the beginning only the source is awake and has to wake up other nodes by disseminating messages throughout the network. Nodes of the network do not know its topology and they do not have distinct labels. In such networks some nodes are impossible to reach. A node in a network is accessible if it can be woken up by some (possibly network-dependent) deterministic algorithm. A deterministic wakeup algorithm for ad hoc networks is universal if it wakes up all accessible nodes in all networks. We study the question of the existence of such a universal wakeup algorithm. For synchronous communication we design a universal wakeup algorithm, and for asynchronous communication we show that no such algorithm exists.
Title: Centralized deterministic broadcasting in undirected multi-hop radio networks
Authors: D. Kowalski, A. Pelc
Abstract:
We consider centralized deterministic broadcasting in radio networks. The aim is to design a polynomial algorithm, which, given a graph G, produces a fast broadcasting scheme in the radio network represented by G. The problem of finding an optimal broadcasting scheme for a given graph is NP-hard, hence we can only hope for a good approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcasting scheme working in time O(D log n + log 2 n), for every n-node graph of diameter D.
Title: Complexity of searching for a black hole
Authors: J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc
Abstract:
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it.
Title: Searching for a black hole in tree networks
Authors: J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc
Abstract:
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given tree and given starting node we are interested in the fastest possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two ``extreme'' classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least 2 children.
Title: Power of communication in cooperative exploration of graphs
Authors: P. Fraigniaud, D. Ilcinkas, E. Markou, A. Pelc
Abstract:
We consider the task of exploring finite anonymous graphs by teams of mobile agents (modeled as finite automata) that have no a priori knowledge of the topology of the graph or of its size. Each edge has to be traversed by at least one agent. Information exchange between agents is crucial for performing such cooperative exploration. Our goal is to compare the strength of two communication scenarios from the point of view of feasibility of exploration: one is the meeting model in which agents can exchange information only when they meet at a node of the graph, and the other is the sharing model in which all agents can exchange all information available to them at each step of the exploration. We show that the sharing model is strictly stronger than the meeting model: there exists a family of graphs that cannot be explored by any finite team of agents in the meeting model but can be explored by just two agents in the sharing model. We also show that three agents are strictly stronger than two agents in the sharing model but no team of three agents can explore all graphs.
Title: Efficient exploration of faulty trees
Authors: E. Markou, A. Pelc
Abstract:
We consider the problem of exploration of trees, some of whose edges are faulty. A robot, situated in a starting node and unaware of the location of faults, has to explore the connected fault-free component of this node by visiting all its nodes. The cost of the exploration is the number of edge traversals. For a given tree and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An algorithm, for a given tree and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any line, and an exploration algorithm for any tree, whose overhead is at most 9/8 larger than that of a perfectly competitive algorithm. Both our algorithms are fairly natural and the total time of local computations used during exploration is linear in the size of the explored tree. Our main contribution is the analysis of performance of these algorithms, showing that natural exploration strategies perform well in faulty trees.
Title: Polynomial deterministic rendezvous in arbitrary graphs
Authors: D. Kowalski, A. Pelc
Abstract:
Two mobile agents have to meet at some node of a connected graph. We study deterministic algorithms for this problem, assuming that agents have distinct identifiers and are located in nodes of an unknown anonymous connected graph. Startup times of the agents are arbitrarily decided by the adversary. Deterministic rendezvous has been previously shown feasible in arbitrary graphs but the proposed algorithm was exponential in the number n of nodes and in the smaller identifier l, and polynomial in the difference t between startup times. We show a deterministic rendezvous algorithm polynomial in n, t and log l.
Title: Model driven architecture (MDA) of distributed systems
Authors: K. El Guemhioui
Abstract:
The MDA (Model Driven Architecture) approach is a new way of developing large distributed applications. One defines a platform independent model (PIM) that describes the business logic of a system undistorted by any technological details, and then transforms it into one or more platform-specific models (PSMs), each describing how the base model is implemented on a different execution environment (such as CORBA, or C#.NET). By developing functionality and behaviour once and only once, and then automatically deriving specific platform (technology) implementations, MDA aims to significantly improve software productivity and protect IT investments from technology obsolescence. The current MDA initiative does not give much guidance on how to define the PIM and PSMs, nor on how to derive the PSMs from the PIM. We intend to address the two aforementioned issues by (1) proposing a framework for a methodological and systematic specification of PIM and PSMs, and (2) devising a set of generative techniques for the automatic transformation of PIM into PSMs.
Title: Deterministic broadcasting time in radio networks of unknown topology
Authors: D. Kowalski, A. Pelc
Abstract:
In a seminal paper [BGI]
R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time complexity of broadcast in radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences 45 (1992), 104-126.
the authors considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They proved a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from [BGI]. Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time Omega(sqrt[4]{n}) on one of these graphs. In view of the randomized algorithm from [BGI], runnning in expected time O(D log n + log 2 n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.
Title:
Faster deterministic broadcasting in ad hoc radio networks
Authors: D. Kowalski, A. Pelc
Abstract:
We consider radio networks modeled as directed graphs. In ad hoc radio networks, every node knows only its own label and a linear bound on the size of the network but is unaware of the topology of the network, or even of its own neighborhood. The fastest currently known deterministic broadcasting algorithm working for arbitrary n-node ad hoc radio networks, has running time O (n log 2 n). Our main result is a broadcasting algorithm working in time O (n log n log D) for arbitrary n-node ad hoc radio networks of radius D. The best currently known lower bound on broadcasting time in ad hoc radio networks is Omega (n log D), hence our algorithm is the first to shrink the gap between bounds on broadcasting time in radio networks of arbitrary radius to a logarithmic factor. We also show a broadcasting algorithm working in time O (n log D) for complete layered n-node ad hoc radio networks of radius D. The latter complexity is optimal.
Title: Leader election in rings with nonunique labels
Authors: S. Dobrev, A. Pelc
Abstract:
We consider the leader election problem in a ring whose nodes have possibly nonunique labels. Every node knows a priori its own label and two integers, m and M, which are, respectively, a lower and an upper bound on the (unknown) size n of the ring. The aim is to decide whether leader election is possible and to perform it, if so. We consider both the synchronous and the asynchronous version of the problem and we are interested in message complexity in both cases. For the synchronous version we present an algorithm using O(n log n) messages and working in time O(M). Moreover, our algorithm uses O(n) messages when all identifiers are distinct. For the asynchronous version we show an Omega(nM) lower bound on message complexity for this problem, and present an algorithm for it using O(nM) messages.
Title: Tree exploration with little memory
Authors: K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc
Abstract:
A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. While O(log Delta) bits of memory suffice to explore any tree of maximum degree Delta if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed Omega(log log log n) bits of memory are needed for some such trees of size n). For the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound Omega (log n) on required memory size, and present an algorithm to accomplish this task with O(log 2 n)-bit memory, for all n-node trees.
Title: Optimal graph exploration without good maps
Authors: A. Dessmark, A. Pelc
Abstract:
A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class, is called the overhead of algorithm for this class of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or - in one case - close to smallest, overhead. An important contribution of this project is establishing lower bounds that prove optimality of these exploration algorithms.
Title: Tradeoffs between knowledge and time of communication
in geometric radio networks
Authors: A. Dessmark, A. Pelc
Abstract:
We consider deterministic broadcasting in geometric radio networks (GRN) whose nodes know only a limited part of the network. Nodes of a GRN are situated in the plane and each of them is equipped with a transmitter of some range r. A signal from this node can reach all nodes at distance at most r from it but if a node u is situated within the range of two nodes transmitting simultaneously, then a collision occurs at u and u cannot get any message. Each node knows the part of the network within knowledge radius s from it, i.e., it knows the positions, labels and ranges of all nodes at distance at most s. The aim of this paper is to study the impact of knowledge radius s on the time of deterministic broadcasting in a GRN with n nodes and eccentricity D of the source. The results depend on whether collision detection is available. First consider the scenario without collision detection, for arbitrary GRN. For s exceeding the largest range, or s exceeding the largest distance between any two nodes, we design an (optimal) broadcasting algorithm working in time O(D). For s=0, i.e., when knowledge of each node is limited to itself, we show a broadcasting algorithm working in time O(n). In contrast to this upper bound which assumes that each node knows its own position, we show a surprising result that broadcasting requires time Omega (n log n) for some GRN whose nodes do not have this knowledge. For symmetric GRN, we show that broadcasting time is O(D+ log n), assuming arbitrary positive knowledge radius. If the collision detection capability is additionally assumed, we show that optimal broadcasting time in symmetric GRN is Theta(D+ log n), even if knowledge radius is s=0. These results show sharp contrasts between the efficiency of broadcasting in geometric radio networks as compared to broadcasting in arbitrary graphs. They also show quantitatively the impact of various types of knowledge available to nodes on broadcasting time in GRN. Efficiency of broadcasting is influenced by knowledge radius, knowledge of individual positions when knowledge radius is zero, and awareness of collisions.