Abstract: We present three new coordination mechanisms for schedul-
ing n sel¯sh jobs on m unrelated machines. A coordination
mechanism aims to mitigate the impact of sel¯shness of jobs
on the e±ciency of schedules by de¯ning a local schedul-
ing policy on each machine. The scheduling policies induce
a game among the jobs and each job prefers to be sched-
uled on a machine so that its completion time is minimum
given the assignments of the other jobs. We consider the
maximum completion time among all jobs as the measure
of the e±ciency of schedules. The approximation ratio of
a coordination mechanism quanti¯es the e±ciency of pure
Nash equilibria (price of anarchy) of the induced game. Our
mechanisms are deterministic, local, and preemptive in the
sense that the scheduling policy does not necessarily process
the jobs in an uninterrupted way and may introduce some
idle time. Our ¯rst coordination mechanism has approxima-
tion ratio O(logm) and always guarantees that the induced
game has pure Nash equilibria to which the system con-
verges in at most n rounds. This result improves a recent
bound of O(log2 m) due to Azar, Jain, and Mirrokni and,
similarly to their mechanism, our mechanism uses a global
ordering of the jobs according to their distinct IDs. Next
we study the intriguing scenario where jobs are anonymous,
i.e., they have no IDs. In this case, coordination mechanisms
can only distinguish between jobs that have diffeerent load
characteristics. Our second mechanism handles anonymous
jobs and has approximation ratio O
¡ logm
log logm
¢
although the
game induced is not a potential game and, hence, the exis-
tence of pure Nash equilibria is not guaranteed by potential
function arguments. However, it provides evidence that the
known lower bounds for non-preemptive coordination mech-
anisms could be beaten using preemptive scheduling poli-
cies. Our third coordination mechanism also handles anony-
mous jobs and has a nice \cost-revealing" potential func-
tion. Besides in proving the existence of equilibria, we use
this potential function in order to upper-bound the price of stability of the induced game by O(logm), the price of an-
archy by O(log2 m), and the convergence time to O(log2 m)-
approximate assignments by a polynomial number of best-
response moves. Our third coordination mechanism is the
¯rst that handles anonymous jobs and simultaneously guar-
antees that the induced game is a potential game and has
bounded price of anarchy.
Abstract: In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C>1 under a (w,\~{n})-adversary. We obtain the following results:
• Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention–resolution results in instability at rates View the MathML source and for large enough values of C.
• The combination of dynamically changing link capacities with compositions of contention–resolution protocols on network queues suffices for similar instabilitybounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates View the MathML source for large enough values of C.
• The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instabilitybounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.
Abstract: We study the performance of approximate Nash equilibria for congestion
games with polynomial latency functions. We consider how much the price of anarchy
worsens and how much the price of stability improves as a function of the
approximation factor . We give tight bounds for the price of anarchy of atomic and
non-atomic congestion games and for the price of stability of non-atomic congestion
games. For the price of stability of atomic congestion games we give non-tight
bounds for linear latencies. Our results not only encompass and generalize the existing
results of exact equilibria to -Nash equilibria, but they also provide a unified
approach which reveals the common threads of the atomic and non-atomic price of
anarchy results. By expanding the spectrum, we also cast the existing results in a new
light.
Abstract: In this work, we study the impact of dynamically changing
link capacities on the delay bounds of LIS (Longest-In-
System) and SIS (Shortest-In-System) protocols on specific
networks (that can be modelled as Directed Acyclic Graphs-
DAGs) and stabilitybounds of greedy contention-resolution
protocols running on arbitrary networks under the Adversarial
Queueing Theory. Especially, we consider the model
of dynamic capacities, where each link capacity may take
on integer values from [1, C] withC > 1, under a (w, \~{n})-
adversary.
Abstract: In this work, we study the impact of dynamically changing link capacities on the delay bounds of LIS (Longest-In-System) and SIS (Shortest-In-System) protocols on specific networks (that can be modelled as Directed Acyclic Graphs (DAGs)) and stabilitybounds of greedy contention–resolution protocols running on arbitrary networks under the Adversarial Queueing Theory. Especially, we consider the model of dynamic capacities, where each link capacity may take on integer values from [1,C] with C>1, under a (w,\~{n})-adversary. We show that the packet delay on DAGs for LIS is upper bounded by O(iw\~{n}C) and lower bounded by {\`U}(iw\~{n}C) where i is the level of a node in a DAG (the length of the longest path leading to node v when nodes are ordered by the topological order induced by the graph). In a similar way, we show that the performance of SIS on DAGs is lower bounded by {\`U}(iw\~{n}C), while the existence of a polynomial upper bound for packet delay on DAGs when SIS is used for contention–resolution remains an open problem. We prove that every queueing network running a greedy contention–resolution protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length of the longest path in the network.
Abstract: In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≰ 0.1428. We generalize this results to show upper bound for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≱ 0.8357, improving the previous known bounds of [2].
Abstract: A packet-switching network is stable if the number of packets in the network remains bounded at all times. A very natural question that arises in the context of stability properties of such networks is how network structure precisely affects these properties. In this work we embark on a systematic study of this question in the context of Adversarial Queueing Theory, which assumes that packets are adversarially injected into the network. We consider size, diameter, maximum vertex degree, minimum number of disjoint paths that cover all edges of the network and network subgraphs as crucial structural parameters of the network, and we present a comprehensive collection of structural results, in the form of stability and instabilitybounds on injection rate of the adversary for various greedy protocols: —Increasing the size of a network may result in dropping its instability bound. This is shown through a novel, yet simple and natural, combinatorial construction of a size-parameterized network on which certain compositions of greedy protocols are running. The convergence of the drop to 0.5 is found to be fast with and proportional to the increase in size. —Maintaining the size of a network small may already suffice to drop its instability bound to a substantially low value. This is shown through a construction of a FIFO network with size 22, which becomes unstable at rate 0.704. This represents the current state-of-the-art trade-off between network size and instability bound. —The diameter, maximum vertex degree and minimum number of edge-disjoint paths that cover a network may be used as control parameters for the stability bound of the network. This is shown through an improved analysis of the stability bound of any arbitrary FIFO network, which takes these parameters into account. —How much can network subgraphs that are forbidden for stability affect the instability bound? Through improved combinatorial constructions of networks and executions, we improve the state-of-the-art instability bound induced by certain known forbidden subgraphs on networks running a certain greedy protocol. —Our results shed more light and contribute significantly to a finer understanding of the impact of structural parameters on stability and instability properties of networks.
Abstract: In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, where each link capacity may take on only two possible (integer) values, namely 1 and C>1 under a (w,\~{n})-adversary. We obtain the following results:
• Allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the LIS (Longest-in-System) protocol for contention–resolution results in instability at rates View the MathML source and for large enough values of C.
• The combination of dynamically changing link capacities with compositions of contention–resolution protocols on network queues suffices for similar instabilitybounds: The composition of LIS with any of SIS (Shortest-in-System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) protocols is unstable at rates View the MathML source for large enough values of C.
• The instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instabilitybounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.
Abstract: We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it selects to run its job to the server among its permissible servers having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness.
We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy and price of stability of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions.
Abstract: We study the load balancing problem in the context of a set of clients each
wishing to run a job on a server selected among a subset of permissible servers for
the particular client. We consider two different scenarios. In selfish load balancing,
each client is selfish in the sense that it chooses, among its permissible servers, to
run its job on the server having the smallest latency given the assignments of the
jobs of other clients to servers. In online load balancing, clients appear online and,
when a client appears, it has to make an irrevocable decision and assign its job to
one of its permissible servers. Here, we assume that the clients aim to optimize some
global criterion but in an online fashion. A natural local optimization criterion that
can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy
online solutions. The aim of this paper is to determine how much the quality of load
balancing is affected by selfishness and greediness.
We characterize almost completely the impact of selfishness and greediness in
load balancing by presenting new and improved, tight or almost tight bounds on the
price of anarchy of selfish load balancing as well as on the competitiveness of the
greedy algorithm for online load balancing when the objective is to minimize the
total latency of all clients on servers with linear latency functions. In addition, we
prove a tight upper bound on the price of stability of linear congestion games.