Deterministic rendezvous for two anonymous mobile agents navigating synchronously in an anonymous connected graph calls for their meeting at some node. This is a distributed symmetry breaking task equivalent to the fundamental task of leader election between the agents. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are initial positions of the agents. Such an instance is feasible if there is a deterministic algorithm, possibly valid only for this instance, that guarantees rendezvous for it. A rendezvous algorithm is universal for a class of instances, if it is valid for all feasible instances from this class.

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.

We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a message and all messages have to reach all nodes). Nodes are assigned labels that are (not necessarily different) binary strings. Each node knows its own label and can use it as a parameter in the same deterministic algorithm. The length of a labeling scheme is the largest length of a label. The goal is to find labeling schemes of asymptotically optimal length for the above tasks, and to design fast deterministic distributed algorithms for each of them, using labels of optimal length. Our main result concerns broadcasting. We show the existence of a labeling scheme of constant length that supports broadcasting in time O(D+log² n), where D is the diameter of the network and n is the number of nodes. This broadcasting time is an improvement over the best currently known O(Dlog n + log² n) time of broadcasting with constant-length labels, due to Ellen and Gilbert (SPAA 2020). It also matches the optimal broadcasting time in radio networks of known topology. Hence, we show that appropriately chosen node labels of constant length permit to achieve, in a distributed way, the optimal centralized broadcasting time. This is, perhaps, the most surprising finding of this paper. We are able to obtain our result thanks to a novel methodological tool of propagating information in radio networks, that we call a 2-height respecting tree. Next, we apply our broadcasting algorithm to solve the gossiping problem. We get a gossiping algorithm working in time O(D + Δlog n + log² n), using a labeling scheme of optimal length O(log Δ), where Δ is the maximum degree. Our time is the same as the best known gossiping time in radio networks of known topology.

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.

Linial's seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $\log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.

A team of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node and declare that they have all met. Agents have different labels which are positive integers, and move in synchronous rounds along links of the network. The above task is known as gathering and was traditionally considered under the assumption that when some agents are at the same node then they can talk, i.e., exchange currently available information. In this paper we ask the question of whether this ability of talking is needed for gathering. The answer turns out to be no.

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [ 3 ] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s . The size of the tank is B = 2 (1+α) r , for some positive real constant α, where r , called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most ⌊ B ⌋ edge traversals between two consecutive visits at node s . Let e(d) be the number of edges whose at least one endpoint is at distance less than d from s . Awerbuch et al. [ 3 ] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d) . We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d ) and then show how to modify this algorithm to work in the model from Awerbuch et al. [ 3 ] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ ( e(d) ) for all graphs, and thus our algorithms are also almost optimal.

Abstract Treasure hunt is finding a hidden inert target by a mobile agent. We consider deterministic algorithms for treasure hunt in trees. Our goal is to establish the impact of different kinds of initial knowledge given to the agent on the cost of treasure hunt, defined as the total number of edge traversals until the agent reaches the treasure. The agent can be initially given either a complete map of the tree rooted at its starting node, with all port numbers marked, or a blind map of the tree rooted at its starting node but without port numbers. It may also be given, or not, the distance from the root to the treasure. This yields four different knowledge types that are partially ordered by their precision. The penalty of a less precise knowledge type over a more precise knowledge type measures intuitively the worst‐case ratio of the cost of an algorithm supplied with knowledge of type over the cost of an algorithm supplied with knowledge of type . Our main results establish penalties for comparable knowledge types in this partial order. For knowledge types with known distance, the penalty for having a blind map over a complete map turns out to be very large. By contrast, for unknown distance, the penalty of having a blind map over having a complete map is small. When a map is provided (either complete or blind), the penalty of not knowing the distance over knowing it is medium.

Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader , and for all other nodes to become non-leaders . We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour transmitting in this round. If v listens in a round in which more than one neighbour transmits, then v hears noise that is different from any message and different from silence. We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider configurations . A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time O ( n 2 σ, where n is the number of nodes and σ is the difference between the largest and smallest tag of the configuration. We then ask the question whether there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$. The size of the tank is $B=2(1+α)r$, for some positive real constant $α$, where $r$, called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge traversals between two consecutive visits at node $s$. Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$. We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $\mathcal{O}(e(d) \log d)$, and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Θ(e(d))$ for all graphs and thus our algorithms are also almost optimal.

No abstract available.

Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs 'leader' and all other nodes output 'non-leader', or in a strong way, where all nodes must also learn which node is the leader. If the nodes have distinct identifiers, then such an agreement means that all nodes have to output the identifier of the elected leader. For anonymous networks, the strong version of leader election requires that all nodes must be able to find a path to the leader, as this is the only way to identify it. In this paper, we study variants of deterministic leader election in arbitrary anonymous networks. Leader election is impossible in some anonymous networks, regardless of the allocated amount of time, even if nodes know the entire map of the network. This is due to possible symmetries in 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 initial knowledge, regardless of the allocated time. On the other hand, for any network in which leader election (weak or strong) is possible knowing the map, there is a minimum time, called the 'election index', in which this can be done. We consider four formulations of leader election discussed in the literature in the context of anonymous networks : one is the weak formulation, and the three others specify three different ways of finding the path to the leader in the strong formulation. Our aim is to compare the amount of initial information needed to accomplish each of these "four shades" of leader election in minimum time. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire network. The length of this string is called the size of advice. We show that the size of advice required to accomplish leader election in the weak formulation in minimum time is exponentially smaller than that needed for any of the strong formulations. Thus, if the required amount of advice is used as a measure of the difficulty of the task, the weakest version of leader election in minimum time is drastically easier than any version of the strong formulation in minimum time.

We consider the fundamental problems of size discovery and topology recognition in radio networks modeled by simple undirected connected graphs. Size discovery calls for all nodes to output the number of nodes in the graph, called its size, and in the task of topology recognition each node has to learn the topology of the graph and its position in it. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbor transmits). The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Nodes have labels which are (not necessarily different) binary strings. Each node knows its own label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. For size discovery, we construct a labeling scheme of length O(log logΔ) (which is known to be optimal, even if collision detection is available) and we design an algorithm for this problem using this scheme and working in time O(log² n), where n is the size of the graph. We also show that time complexity O(log² n) is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length O(log logΔ). For topology recognition, we construct a labeling scheme of length O(logΔ), and we design an algorithm for this problem using this scheme and working in time O (DΔ+min(Δ²,n)), where D is the diameter of the graph. We also show that the length of our labeling scheme is asymptotically optimal.

Abstract A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $${\mathbb {Z}} \times {\mathbb {Z}}$$ Z × Z . Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the shape , is initially connected. The (Manhattan) distance between the furthest cells of the shape is called its span . The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest . That is, the robot has to move all bricks in such a way that the span of the resulting shape be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected shape, in time $$O(sn)$$ O ( s n ) , where s is the span of the initial shape and $$n$$ n is the number of bricks. We show that this complexity is optimal.

Two mobile agents represented by points freely moving in the plane and starting at two different positions, have to meet. The meeting, called rendezvous, occurs when agents are at distance at most r of each other and never move after this time, where r is a positive real unknown to them, called the visibility radius. Agents are anonymous and execute the same deterministic algorithm. Each agent has a set of private attributes, some or all of which can differ between agents. These attributes are: the initial position of the agent, its system of coordinates (orientation and chirality), the rate of its clock, its speed when it moves, and the time of its wake-up. If all attributes (except the initial positions) are identical and agents start at distance larger than r then they can never meet, as the distance between them can never change. However, differences between attributes make it sometimes possible to break the symmetry and accomplish rendezvous. Such instances of the rendezvous problem (formalized as lists of attributes), are called feasible.

Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour transmitting in this round. If v listens in a round in which more than one neighbour transmits then v hears noise that is different from any message and different from silence. We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm, we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time $O(n^2σ)$, where n is the number of nodes and σ is the difference between the largest and smallest tag of the configuration. We then ask the question if there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $\mathbb{Z} \times \mathbb{Z}$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time $O(sz)$, where $s$ is the span of the initial field and $z$ is the number of bricks. We show that this complexity is optimal.

Broadcast is one of the fundamental network communication primitives. One node of a network, called the source, has a message that has to be learned by all other nodes. We consider broadcast in radio networks, modeled as simple undirected connected graphs with a distinguished source. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. At the receiving end, a node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour that transmits in this round. If more than one neighbour of a node v transmits in a given round, we say that a collision occurs at v. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbour transmits). We are interested in the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence O(łog n)-bit labels are sufficient for this task in n-node networks. In fact, O(łog Δ)-bit labels, where Δ is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we can get the following additional strong property of our algorithm: there exists a common round in which all nodes know that broadcast has been completed.

Two anonymous mobile agents navigate synchronously in an anonymous graph and have to meet at a node, using a deterministic algorithm. This is a symmetry breaking task called rendezvous, equivalent to the fundamental task of leader election between the agents. When is this feasible in a completely anonymous environment? It is known that agents can always meet if their initial positions are nonsymmetric, and that if they are symmetric and agents start simultaneously then rendezvous is impossible. What happens for symmetric initial positions with non-simultaneous start? Can symmetry between the agents be broken by the delay between their starting times? In order to answer these questions, we consider space-time initial configurations (abbreviated by STIC). A STIC is formalized as [(u,v),δ], where u and v are initial nodes of the agents in some graph and δ is a non-negative integer that represents the difference between their starting times. A STIC is feasible if there exists a deterministic algorithm, even dedicated to this particular STIC, which accomplishes rendezvous for it. Our main result is a characterization of all feasible STICs and the design of a universal deterministic algorithm that accomplishes rendezvous for all of them without any a priori knowledge of the agents. Thus, as far as feasibility is concerned, we completely solve the problem of symmetry breaking between two anonymous agents in anonymous graphs. Moreover, we show that such a universal algorithm cannot work for all feasible STICs in time polynomial in the initial distance between the agents.

We consider the fundamental 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, initially situated at some starting node v , has to visit all nodes and stop. The time of the exploration is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori , to explore the graph in a given time, using a deterministic algorithm. Following the paradigm of algorithms with advice , 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. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time? We first determine the minimum size of advice to achieve exploration in polynomial time. We prove that some advice of size log log log n − c , for any constant c , is sufficient for polynomial exploration, and that no advice of size log log log n −ϕ ( n ), where ϕ is any function diverging to infinity, can help to do this. These results hold both for the instance and for the map oracles. On the other side of the spectrum, when advice is large, there are two natural time thresholds: Θ ( n 2 ) for a map oracle, and Θ ( n ) for an instance oracle. This is because, in both cases, these time benchmarks can be achieved with sufficiently large advice (advice of size O ( n log n ) suffices). We show that, with a map oracle, time Θ ( n 2 ) cannot be improved in general, regardless of the size of advice. What is then the smallest advice to achieve time Θ ( n 2 ) with a map oracle? We show that this smallest size of advice is larger than n δ , for any δ < 1/3. For large advice, the situation changes significantly when we allow an instance oracle instead of a map oracle. In this case, advice of size O ( n log n ) is enough to achieve time O ( n ). Is such a large advice needed to achieve linear time? We answer this question affirmatively. Indeed, we show more: with any advice of size o ( n log n ), the time of exploration must be at least n ϵ , for any ϵ < 2, and with any advice of size O ( n ), the time must be Ω( n 2 ). We finally look at Hamiltonian graphs, as for them it is possible to achieve the absolutely optimal exploration time n −1, when sufficiently large advice (of size o ( n log n )) is given by an instance oracle. We show that a map oracle cannot achieve this: regardless of the size of advice, the time of exploration must be Ω( n 2 ), for some Hamiltonian graphs. However, even for the instance oracle, with advice of size o ( n log n ), optimal time n −1 cannot be achieved: Indeed, we show that the time of exploration with such advice must sometimes exceed the optimal time n −1 by a summand n ϵ , for any ϵ < 1.

A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D>0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2 pi whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is Theta(D^2). We show that if all angles given as hints are at most pi, then the cost can be lowered to O(D), which is optimal. If all angles are at most beta, where beta<2 pi is a constant unknown to the agent, then the cost is at most O(D^{2-epsilon}), for some epsilon>0. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2 pi, then we show that cost Theta(D^2) cannot be beaten.

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 positive integers. Each agent 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. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), 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 t 1 and t 2 , whether the distance from the other agent at time t 1 was smaller, equal or larger than at time t 2 . In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than ρ or at distance at least ρ from the other agent, for some real ρ > 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 cost of meeting, defined as the total distance travelled by both agents until the meeting. For the monotone model we show an algorithm achieving meeting at cost 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 ρ (i.e., when they sense each other initially) then meeting can be guaranteed at cost O( ρ log λ), where λ is the larger label, and that this cost cannot be improved in general. Finally we observe that, if agents start at distance αρ, for some constant α > 1 in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting cost is of the same order of magnitude as without any sniffing ability.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node and terminate. This problem is known asgathering. We study deterministic gathering algorithms under the assumption that agents are subject tocrash faultswhich can occur at any time. Two fault scenarios are considered. Amotion faultimmobilizes the agent at a node or inside an edge but leaves intact its memory at the time when the fault occurred. A more severetotal faultimmobilizes the agent as well, but also erases its entire memory. Of course, we cannot require faulty agents to gather. Thus the gathering problem for fault prone agents calls for all fault‐free agents to gather at a single node, and terminate.

Leader election is one of the basic problems in distributed computing. This is a symmetry breaking problem: all nodes of a network must agree on a single node, called the leader. If the nodes of the network have distinct labels, then such an agreement means that all nodes have to output the label of the elected leader. 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.

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader . If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, 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 article, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice , this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice . For a given time τ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ. For most values of τ, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n -node tree of diameter diam ⩽ D . While leader election in time diam can be performed without any advice, for time diam − 1 we give tight upper and lower bounds of Θ(log D ). For time diam − 2 we give tight upper and lower bounds of Θ(log D ) for even values of diam , and tight upper and lower bounds of Θ(log n ) for odd values of diam . Moving to shorter time, in the interval [β · diam , diam − 3] for constant β > 1/2, we prove an upper bound of O ( n log n / D ) and a lower bound of Ω( n / D ), the latter being valid whenever diam is odd or when the time is at most diam − 4. Hence, with the exception of the special case when diam is even and time is exactly diam − 3, our bounds leave only a logarithmic gap in this time interval. Finally, for time α · diam for any constant α < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time Θ( n ).

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, 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 anonymous trees. Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice. For a given time τ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ. For most values of τ, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n-node tree of diameter diam ≤ D. While leader election in time diam can be performed without any advice, for time diam – 1 we give tight upper and lower bounds of ⊝(log D). For time diam – 2 we give tight upper and lower bounds of ⊝(log D) for even values of diam, and tight upper and lower bounds of ⊝(log n) for odd values of diam. Moving to shorter time, in the interval [β · diam, diam – 3] for constant β > 1/2, we prove an upper bound of and a lower bound of , the latter being valid whenever diam is odd or when the time is at most diam – 4. Hence, with the exception of the special case when diam is even and time is exactly diam–3, our bounds leave only a logarithmic gap in this time interval. Finally, for time α · diam for any constant α < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time ⊝(n).

Finding the node with the largest label in a labeled network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which leader election is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In selection, this node has to output 1 and all other nodes have to output 0. In election, the other nodes must additionally learn the largest label (everybody has to know who is the elected leader). Our aim is to compare the difficulty of these two seemingly similar tasks executed under stringent running time constraints. The measure of difficulty is the amount of information that nodes of the network must initially possess, in order to solve the given task in an imposed amount of time. Following the standard framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire graph. The length of this string is called the size of advice. The paradigm of algorithms with advice has a far-reaching importance in the realm of network algorithms. Lower bounds on the size of advice give us impossibility results based strictly on the amount of initial knowledge outlined in a model's description. This more general approach should be contrasted with traditional results that focus on specific kinds of information available to nodes, such as the size, diameter, or maximum node degree. Consider the class of n-node graphs with any diameter diam ≤ D, for some integer D. If time is larger than diam, then both tasks can be solved without advice. For the task of election, we show that if time is smaller than $diam$, then the optimal size of advice is Θ(log n), and if time is exactly diam, then the optimal size of advice is Θ(log D). For the task of selection, the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is O(diamε), for any ε < 1, then the optimal size of advice is Θ(log D), and, if time is Θ(diam) (and at most diam) then this optimal size is Θ(log log D). Thus there is an exponential increase of difficulty (measured by the size of advice) between selection in time O(diamε), for any ε < 1, and selection in time Θ(diam). As for the comparison between election and selection, our results show that, perhaps surprisingly, while for small time, the difficulty of these two tasks on rings is similar, for time Θ(diam) the difficulty of election (measured by the size of advice) is exponentially larger than that of selection.

We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For n-node networks of unknown topology we show a consensus algorithm using O(n 2 ) messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses O(n 3/2 log 2 n) messages on any n-node network and we show that some networks require Ω(n log n) messages to achieve consensus.

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence, we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: \tt team size, in which every agent has to find the total number of agents; \tt leader election, in which all agents have to output the label of a single agent; \tt perfect renaming, in which all agents have to adopt new and different labels from the set $\{1,\dots,k\}$, where $k$ is the number of agents; and \tt gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm, we solve all of these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.

Two mobile agents, starting from different nodes of a 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.

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done.

A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm, and move in synchronous rounds along links of the network. They are silent: They cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this model, devoid of any means of communication between agents, is impossible. Our aim is to solve the exploration problem by giving to agents very restricted local traffic reports . Specifically, an agent that is at a node v in a given round is provided with three bits of information answering the following questions: Am I alone at v ? Did any agent enter v in this round? Did any agent exit v in this round? We show that this small amount of information permits us to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric ; that is, in which there are agents with different views of the network. The algorithm works in polynomial time in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f +2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f +2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f +1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of f +1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2 f +1 good agents when the size of the network is known and for at least 4 f +2 good agents when it is unknown.

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it, but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents.

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.

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, 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 assume that the agents are identical, and move in synchronous rounds. 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 Ω (log n ) bits, even for the line of length n . This lower bound meets a previously known upper bound of O (log n ) bits for rendezvous in arbitrary graphs 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 ℓ 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 ℓ + log log n ) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most ℓ 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 Ω (log ℓ + log log n ) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents, and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents we show that any number of good agents permit to solve the problem for networks of known size. If the size is unknown, then this minimum number is f + 2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f + 2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f + 1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents we give a lower bound of f + 1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side we give deterministic gathering algorithms for at least 2f + 1 good agents when the size of the network is known, and for at least 4f + 2 good agents when it is unknown.

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with k memory bits, we show that optimal rendezvous time is Θ(n+n2/k) in n-node trees. More precisely, if k ≥ c log n, for some constant c, we design agents accomplishing rendezvous in arbitrary trees of unknown size n in time O(n+n2/k), starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time o(n+n2/k), even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a n-node line.

Abstract We consider the task of comparing two rooted trees with port labels. Roots of the trees are joined by an edge and the comparison has to be performed 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 nodes of the other getting 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 versus time trade‐offs. We show that if the automaton hasxbits of memory, wherex≥clogn, for a small constantc, then the optimal time to accomplish the comparison task in the class of trees of size at mostnand of height at mosth> 1 is Θ(h+n/x). For the asynchronous scenario, we study memory versus number of messages trade‐offs. We show that if the automaton hasxbits of memory, wheren≥x≥clogn, then the optimal number of messages to accomplish the comparison task in the class of trees of size at mostnis Θ(n2/x). © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

Abstract Two or more mobile entities, called agents or robots, starting at distinct initial positions, have to meet. This task is known in the literature as rendezvous. Among many alternative assumptions that have been used to study the rendezvous problem, two most significantly influence the methodology appropriate for its solution. The first of these assumptions concerns the environment in which the mobile entities navigate: it can be either a terrain in the plane, or a network modeled as an undirected graph. The second assumption concerns the way in which the entities move: it can be either deterministic or randomized. In this article, we survey results on deterministic rendezvous in networks. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O (log n )-bit memory for all n -node trees. This strengthens the result from Diks et al. [2004], where O (log 2 n )-bit memory was used for tree exploration, and matches the lower bound on memory size proved there. We also extend our O (log n )-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however, the explicit values of port numbers are not available.

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 availability 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(log2n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log2n).

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. Intuitively, the rendezvous problem is more difficult than exploration, as it reduces to the latter, if one of the agents is inert. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically.

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 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. 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 these 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 previously stated agents will eventually get to within an arbitrarily small positive distance from each other.

The aim of rendezvous in a graph is meeting of 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 study the connectivity and diameter of the fault-free part of n-node networks where nodes fail in a random dependent way. 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, causing faults in the given node and its neighbors; faults at distance at most 2 become dependent. We investigate the impact of the spot probability on the connectivity and diameter of the fault-free part of the network. We show a network which has a low diameter with high probability, if p ≤ 1/c log n. We also show that, for constant spot probabilities, most classes of networks do not have their fault-free part connected with high probability. For smaller spot probabilities, connectivity with high probability is supported even by bounded degree networks: the torus supports connectivity with high probability when p ε 1/ω(n1/2), and does not when p ε 1/O(n1/2); a network built of tori is designed, with the same fault-tolerance properties and additionally having low diameter. We show, however, that for networks of degree bounded above by a constant Δ, the fault-free part can not be connected with high probability if p ε 1/O(n1/Δ). This is the first analytic paper which investigates the connectivity and diameter of networks where nodes fail in a random dependent way. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of a tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio, taken over n-node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade-off between the size of advice and the best competitive ratio of a broadcasting algorithm for n-node trees. We establish such a trade-off with an approximation factor of Onε), for an arbitrarily small positive constant ε. This is the first problem for which a trade-off between the amount of provided information and the efficiency of the solution is shown for arbitrary size of advice.

We consider broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time.In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning.

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 oracle size) that has to be available to nodes in order to perform efficient communication.It turns out that the minimum oracle size 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 oracle size permitting the wakeup with a linear number of messages in a n-node network, is Θ (n log n), while the broadcast with a linear number of messages can be achieved with an oracle of size O(n). We also show that the latter oracle size is almost optimal: no oracle 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.

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 independently with fixed probability p<1. 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 on n-node graphs for sufficiently large n) under these scenarios. If only omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For Byzantine faults, almost-safe broadcasting is feasible in the message passing model iff p<1/2 and in the radio model iff p<(1-p)Δ+1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, we give the following upper and lower bounds. Consider an n-node graph G with a given source s, and denote by D the radius of G w.r.t. s (namely, the largest distance from s to any node in G). Then for the message passing model we show that assuming omission faults, the optimal almost-safe broadcasting time is Θ (D + log n). Assuming Byzantine faults, almost-safe broadcasting is possible in time O(D+log α n), for any constant α > 1. For the radio model we show that almost-safe broadcasting in time O (opt + log n) (where opt is the optimal fault-free broadcasting time) is impossible for some graphs, even with omission failures, and we give an almost-safe broadcasting algorithm of time O(opt • log n) for any graph, for both types of failures.

We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http://www.wisdom.weizmann.ac.il/mathusers/oded/p\_bgi.html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (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 these graphs. In view of the randomized algorithm from BGI, running in expected time ${\cal O}(D \log n + \log ^2 n)$ on all n-node graphs of diameter D (cf. also a recent ${\cal O}(D \log (n/D) + \log ^2 n)$-time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication.

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 $\cO$ (n log2n). Our main result is a broadcasting algorithm working in time $\cO$ (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 $\cO$ (n log D) for complete layeredn -node ad hoc radio networks of radius D. The latter complexity is optimal.

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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time O(D log(n/D) + log2 n) in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [14]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time O(D log n + log2 n). For deterministic broadcasting, we show the lower bound Ω(n(log n)/(log (n/D)))) on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time O(n log n), thus shrinking -- for the first time -- the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor.

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.

Abstract We consider distributed deterministic broadcasting in synchronous radio networks. A node receives a message in a given round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know the network topology or even their immediate neighborhood. (Such networks are calledad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their executiontime(number of rounds) and theircost(number of transmissions). We focus our study on the execution time of algorithms which have cost close to minimum. We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the numbernof nodes and the eccentricityDof the source. Our main contribution is proving tight lower bounds on the time of low‐cost broadcasting which show sharp differences between these scenarios. In each case, we also give broadcasting algorithms whose performance matches these lower bounds. © 2002 Wiley Periodicals, Inc.

We consider two interrelated tasks in a synchronous n-node ring: distributed constant coloring and local communication. Every node knows the labels of nodes up to a distance r from it, called the knowledge radius. In distributed constant coloring every node has to assign itself one out of a constant number of colors, so that adjacent nodes get different colors. In local communication every node has to communicate a message to both of its neighbors. We study these problems in two popular communication models: the one-way model in which each node can only either transmit to one neighbor or receive from one neighbor, in any round, and the radio model in which simultaneous receiving from two neighbors results in interference noise. We show that distributed constant coloring and local communication are tightly related and one can be used to accomplish the other. Also in most situations the optimal time is the same for both of them, and it strongly depends on knowledge radius.

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 is situated within range of two nodes transmitting simultaneously it 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.

Abstract We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB), the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB), the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS), all nodes must simultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n‐node network and show networks in which time 2n − o(n) is needed. For ABB, we show algorithms working in time (2 + ϵ)n, for any fixed positive constant ϵ and sufficiently large n. Thus, for both BB and ABB, our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n and a more complicated algorithm which works in time 2.9n. The optimal time of full synchronization remains an open problem. © 2001 John Wiley & Sons, Inc.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v . Apart from that, each node knows only the maximum degree Δ of the network and the number n of nodes. One node of the network, called the source , has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well in at most the same time. We show tradeoffs between knowledge radius and time of deterministic broadcasting, when knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radii 1 and 2. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal, for a given knowledge radius. For knowledge radius 1 we develop a broadcasting algorithm working in time O (min( n , D 2 Δ)), where n is the number of nodes, D is the diameter of the network, and Δ is the maximum degree. We show that for bounded maximum degree Δ this algorithm is asymptotically optimal. For knowledge radius 2 we show how to broadcast in time O ( D Δ log n )) and prove a lower bound Ω( D Δ) on broadcasting time, when D Δ ∈ O ( n ). This lower bound is valid for any constant knowledge radius. For knowledge radius log * n+3 we show how to broadcast in time O ( D Δ). Finally, for any knowledge radius r , we show a broadcasting algorithm working in time O ( D 2 Δ/ r ). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology or the size of the network (unknown network). They execute identical algorithms, apart from a distinguished node, called the source, which starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.

This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually, when the processor wakes up.

We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of Ω(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. 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([logn] + 2k, logn + klog logn/k+1). We also describe a network whose depth nearly matches the lower bound.

A robot has to explore an undirected connected graph by visiting all its nodes and traversing all edges. It may either have a complete a priori knowledge of the graph or only have an unoriented map of it, or, finally, lack any knowledge of the graph. We study the impact of this varying amount of knowledge on exploration performance. It is shown that the best exploration algorithm lacking any knowledge of the graph uses twice as many edge traversals in the worst case as does the best algorithm which has an unoriented map of the graph. On the other hand, the latter uses twice as many edge traversals in the worst case as does the best algorithm having a complete knowledge of the graph. Similar results for the restricted case of exploration algorithms working only for trees are also established. © 2000 John Wiley & Sons, Inc.

We consider the problem of adaptive fault diagnosis in hypercube multiprocessor systems. Processors perform tests on one another and later tests can be scheduled on the basis of previous test results. Fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. The goal is to identify correctly the status of all processors, assuming that the number of faults does not exceed the hypercube dimension. We propose an adaptive diagnosis algorithm whose efficiency is drastically better than that of any previously known strategies. While the worst-case number of tests for any of them exceeds 2/sup n/ log n for an n-dimensional hypercube, our method uses at most 2/sup n/+3n/2 tests in the worst case. We can also modify our algorithm to improve the number of testing rounds. By slightly increasing the number of tests to 2/sup n/+(n+1)/sup 2/ (still a much better performance than 2/sup n/ log n), we can carry out diagnosis in at most 11 rounds in the worst case (as opposed to over n rounds in the best previously known strategy).

We studied adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees,rings, and tori. These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis were found to be significantly smaller than that of classical (one-step) diagnosis. © 1999 John Wiley & Sons, Inc. Networks 34: 206–214, 1999

Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with at most one other processor and during such a transmission each member of a communicating pair learns all values currently known to the other. Two important criteria of efficiency of a gossiping algorithm are its running time and the total number of transmissions. Another measure of quality of a gossiping algorithm is the total number of links used for transmissions. This is the minimum cost of a network which can support the gossiping algorithm. We establish trade-offs between the time T of gossiping and the number C of transmissions and between the time of gossiping and the number L of links used by the algorithm. For a given T we construct gossiping algorithms working in time T, with parameters C and L close to optimal.

We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another; fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. Processors fail with arbitrary probabilities and all failures are independent. The goal is to identify correctly the status of all processors, based on the set of test results. A diagnosis algorithm is optimal if it has the highest probability of correctness (reliability) among all (deterministic) diagnosis algorithms. We give a fast diagnosis algorithm and prove its optimality for arbitrary values of failure probabilities. This is the first time that optimal diagnosis is given for systems without any assumptions on the behavior of faulty processors or on the values of failure probabilities. We also investigate locally optimal diagnosis algorithms: For any set of test results, they return the most probable configuration of faulty and fault-free processors that could yield it. We show a fast diagnosis which is always locally optimal. If all processors have failure probabilities smaller than 1/2 , a locally optimal diagnosis is proved to be optimal. However, if some processors have failure probabilities exceeding 1/2 , a locally optimal diagnosis need not have the highest reliability. We even show examples that it may have arbitrarily small reliability when the number of processors increases, while optimal reliability remains constant.

We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. Since the upper bound k on the number of faults is not always known, it is important to design broadcasting schemes that behave well under any possible number of faults. It turns out that achieving the lowest possible k-vulnerability for all k simultaneously is impossible for some trees. Hence a natural goal is to seek, for any tree T, a broadcasting scheme that simultaneously approximates the lowest possible k-vulnerability for every k, up to a given constant factor c (independent of L). We describe a polynomial algorithm which decides if such a "universally fault-tolerant" broadcasting scheme exists for given T and c, and constructs such a scheme if it exists.

There is given a graph, that models a communication network of a multiprocessor system, and there are tokens (jobs) allocated to nodes of the graph. The task is to distribute the tokens evenly, subject to the constraint that they may be moved only along the edges of the graph. The cost of a distribution strategy is measured as the total number of operations of moving a token along an edge. An algorithm for general graphs is developed, by reduction to a maximum-flow minimum-cost problem, that finds a cost-optimal distribution strategy, given a graph and an initial token allocation. The main result is an algorithm for graphs that are lines of nodes; it finds the distribution strategy in time O(n), for a line of n nodes.

We consider probabilistic diagnosis in multiprocessor systems. Processors can test one another; fault-free processors give correct test results, while faulty testers are unpredictable. Processors fail independently with constant probability p<1/2 and the goal is to identify correctly the status of all processors, based on the set of test results. A diagnosis algorithm is globally optimal if it has the highest probability of correctness among all (deterministic) diagnosis algorithms. We give fast globally optimal diagnosis algorithms for a class of test assignments including complete directed graphs and directed acyclic graphs. This is the first time that globally optimal diagnosis is given in a probabilistic model without any assumptions on the behavior of faulty processors.

No abstract available.

In broadcasting, information originally held in one node of a communication network (called the source) has to be transmitted to all other nodes. In a unit of time, every node which already received the source message can transmit it to one neighbor. in classical broadcasting, the choice of neighbors to be informed by a node and the order in which they are informed may depend on the source. Thus, nodes need to store many transmission lists corresponding to different possible sources and need to know the source to adapt their behavior accordingly. In this paper, we consider a variant of broadcasting in which every node is given a priori a single ordered list containing some of its neighbors. This list is meant to be universal for all possible sources. Upon obtaining the source message, a node transmits it to the neighbors from its list in prescribed order and then stops. This requires substantially less local memory devoted to schedule communication but usually increases broadcasting time. We compare broadcasting time in this and in the classical model and design optimal broadcasting schemes in the universal-list model for trees, rings, and grids. For tori and for complete graphs, we give upper bounds on broadcasting time. © 1996 John Wiley & Sons, Inc.

Broadcasting and gossiping are fundamental tasks in network communication. In broadcasting, or one-to-all communication, information originally held in one node of the network (called the source) must be transmitted to all other nodes. In gossiping, or all-to-all communication, every node holds a message which has to be transmitted to all other nodes. As communication networks grow in size, they become increasingly vulnerable to component failures. Thus, capabilities for fault-tolerant broadcasting and gossiping gain importance. The present paper is a survey of the fast-growing area of research investigating these capabilities. We focus on two most important efficiency measures of broadcasting and gossiping algorithms: running time and number of elementary transmissions required by the communication process. We emphasize the unifying thread in most results from the research in fault-tolerant communication: the trade-offs between efficiency of communication schemes and their fault-tolerance. © 1996 John Wiley & Sons, Inc.

Every node of a communication network has a constant size value which should be made known to all other nodes. Nodes and links fail independently with constant probabilities $p < 1$ and $q < 1$, respectively. Faults are permanent and of crash type: a faulty link does not transmit messages and a faulty node neither sends nor receives messages. In a unit of time, every node can send a packet of information to at most one neighbor and receive a packet from at most one neighbor. The size of each packet does not exceed $b(n)$, where n is the number of nodes. For every $\eta > 0$ we present an algorithm to exchange values between all fault-free nodes of an n-node network in time $O(\frac{n}{b(n)}) + \log n$), with probability exceeding $1 - n^{ - \eta } $, for sufficiently large n. This order of magnitude of running time is optimal.

Abstract We study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability p. They test their neighbors, and a fault‐free processor has probability 1 − q of discovering a fault of a failed neighbor in an individual test. Subsequently, fault‐free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every p ≤ ½, q ≤ 1, we construct systems with O(n log n) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 − n−1. We also show that for some small fixed p and q a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small k, for a system with n processors and kn log n links, the probability of achieving correct diagnosis cannot exceed n−0.5. © 1994 by John Wiley & Sons, Inc.

A mesh-connected processor array is considered in which the links are faulty in the following sense: Each attempt by two neighboring processors to communicate by exchanging messages may fail with some constant probability. A message sent across a link and not delivered is said to be delayed by the link. It is assumed that all the links delay with the same fixed delay probability, independently of each other. The problem of sorting is addressed in this model. It is proved that an $n \times n$ mesh can be sorted in the expected time $O( n )$ with large probability. More precisely, it is shown that there are two constants $c > 0$ and $r > 1$, depending on the delay probability, such that the $n \times n$ mesh is sorted in time $cn + t$ with the probability at least $1 - r^{ - t} $. One specific algorithm is considered, but the analysis shows that many known algorithms could sort in the expected time $O( n )$, after some natural modifications.

Algorithm-based fault tolerance has been proposed as a technique to detect incorrect computations in multiprocessor systems. In algorithm-based fault tolerance, processors produce data elements that are checked by concurrent error detection mechanisms. We investigate the efficacy of this approach for diagnosis of processor faults. Because checks are performed on data elements, the problem of location of data errors must first be solved. We propose a probabilistic model for the faults and errors in a multiprocessor system and use it to evaluate the probabilities of correct error location and fault diagnosis. We investigate the number of checks that are necessary to guarantee error location with high probability. We also give specific check assignments that accomplish this goal. We then consider the problem of fault diagnosis when the locations of erroneous data elements are known. Previous work on fault diagnosis required that the data sets produced by different processors be disjoint. We show, for the first time, that fault diagnosis is possible with high probability, even in systems where processors combine to produce individual data elements.>

Abstract We consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message bits.

Diagnosis of multiprocessor systems in which faulty processors can be replaced by spares or repaired is known as sequential diagnosis. A generalization is considered of classical sequential diagnosis, referred to as diagnosis and repair, under a probabilistic model for the faults and test outcomes in a system. It is shown that correct diagnosis and repair of all faulty processors can be achieved with high probability in a large class of systems including, for example, rings, grids, meshes, tori, and hypercubes. These results show, without restrictive assumptions on the behavior of faulty processors, that correct diagnosis can be achieved in these widely used, low-degree systems when a fixed percentage of the processors in the system are faulty.>

Reconfiguration of memory array using spare rows and spare columns, which has been shown to be a useful technique for yield enhancement of memories, is considered. A clustered failure model that adopts the center-satellite approach of F.J. Meyer and D.K. Pradhan (1989) is proposed and utilized to show that the total number of faulty cells that can be tolerated when clustering occurs is larger than when faults are independent. It is also shown that an optimal solution to the reconfiguration problem can be found in polynomial time for a special case of the clustering model. An efficient approximation algorithm is given for the general case of the probabilistic model assumed. It is shown, through simulation, that the computation time required by this algorithm to repair large arrays containing a significant number of clustered faults is small.>

Abstract We consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p ≤ .29, we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p ≤ .02 and show that no such protocol exists if p ≥ .15.

A variant of the well-known gossip problem is studied. Each of n members of a communication network has a piece of information that should be made known to everybody else. This is to be done by placing a sequence of two-party phone calls along the lines of the network. During each call, the two participants exchange all information they currently have, in a unit of time. It is assumed that calls fail independently with fixed probability $0 < p < 1$ and that no information is exchanged during a failed call. For communication networks of bounded degree, efficient schemes of calls are shown that assure complete communication with probability converging to 1 as n grows. Both the number of calls and the time they use are of minimal order.

The authors consider a comparison-based probabilistic model for multiprocessor fault diagnosis. They study the problem of optimal diagnosis, which is to correctly identify the status (faulty/fault-free) of units in the system, with maximum probability. For some parameter values, this probabilistic model is well approximated by the asymmetric comparison model introduced by M. Malek (1980). For arbitrary systems it is shown that optimal diagnosis in the probabilistic model and in Malek's model is NP-hard. However, the authors construct efficient diagnosis algorithms in the asymmetric comparison model for a class of systems corresponding to bipartite graphs which includes hypercubes, grids, and forests. Furthermore, for ring systems, a linear-time algorithm to perform optimal diagnosis in the probabilistic model is presented.>

In comparison models for system-level fault diagnosis, pairs of units are given the same job and results are compared. The result of such a comparison test can be 0 (match) or 1 (mismatch) and diagnosis is based on the collection of test results. Two such models have been studied, among others: the symmetric model of K.Y. Chwa and S.L. Hakimi (Inform. Control, 49, p.212-38, 1981) and the asymmetric model of M. Malek (Proc. 7th Symp. Comput. Architecture, p.31-35, May 1980). The worst-case optimal testing algorithms for t-fault detection, sequential t-fault diagnosis, and one-step t-fault diagnosis in both models are presented. Nonadaptive and adaptive testing is discussed and it is shown that the latter often enables one to decrease the number of tests.>

Ordered sets are used as a computational model for motion planning problems. Every ordered set has a two-directional point representation using subdivisions. These subdivision points correspond to direction changes along the path of motion.

The author considers two comparison-based diagnosis models previously introduced by K.Y. Chwa et al. (1981) and M. Malek (1980). For each of them, classical t-diagnosability and probabilistic diagnosability based on the maximum likelihood principle are discussed, probabilistic model for comparison testing is introduced. In all considered models, optimal diagnosable systems, i.e., those which use the least possible number of testing links, are designed. These systems have a linear number of links and can be diagnosed in linear time. It is proved, however, that for general systems, both diagnosis and diagnosability problems are NP-hard. The model is used for fault diagnosis of multiprocessor systems.>

Abstract An ideal I defined on a group G is called idempotent if for every A ∈ I, {g ∈ G:Ag−1 ∉ ∈ I} ∈ I. We show that a countably complete idempotent ideal on an abelian group cannot be prime but may have strong saturation properties.