Title: Impact of Knowledge on Election Time in Anonymous Networks

Authors: Y. Dieudonné, A. Pelc

Abstract:

Leader election is one of the basic problems in distributed computing. For anonymous networks, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in arbitrary anonymous networks. It is well known that leader election is impossible in some networks, regardless of the allocated amount of time, even if nodes know the map of the network. However, even in networks in which it is possible to elect a leader knowing the map, the task may be still impossible without any knowledge, regardless of the allocated time. On the other hand, for any network in which leader election is possible knowing the map, there is a minimum time, called the election index, in which this can be done. Informally, the election index of a network is the minimum depth at which views of all nodes are distinct. Our aim is to establish tradeoffs between the allocated time T and the amount of information that has to be given a priori to the nodes to enable leader election in time T in all networks for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information is provided to all nodes at the start by an oracle knowing the entire network. The length of this string (its number of bits) is called the size of advice. For a given time T allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time T. We focus on the two sides of the time spectrum and give tight (or almost tight) bounds on the minimum size of advice for these extremes. We also show that constant advice is not sufficient for leader election in all graphs, regardless of the allocated time.

Title: Exploration of Faulty Hamiltonian Graphs

Authors: D. Caissy, A. Pelc

Abstract:

We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network 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 exploration algorithm, for a given network 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 ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm.

Title: Deterministic Graph Exploration with Advice

Authors: B. Gorain, A. Pelc

Abstract:

We consider the task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,…,d-1. A mobile agent has to visit all nodes and stop. The exploration time is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm. This a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. We first consider exploration in polynomial time, and determine the exact minimum size of advice to achieve it. This size is logloglogn-\Theta(1), for both types of oracles. When advice is large, there are two natural time thresholds: \Theta(n2) for a map oracle, and \Theta(n) for an instance oracle, that can be achieved with sufficiently large advice. We show that, with a map oracle, time \Theta(n2) cannot be improved in general, regardless of the size of advice. We also show that the smallest size of advice to achieve this time is larger than n^\delta, for any \delta<1/3. For an instance oracle, advice of size O(nlogn) is enough to achieve time O(n). We show that, with any advice of size o(nlogn), the time of exploration must be at least n^\epsilon, for any \epsilon<2, and with any advice of size O(n), the time must be \Omega(n2). We also investigate minimum advice sufficient for fast exploration of hamiltonian graphs.

Title: Asynchronous Broadcasting with Bivalent Beeps

Authors: K. Hounkanli, A. Pelc

Abstract:

In broadcasting, one node of a network has a message that must be learned by all other nodes. We study deterministic algorithms for this fundamental communication task in a very weak model of wireless communication. The only signals sent by nodes are beeps. Moreover, they are delivered to neighbors of the beeping node in an asynchronous way: the time between sending and reception is finite but unpredictable. We first observe that under this scenario, no communication is possible, if beeps are all of the same strength. Hence we study broadcasting in the bivalent beeping model, where every beep can be either soft or loud. At the receiving end, if exactly one soft beep is received by a node in a round, it is heard as soft. Any other combination of beeps received in a round is heard as a loud beep. The cost of a broadcasting algorithm is the total number of beeps sent by all nodes. We consider four levels of knowledge that nodes may have about the network: anonymity (no knowledge whatsoever), ad-hoc (all nodes have distinct labels and every node knows only its own label), neighborhood awareness (every node knows its label and labels of all neighbors), and full knowledge (every node knows the entire labeled map of the network and the identity of the source). We first show that in the anonymous case, broadcasting is impossible even for very simple networks. For each of the other three knowledge levels we provide upper and lower bounds on the minimum cost of a broadcasting algorithm. Our results show separations between all these scenarios. Perhaps surprisingly, the jump in broadcasting cost between the ad-hoc and neighborhood awareness levels is much larger than between the neighborhood awareness and full knowledge levels, although in the two former levels knowledge of nodes is local, and in the latter it is global.

Title: Deterministic Meeting of Sniffing Agents in the Plane

Authors: S. Elouasbi, A. Pelc

Abstract:

Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are integers from the set {0,…,L-1} . Each agent knows L and knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. Agents have sensors enabling them to estimate the distance from the other agent, but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than \rho or at distance at least \rho from the other agent, for some real \rho>1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance. In the monotone model it is assumed that the sensor is ideally accurate and can measure any change of intensity. In the binary model it is only assumed that the sensor can detect the scent below some distance (without being able to measure intensity) above which the scent is too weak to be detected. We show the impact of the two ways of sensing on the time of meeting, measured from the start of the later agent. For the monotone model we show an algorithm achieving meeting in time O(D), where D is the initial distance between the agents. This complexity is optimal. For the binary model we show that, if agents start at distance smaller than \rho (i.e., when they sense each other initially) then meeting can be guaranteed within time O(\rho logL), and that this time cannot be improved in general. Finally we observe that, if agents start at distance \alpha \rho, for some constant \alpha>1 in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting time is of the same order of magnitude as without any sniffing ability.