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.

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.

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.

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.

We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 ≤ ρ ≤ 1 and burstiness σ ≤ 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(ℓ d1/ℓ + σ) space suffice, where d is the number of distinct destinations and ℓ=⌋1/ρ⌊ and we show that Ω(1 over ℓ d1/ℓ + σ) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d' + σ where d' is the maximum number of destinations on any root-leaf path.

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.

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.

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.