Arrow Research search

Author name cluster

Andrzej Pelc

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

52 papers
2 author rows

Possible papers

52

TCS Journal 2026 Journal Article

Exploration of convex terrains by a deterministic automaton with pebbles

  • Mohamed Anouar Baaziz
  • Andrzej Pelc

A mobile agent, modeled as a deterministic finite automaton, has to explore a convex terrain, i. e. , a convex open subset of the plane. The agent starts at an unknown point of the terrain and makes a series of moves. Before each move it takes a snapshot, which is the part of the terrain included in the disc of radius 1 centered at the current position of the agent. This snapshot is an input that causes the agent to possibly change state and make the next move in a chosen direction at a chosen distance less than 1, inside the terrain. The agent explores the terrain if every point of it can be eventually “seen” by the agent, i. e. , is eventually in some snapshot. For many convex terrains, such exploration is impossible without marking the terrain in any way. Hence we allow the agent to use movable pebbles. A pebble can be dropped, subsequently seen by the agent if it returns to it, and possibly picked again. We consider the problem of determining the minimum number of pebbles sufficient for an agent to explore convex terrains. Our main result is a complete solution of this problem. We classify all convex terrains into five types, depending on whether the terrain contains a (infinite straight) line and whether it is bounded. For each of these types, we determine the minimum number of pebbles sufficient for exploration of all terrains of a given type. The agent is given the type of the terrain but does not know in which terrain of the given type it is operating and does not know its starting point. In all cases we determine the minimum number of pebbles sufficient for exploration. Each result has two parts. In the positive part, we design an algorithm that explores all terrains of a given type by an agent, using a given number of pebbles. In the negative part, we show that no agent using fewer pebbles can explore all terrains of the given type. The main methodological difficulty comes from the fact that, while the terrains to be explored are unbounded (apart from the easiest case of type 1 terrains), the agent exploring them has only finite memory and does not know which terrain it is exploring (the agent is designed to explore all terrains of a given type). Thus the exploration algorithms must be designed in a way to prevent the agent from “getting lost” in the terrain by entering a loop that would strand it in one direction, leaving some parts of the terrain unexplored. This has to be done using only few pebbles as markers. Organizing exploration in a way to prevent this danger, not knowing the explored terrain of a given type or the starting point, is our main algorithmic contribution.

Details DOI

TCS Journal 2025 Journal Article

Sniffing helps to meet: Deterministic rendezvous of anonymous agents in the grid

  • Younan Gao
  • Andrzej Pelc

Two identical anonymous mobile agents have to meet at a node of the infinite oriented grid whose nodes are unlabeled. This problem is known as rendezvous. The agents execute the same deterministic algorithm. Time is divided into rounds, and in each round each agent can either stay idle at the current node or move to an adjacent node. An adversary places the agents at two nodes of the grid at a distance at most D, and wakes them up in possibly different rounds. Each agent starts executing the algorithm in its wakeup round. If agents cannot leave any marks on visited nodes then they can never meet, even if they start simultaneously at adjacent nodes and know it. Hence, we assume that each agent marks any unmarked node it visits, and that an agent can distinguish if a node it visits has been previously marked or not. (If agents are ants then marking a node means secreting a chemical known as pheromone that can be subsequently sniffed). The time of a rendezvous algorithm is the number of rounds between the wakeup of the later agent and rendezvous. We ask the question whether the capability of marking nodes enables the agents to meet, and if so, what is the fastest rendezvous algorithm. We consider this rendezvous problem under three scenarios. In the first scenario, agents know D but may start with arbitrary delay. In the second scenario, they start simultaneously but do not have any a priori knowledge. In the third, most difficult scenario, we do not make any of the above facilitating assumptions. Agents start with arbitrary delay and they do not have any a priori knowledge. We prove that in the first two scenarios rendezvous can be accomplished in time O ( D ). This is clearly optimal. For the third scenario, we prove that there does not exist any rendezvous algorithm working in time o ( D 2 ), and we show an algorithm working in time O ( D 2 ). The above negative result shows a separation between the optimal complexity in the two easier scenarios and the optimal complexity in the most difficult scenario.

Details DOI

TCS Journal 2024 Journal Article

Deterministic rendezvous in infinite trees

  • Subhash Bhagat
  • Andrzej Pelc

The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set { 1, …, L }. They wake up at possibly different times and move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous algorithms. The time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. In most of the literature concerning rendezvous in graphs, the graph is finite and the time of rendezvous depends on its size. This approach is impractical for very large graphs and impossible for infinite graphs. For such graphs it is natural to design rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in infinite trees. All our algorithms work in finite trees as well. Our main goal is to study the impact of orientation of a tree on the time of rendezvous. We first design a rendezvous algorithm working for unoriented regular trees, whose time is in O ( z ( D ) log ⁡ L ), where z ( D ) is the size of the ball of radius D, i. e. , the number of nodes at distance at most D from a given node. The algorithm works for arbitrary delay between waking times of agents and does not require any initial information about parameters L or D. Its disadvantage is its complexity: z ( D ) is exponential in D for any degree d > 2 of the tree. We prove that this high complexity is inevitable: Ω ( z ( D ) ) turns out to be a lower bound on rendezvous time in unoriented regular trees, even for simultaneous start and even when agents know L and D. Then we turn attention to oriented trees. While for arbitrary delay between waking times of agents the lower bound Ω ( z ( D ) ) still holds, for simultaneous start the time of rendezvous can be dramatically shortened. We show that if agents know either a polynomial upper bound on L or a linear upper bound on D, then rendezvous can be accomplished in oriented trees in time O ( D log ⁡ L ), which is optimal. If no such extra knowledge is available, a significant speedup is still possible: in this case we design an algorithm working in time O ( D 2 + log 2 ⁡ L ).

Details DOI

TCS Journal 2021 Journal Article

Finding the size and the diameter of a radio network using short labels

  • Barun Gorain
  • Andrzej Pelc

The number of nodes of a network, called its size, and the largest distance between nodes of a network, called its diameter, are among the most important network parameters. Knowing the size and/or diameter (or a good upper bound on those parameters) is a prerequisite of many distributed network algorithms, ranging from broadcasting and gossiping, through leader election, to rendezvous and exploration. A radio network is a collection of stations, called nodes, with wireless transmission and receiving capabilities. It is modeled as a simple connected undirected graph whose nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node v hears a message from a neighbor w in a given round, if v listens in this round, and if w is its only neighbor that transmits in this round. If v listens in a round, and two or more neighbors of v transmit in this round, a collision occurs at v. If v transmits in a round, it does not hear anything in this round. Two scenarios are considered in the literature: if listening nodes can distinguish collision from silence (the latter occurs when no neighbor transmits), we say that the network has the collision detection capability, otherwise there is no collision detection. We consider the tasks of size discovery and diameter discovery: finding the size (resp. the diameter) of an unknown radio network with collision detection. All nodes have to output the size (resp. the diameter) of the network, using a deterministic algorithm. Nodes have labels which are (not necessarily distinct) binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on the following problems: What is the shortest labeling scheme that permits size discovery in all radio networks of maximum degree Δ? What is the shortest labeling scheme that permits diameter discovery in all radio networks? Our main result states that the minimum length of a labeling scheme that permits size discovery is Θ ( log ⁡ log ⁡ Δ ). The upper bound is proven by designing a size discovery algorithm using a labeling scheme of length O ( log ⁡ log ⁡ Δ ), for all networks of maximum degree Δ. The matching lower bound is proven by constructing a class of graphs (in fact even of trees) of maximum degree Δ, for which any size discovery algorithm must use a labeling scheme of length at least Ω ( log ⁡ log ⁡ Δ ) on some graph of this class. By contrast, we show that diameter discovery can be done in all radio networks using a labeling scheme of constant length.

Details DOI

TCS Journal 2021 Journal Article

Short labeling schemes for topology recognition in wireless tree networks

  • Barun Gorain
  • Andrzej Pelc

We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i. e. , an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node v hears a message from a neighbor w in a given round, if v listens in this round, and if w is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. Each node knows its label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems. • What is the shortest labeling scheme that permits topology recognition in all wireless tree networks of diameter D and maximum degree Δ? • What is the fastest topology recognition algorithm working for all wireless tree networks of diameter D and maximum degree Δ, using such a short labeling scheme? We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree Δ ≥ 3 is Θ ( log ⁡ log ⁡ Δ ). For such short labeling schemes, used by an algorithm working for the class of trees of diameter D ≥ 4 and maximum degree Δ ≥ 3, we show almost matching bounds on the time of topology recognition: an upper bound O ( D Δ ), and a lower bound Ω ( D Δ ϵ ), for any constant ϵ < 1. Our upper bounds are proven by constructing a topology recognition algorithm using a labeling scheme of length O ( log ⁡ log ⁡ Δ ) and using time O ( D Δ ). Our lower bounds are proven by constructing a class of trees for which any topology recognition algorithm must use a labeling scheme of length at least Ω ( log ⁡ log ⁡ Δ ), and a class of trees for which any topology recognition algorithm using a labeling scheme of length O ( log ⁡ log ⁡ Δ ) must use time at least Ω ( D Δ ϵ ), on some tree of this class.

Details DOI

TCS Journal 2020 Journal Article

Global Synchronization and Consensus Using Beeps in a Fault-Prone Multiple Access Channel

  • Kokouvi Hounkanli
  • Avery Miller
  • Andrzej Pelc

Global synchronization is an important prerequisite to many distributed tasks. Communication between processors proceeds in synchronous rounds. Processors are woken up in possibly different rounds. The clock of each processor starts in its wakeup round showing local round 0, and ticks once per round, incrementing the value of the local clock by one. The global round 0, unknown to processors, is the wakeup round of the earliest processor. Global synchronization (or establishing a global clock) means that each processor chooses a local clock round such that their chosen rounds all correspond to the same global round t. We study the task of global synchronization in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the beeping model. Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i. e. , stay silent, or beep, i. e. , emit a signal. In each round, a fault can occur in the channel independently with constant probability 0 < p < 1. In a fault-free round, an awake processor hears a beep if it listens in this round and if one or more other processors beep in this round. A processor still dormant in a fault-free round in which some other processor beeps is woken up by this beep and hears it. In a faulty round nothing is heard, regardless of the behaviour of the processors. An algorithm working with error probability at most ϵ, for a given ϵ > 0, is called ϵ-safe. Our main result is the design and analysis, for any ϵ > 0, of a deterministic ϵ-safe global synchronization algorithm that works in O ( log p 2 ⁡ ϵ ) time in any fault-prone MAC using beeps. As an application, we solve the consensus problem in a fault-prone MAC using beeps. Processors have input values from some set V and they have to decide the same value from this set. If all processors have the same input value, then they must all decide this value. Using global synchronization, we give a deterministic ϵ-safe consensus algorithm that works in time O ( ( log ⁡ w ) ( log p ⁡ ϵ ) ) in a fault-prone MAC, where w is the smallest input value of all participating processors. We show that this time cannot be significantly improved, even when the MAC is fault-free.

Details DOI

TCS Journal 2016 Journal Article

Topology recognition and leader election in colored networks

  • Dariusz Dereniowski
  • Andrzej Pelc

Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with not necessarily distinct labels called colors, and ports at each node of degree d are arbitrarily numbered 0, 1, …, d − 1. Colored networks are generalizations both of labeled networks, in which nodes have distinct labels, and of anonymous networks, in which nodes do not have labels (all nodes have the same color). In colored networks, topology recognition and leader election are not always feasible. Hence we study two more general problems. Consider a colored network and an input I given to its nodes. The aim of the problem TOP, for this colored network and for I, is to solve topology recognition in this network, if this is possible under input I, and to have all nodes answer “unsolvable” otherwise. Likewise, the aim of the problem LE is to solve leader election in this network, if this is possible under input I, and to have all nodes answer “unsolvable” otherwise. We show that nodes of a network can solve problems TOP and LE, if they are given, as input I, an upper bound k on the number of nodes of a given color, called the size of this color. On the other hand we show that, if the nodes are given an input that does not bound the size of any color, then the answer to TOP and LE must be “unsolvable”, even for the class of rings. Under the assumption that nodes are given an upper bound k on the size of a given color, we study the time of solving problems TOP and LE in the LOCAL model in which, during each round, each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. We give an algorithm to solve each of these problems in arbitrary networks in time O ( k D + D log ⁡ ( n / D ) ), where D is the diameter of the network and n is its size. We also show that this time is optimal, by exhibiting classes of networks in which every algorithm solving problems TOP or LE must use time Ω ( k D + D log ⁡ ( n / D ) ).

Details DOI

TCS Journal 2015 Journal Article

Fast rendezvous with advice

  • Avery Miller
  • Andrzej Pelc

Two mobile agents, starting from different nodes of an n-node network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set { 1, …, L }, which it can use in the execution of the algorithm, but it does not know the label of the other agent. The main efficiency measure of a rendezvous algorithm's performance is its time, i. e. , the number of rounds from the start of the earlier agent until the meeting. If D is the distance between the initial positions of the agents, then Ω ( D ) is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time O ( D ) is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time Θ ( D ). Following the standard paradigm of algorithms with advice, this information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i. e. , the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice, which can be used by the agents during their navigation. The length of this string is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to meet in time Θ ( D ). We show that this optimal size of advice is Θ ( D log ⁡ ( n / D ) + log ⁡ log ⁡ L ). The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time Θ ( D ) for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time Θ ( D ) with smaller advice.

Details DOI

TCS Journal 2014 Journal Article

Price of asynchrony in mobile agents computing

  • Yoann Dieudonné
  • Andrzej Pelc

Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and synchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost O ( D ℓ ), where ℓ is the length of the (binary representation of the) smaller label, while cost Ω ( D 2 + D ℓ ) is needed for asynchronous completion of rendezvous. Hence, for instances with ℓ = o ( D ), the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchronous rendezvous.

Details DOI

SODA Conference 2013 Conference Paper

Anonymous Meeting in Networks

  • Yoann Dieudonné
  • Andrzej Pelc

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An initial configuration of agents is called gatherable if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i. e. , algorithms that gather all gatherable configurations. The first algorithm works under the assumption that an upper bound n on the size of the network is known. In this case our algorithm guarantees gathering with detection, i. e. , the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound n on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. Leader election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign, in some common round, value 1 (leader) to one of the entities and value 0 (non-leader) to all others. For anonymous agents in graphs, leader election turns out to be equivalent to gathering with detection. Hence, as a by-product, we obtain a complete solution of the leader election problem for anonymous agents in arbitrary graphs.

Details

TCS Journal 2013 Journal Article

Gathering asynchronous oblivious agents with local vision in regular bipartite graphs

  • Samuel Guilbault
  • Andrzej Pelc

We consider the problem of gathering identical, memoryless, mobile agents in one node of an anonymous graph. Agents start from different nodes of the graph. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, an agent takes a snapshot of its immediate neighborhood (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. The novelty of our model with respect to the existing literature on gathering asynchronous oblivious agents in graphs is that the agents have very restricted perception capabilities: they can only see their immediate neighborhood. An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of “stars” (an agent A with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration.

Details DOI

TCS Journal 2012 Journal Article

Choosing the best among peers

  • Jurek Czyzowicz
  • Leszek Gąsieniec
  • Andrzej Pelc

A group of n peers, e. g. , computer scientists, has to choose the best, i. e. , the most competent among them. Each member of the group may vote for one other member, or abstain. Self-voting is not allowed. A voting graph is a directed graph in which an arc ( u, v ) means that u votes for v. While opinions may be subjective, resulting in various voting graphs, it is natural to assume that more competent peers are also, in general, more competent in evaluating competence of others. We capture this by proposing a voting system in which each member is assigned a positive integer value satisfying the following strict support monotonicity property: the value of x is larger than the value of y if and only if the sum of values of members voting for x is larger than the sum of values of members voting for y. Then we choose the member with the highest value, or if there are several such members, another election mechanism, e. g. , using randomness, chooses one of them. We show that for every voting graph there is a value function satisfying the strict support monotonicity property and that such a function can be computed in linear time. However, it turns out that this method of choosing the best among peers is vulnerable to vote manipulation: even one voter of very low value may change his/her vote so as to get the highest value. This is due to the possibility of loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs by erasing all arcs that belong to some cycle. This modification results in a pruned voting graph which is always a rooted forest. We show that for all pruned voting graphs there are value functions giving a guarantee against manipulation. More precisely, we show a value function guaranteeing that no coalition of k members all of whose values are lower than those of ( 1 − 1 / ( k + 1 ) ) n other members can manipulate their votes so that one of them gets the largest value. In particular, no single member from the lower half of the group is able to manipulate his/her vote to become elected. We also show that no better guarantee can be given for any value function satisfying the strict support monotonicity property.

Details DOI

TCS Journal 2011 Journal Article

Asynchronous deterministic rendezvous in bounded terrains

  • Jurek Czyzowicz
  • David Ilcinkas
  • Arnaud Labourel
  • Andrzej Pelc

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e. g. , speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

Details DOI

MFCS Conference 2010 Conference Paper

Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains

  • Jurek Czyzowicz
  • Adrian Kosowski
  • Andrzej 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 ε - RV, when these points have to get at distance less than ε 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 the feasibility of exact and of ε -RV when agents are anonymous vs. when they are labeled. We show classes of polygonal terrains which distinguish all the studied scenarios from the point of view of feasibility of rendezvous. The features which influence the feasibility of rendezvous include symmetries present in the terrains, boundedness of their diameter, and the number of vertices of polygons in the terrains.

Details

TCS Journal 2010 Journal Article

Fast radio broadcasting with advice

  • David Ilcinkas
  • Dariusz R. Kowalski
  • Andrzej Pelc

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under a complete knowledge of the network we give a tight answer to the above question: O ( n ) bits of advice are sufficient but o ( n ) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of the advice.

Details DOI

SODA Conference 2010 Conference Paper

How to Meet Asynchronously (Almost) Everywhere

  • Jurek Czyzowicz
  • Arnaud Labourel
  • Andrzej Pelc

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 in each segment of its route is continuous, does not leave it 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 powerful 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. 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.

Details

TCS Journal 2010 Journal Article

Remembering without memory: Tree exploration by asynchronous oblivious robots

  • Paola Flocchini
  • David Ilcinkas
  • Andrzej Pelc
  • Nicola Santoro

In an effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are n -node trees where Ω ( n ) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only O ( log n log log n ) robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree 3, whose exploration requires Ω ( log n log log n ) robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.

Details DOI

TCS Journal 2009 Journal Article

Gathering few fat mobile robots in the plane

  • Jurek Czyzowicz
  • Leszek Ga̧sieniec
  • Andrzej Pelc

Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.

Details DOI

TCS Journal 2008 Journal Article

Gathering asynchronous oblivious mobile robots in a ring

  • Ralf Klasing
  • Euripides Markou
  • Andrzej Pelc

We consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. Robots start from different nodes of the ring. They operate in Look–Compute–Move cycles and have to end up in the same node. In one cycle, a robot takes a snapshot of the current configuration (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. For an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. For an even number of robots we decide the feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.

Details DOI

MFCS Conference 2007 Conference Paper

Communication in Networks with Random Dependent Faults

  • Evangelos Kranakis
  • Michel Paquette
  • Andrzej Pelc

Abstract The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p ≤ 1/ c log n. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1/ n 1/2, and does not when p ∈ 1/ O ( n 1/2 ). Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ∈ 1/ O ( n 1/ d ). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults.

Details

TCS Journal 2007 Journal Article

Feasibility and complexity of broadcasting with random transmission failures

  • Andrzej Pelc
  • David Peleg

Fault-tolerant broadcasting in the message passing and radio models is considered 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. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time 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. If only node-omission failures are assumed, almost-safe broadcasting is feasible for any p < 1, in both communication models. For malicious transmission failures, almost-safe broadcasting in the message passing model is feasible iff p < 1 / 2, and in the radio model it is feasible iff p < ( 1 − p ) Δ + 1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, a number of upper and lower bounds are given in the various models.

Details DOI

TCS Journal 2006 Journal Article

Asynchronous deterministic rendezvous in graphs

  • Gianluca De Marco
  • Luisa Gargano
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc
  • Ugo Vaccaro

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. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O ( D | L min | 2 ) when D is known and O ( ( D + | L max | ) 3 ) if D is unknown, where | L min | and | L max | are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O ( n | L min | ), if the size n of the ring is known, and of cost O ( n | L max | ), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O ( D | L min | ) if the topology of the graph and the initial positions are known to agents.

Details DOI

TCS Journal 2006 Journal Article

Deterministic M2M multicast in radio networks

  • Leszek Gąsieniec
  • Evangelos Kranakis
  • Andrzej Pelc
  • Qin Xin

We study the problem of exchanging messages within a fixed group of k nodes, called participants, in an n-node radio network, modeled as an undirected graph. This communication task was previously considered in the setting of ATM video applications, in [J. M. Tsai, H. -H. Fang, C. -Y. Lee, A multicast solution for ATM video applications, IEEE Trans. Circuits Systems Video Technol. 7 (1997) 675–686], and was called multipoint-to-multipoint (M2M) multicasting. While the radio network topology is known to all nodes, it is assumed that no node is aware of the location of the participants. We give a distributed deterministic algorithm for the M2M multicasting problem in radio networks, and analyze its time complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O ( d log 2 n + k log 4 n ).

Details DOI

MFCS Conference 2006 Invited Paper

Tree Exploration with an Oracle

  • Pierre Fraigniaud
  • David Ilcinkas
  • Andrzej 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 (minimum oracle size) 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 \({\cal 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 information 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 oracle size that turns out to be roughly loglog 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 an oracle of size at most loglog D – c, and we show that every algorithm using an oracle of size loglog D – g ( D ), for any function g unbounded from above, has competitive ratio at least 2.

Details

MFCS Conference 2005 Conference Paper

Asynchronous Deterministic Rendezvous in Graphs

  • Gianluca De Marco
  • Luisa Gargano
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc
  • Ugo 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. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O ( D | L min | 2 ) when D is known and O (( D + | L max |) 3 ) if D is unknown, where | L min | and | L max | are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size but then we also give an optimal algorithm of cost O ( n | L min |), if the size n of the ring is known, and of cost O ( n | L max |), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O ( D | L min |) if the topology of the graph and the initial positions are known to agents.

Details

TCS Journal 2005 Journal Article

Graph exploration by a finite automaton

  • Pierre Fraigniaud
  • David Ilcinkas
  • Guy Peer
  • Andrzej Pelc
  • David Peleg

A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d ⩾ 3, there exists a planar graph of maximum degree d with at most K + 1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω ( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D + 1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ ( D log d ) bits.

Details DOI

MFCS Conference 2004 Conference Paper

Graph Exploration by a Finite Automaton

  • Pierre Fraigniaud
  • David Ilcinkas
  • Guy Peer
  • Andrzej Pelc
  • David Peleg

Abstract A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K -state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most K +1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω( D log d ) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth D +1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O ( D log d ) bits. We thus prove that the worst case space complexity of graph exploration is Θ( D log d ) bits.

Details

MFCS Conference 2003 Conference Paper

Randomized Algorithms for Determining the Majority on Graphs

  • Gianluca De Marco
  • Andrzej Pelc

Abstract Every node of an undirected connected graph is colored white or black. Adjacent nodes can be compared and the outcome of each comparison is either 0 (same color) or 1 (different colors). The aim is to discover a node of the majority color, or to conclude that there is the same number of black and white nodes. We consider randomized algorithms for this task and establish upper and lower bounds on their expected running time. Our main contribution are lower bounds showing that some simple and natural algorithms for this problem cannot be improved in general.

Details

FOCS Conference 2002 Conference Paper

Deterministic Broadcasting Time in Radio Networks of Unknown Topology

  • Dariusz R. Kowalski
  • Andrzej Pelc

In a seminal paper, Bar-Yehuda et al. (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed 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 the work of Bar-Yehuda et al. 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 /spl Omega/(4/spl radic/n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log/sup 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.

Details

MFCS Conference 1996 Conference Paper

Minimizing Congestion of Layouts for ATM Networks with Faulty Links

  • Leszek Gasieniec
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc

Abstract We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network K n of n processors in which a certain number of links may fail. Our main goal is to construct layouts which tolerate any configuration of up to f layouts and have a least possible congestion. First, we study the minimal congestion of 1-hop f -tolerant layouts in K n. For any positive integer f we give upper and lower bounds on this minimal congestion and construct f -tolerant layouts with congestion corresponding to the upper bounds. Our results are based on a precise analysis of the diameter of the network K n [ \(\mathcal{F}\) ] which results from K n by deleting links from a set \(\mathcal{F}\) of bounded size. Next we study the minimal congestion of h -hop f -tolerant layouts in K n, for larger values of the number h of hops. We give upper and lower bounds on the order of magnitude of this congestion, based on results for 1-hop layouts. Finally, we consider a random, rather than worst case, fault distribution. Links fail independently with constant probability p}<1. Our goal now is to construct layouts with low congestion that tolerate the existing faults with high probability. For any p}<1, we show such layouts in K n, with congestion O (log n ).

Details

MFCS Conference 1994 Conference Paper

Reliable Minimum Finding Comparator Networks

  • Piotr Denejko
  • Krzysztof Diks
  • Andrzej Pelc
  • Marek Piotrów

Abstract We consider the problem of constructing reliable minimum finding networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n > 2 items in the presence of k > 0 faulty comparators. We prove that the depth of any such network is at least max([log n ] + 2 k, log n + k log log n/k +1). We also describe a network whose depth nearly matches the lower bound. The lower bounds should be compared with the first nontrivial upper bound O (log n + k log log n /log k ) on the depth of k -fault tolerant sorting networks that was recently derived by Leighton and Ma [6].

Details