Abstract. In the classical model of network creation games introduced by Fabrikant et al. [ On a network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (PODC‘03), 2003, pp. 347–351], [Formula: see text] players correspond to the nodes of a network buying links of price [Formula: see text] and to the other players with the goal of being well-connected to the resulting network. Still as an open problem, the constant PoA conjecture states that the Price of Anarchy (PoA) is constant for any [Formula: see text]. When tackling this problem distinct behaviors must be taken into the account depending on whether [Formula: see text] has either large or low value. It is known that for [Formula: see text] every ne is a tree and for [Formula: see text] with [Formula: see text] the diameter of networks that are in equilibrium when restricting to deviations that consist only in buying links ( buying equilibria) is at most a constant. These results imply that the PoA is constant for the disjoint union of the two ranges, and thus the constant PoA conjecture seems to be true for most of all the possible values [Formula: see text]. In this paper we study the PoA for the remaining range of [Formula: see text] and we show the following: (i) For [Formula: see text] the PoA is constant by proving that the size of any biconnected component of an equilibrium graph is constant. (ii) For [Formula: see text] we have that [Formula: see text], where [Formula: see text] is the maximum diameter of an equilibrium graph for the same range of [Formula: see text]. Therefore if the constant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter. Towards this direction we find nontrivial buying equilibria of nonconstant diameter when [Formula: see text] and [Formula: see text], exploring new intimate relationships between distance-uniform graphs and buying equilibria.

We provide an algorithm that, given a tree homomorphism H and a regular tree language L represented by a tree automaton, determines whether H(L) is regular. This settles a question that has been open for a long time.

Abstract In this article, we propose several variations of the adversarial queueing model and address stability issues of networks and protocols in those proposed models. The first such variation is thepriority model, which is directed at static network topologies and takes into account the case in which packets can have different priorities. Those priorities are assigned by an adversary at injection time. A second variation, thevariable priority model, is an extension of the priority model in which the adversary may dynamically change the priority of packets at each time step. Two more variations, namely thefailure modeland thereliable model, are proposed to cope with dynamic networks. In the failure and reliable models the adversary controls, under different constraints, the failures that the links of the topology might suffer. Concerning stability of networks in the proposed adversarial models, we show that the set ofuniversally stablenetworks in the adversarial model remains the same in the priority, variable priority, failure, and reliable models. From the point of view of protocols (or queueing policies), we show that several protocols that are universally stable in the adversarial queueing model remain so in the priority, failure, and reliable models. However, we show that thelongest‐in‐system(LIS) protocol, which is universally stable in the adversarial queueing model, is not universally stable in any of the other models we propose. Moreover, we show that no queueing policy is universally stable in the variable priority model. Finally, we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable underfirst‐in‐first‐out(FIFO) and LIS in the failure model (and therefore in the reliable and priority models). This characterization allows us to show that the stability problem under FIFO and LIS in the failure model can be solved in polynomial time. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 23–35 2005

We study universal stability of directed and undirected graphs in the adversarial queuing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path before leaving the system. Restrictions on the allowed packet trajectory provide a way to analyze stability under different packet trajectories. We consider five packet trajectories, two for directed graphs and three for undirected graphs, and provide polynomial time algorithms for testing universal stability when considering each of them. In each case we obtain a different characterization of the universal stability property in terms of a set of forbidden subgraphs. Thus we show that variations of the allowed packet trajectory lead to nonequivalent characterizations. Using those characterizations we are also able to provide polynomial time algorithms for testing stability under the \NTGLIS (Nearest To Go-Longest In System) protocol.

In this paper we study the universal stability of undirected graphs in the adversarial queueing model for packet routing. In this setting, packets must be injected in some edge and have to traverse a path before leaving the system. Restrictions on the allowed types of path that packets must traverse provide different packet models. We consider three natural models, and provide polynomial time algorithms for testing universal stability on them. In the three cases, we obtain a different characterization, in terms of forbidden subgraphs, thus showing that slight variations lead to non-equivalent models.We extend those results to show that universal stability of digraphs, in the case in which packets follow directed paths without repeating vertices, can be decided in polynomial time.All the instability results are obtained for the \NTGLIS protocol. Therefore, the property of universal stability is equivalent to \NTGLIS-stability, in all the cases.