Catálogo de publicaciones - libros

FIFO is the most prominent queueing strategy due to its simplicity and the fact that it only works with local information. Its analysis within the adversarial queueing theory however has shown, that there are networks that are not stable under the FIFO protocol, even at arbitrarily low rate. On the other hand there are networks that are universally stable, i.e., they are stable under every greedy protocol at any rate < 1.

The question as to which networks are stable under the FIFO protocol arises naturally. We offer the first polynomial time algorithm for deciding FIFO stability and simple-path FIFO stability of a directed network, answering an open question posed in [1, 4]. It turns out, that there are networks, that are FIFO stable but not universally stable, hence FIFO is not a worst case protocol in this sense. Our characterization of FIFO stability is constructive and disproves an open characterization in [4].

A distinguishing feature of today’s large-scale platforms for distributed computation and communication, such as the is their predominantly manifested by the fact that a wide variety of are simultaneously running over different distributed hosts. A fundamental question that naturally poses itself for such common settings of heterogeneous distributed systems concerns their ability to preserve or restore an acceptable level of performance during link failures. In this work, we address this question for the specific case of stability properties of greedy, contention-resolution protocols operating over a communication network that suffers from . We focus on the framework, where an adversary controls the rates of packet injections and determines packet paths. In addition, the power of the adversary is enhanced to include the manipulation of . Within this framework, we show that the composition of LIS () with any of SIS (), NTS () and FTG () protocols is unstable at rates > 0 when the network size and the link slowdown take large values. These results represent the current record for instability bounds on injection rate for compositions of greedy protocols over dynamic adversarial models, and also suggest that the potential for instability incurred by the composition of greedy protocols may be than that of some protocol.

Virtual private network design in the hose model deals with the reservation of capacities in a weighted graph such that the terminals in this network can communicate with one another. Each terminal is equipped with an upper bound on the amount of traffic that the terminal can send or receive. The task is to install capacities at minimum cost and to compute paths for each unordered terminal pair such that each valid traffic matrix can be routed along those paths.

In this paper we consider a variant of the virtual private network design problem which generalizes the previously studied symmetric and asymmetric case. In our model the terminal set is partitioned into a number of groups, where terminals of each group do not communicate with each other.

Our main result is a 4.74 approximation algorithm for this problem.

We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-determined destination node under interference constraints which are modeled by an integer ≥ 1, so that any node within distance of a sender cannot receive calls from any other sender. A set of calls which do not interfere with each other is referred to as a round. We give algorithms and lower bounds on the minimum number of rounds for this problem, when the network is a path and the destination node is either at one end or at the center of the path. The algorithms are shown to be optimal for any in the first case, and for 1 ≤ ≤ 4, in the second case.

We investigate the computational hardness of the , the and the type of Range Assignment Problems in ℝ and ℝ. We present new reductions for the Connectivity problem, which are easily adapted to suit the other two problems. All reductions are considerably simpler than the technically quite involved ones used in earlier works on these problems. Using our constructions, we can for the first time prove NP-hardness of these problems for real distance-power gradients > 0 (resp. > 1 for ) in 2-d, and prove APX-hardness of all three problems in 3-d for > 1. Our reductions yield improved lower bounds on the approximation ratios for all problems where APX-hardness was known before already. In particular, we derive the overall first APX-hardness proof for Broadcast. This was an open problem posed in earlier work in this area, as was the question whether (Strong) Connectivity remains NP-hard for = 1. Additionally, we give the first hardness results for so-called well-spread instances.

A is a highly harmful host that disposes of visiting agents upon their arrival. It is known that it is possible for a team of mobile agents to locate a black hole in an asynchronous network if each node is equipped with a of at least (log ) dedicated bits of storage. In this paper, we consider the less powerful : each agent has has available a bounded number of tokens that can be carried, placed on a node or removed from it. All tokens are identical (i.e., indistinguishable) and no other form of communication or coordination is available to the agents. We first of all prove that a team of two agents is sufficient to locate the black hole in finite time even in this weaker coordination model. Furthermore, we prove that this can be accomplished using only ( log ) moves in total, which is optimal, the same as with whiteboards. Finally, we show that to achieve this result the agents need to use only (1) tokens each.

Given a set of requests, we tackle the problem of finding ‘good’ broadcast schedules aiming at the minimization of their total flow time. While running at a fixed speed, in the considered model the server is only allowed to use a certain amount of energy to perform these broadcasts. For this task we present optimal and approximation algorithms, respectively, depending on the number of distinct request types and their transmission lengths. The problem is solvable within polynomial time in the offline setting if the transmission lengths of all request types are identical and the number of distinct request types is constant. The presented algorithm can be generalized to obtain an approximation on instances without identical transmission lengths. Regarding the online version, we show lower and upper bounds on the competitive ratio of an optimal algorithm, including randomized algorithms and algorithms using resource augmentation. These lower and corresponding upper bounds match (at least asymptotically).

In an on-demand data broadcast system, clients make requests for data such as weather forecasts, stock prices and traffic information. The server of the system broadcasts the requested data at some time, and all pending requests on this data are satisfied with this single broadcast. All requests have deadlines. The system can abort the current broadcast for more valuable requests and a preempted broadcast may be restarted from the beginning later. In this paper, we design and analyse online scheduler for scheduling broadcasts in such system. The best previously known upper and lower bounds on the competitive ratio of such schedulers are respectively and , where Δ is the ratio between the length of the longest and shortest data pages. In this paper, we design a scheduler that has competitive ratio . We also improve the lower bound of the problem to , and hence prove that our scheduler is optimal within a constant factor.

We consider the problem of sharing the cost of scheduling jobs on parallel machines among a set of agents. In our setting, each agent owns one job and the cost is given by the makespan of the computed assignment. We focus on -budget-balanced cross-monotonic cost-sharing methods since they guarantee the two substantial mechanism properties -budget-balance and group-strategyproofness and provide fair cost-shares. For identical jobs on related machines and for arbitrary jobs on identical machines, we give (+1)/(2)-budget-balanced cross-monotonic cost-sharing methods and show that this is the best approximation possible. As our major result, we prove that the approximation factor for cross-monotonic cost-sharing methods is unbounded for arbitrary jobs and related machines. We therefore develop a cost-sharing method in the (+1)/(2)-core, a weaker but also fair solution concept. We close with a strategyproof mechanism for the model of arbitrary jobs and related machines that recovers at least 3/5 of the cost. All given solutions can be computed in polynomial time.

|| denotes the problem of scheduling jobs on machines of different speeds such that the makespan is minimized. In the paper two special cases of || are considered: Case I, when –1 machine speeds are equal, and there is only one faster machine; and Case II, when machine speeds are all powers of 2. Case I has been widely studied in the literature, while Case II is significant in an approach to design so called algorithms for the scheduling problem.

We deal with the worst case approximation ratio of the classic list scheduling algorithm ’Longest Processing Time (LPT)’. We provide an analysis of this ratio / for both special cases: For one fast machine, a tight bound of is given. When machine speeds are powers of 2 (2-divisible machines), we show that in the worst case 41/30 </<42/30=1.4.

To our knowledge, the best previous lower bound for both problems was 4/3–, whereas the best known upper bounds were 3/2–1/2 for Case I [6] resp. 3/2 for Case II [10]. For both the lower and the upper bound, the analysis of Case II is a refined version of that of Case I.