Publikationen

Abstract: We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.

Abstract: This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol Gnn that solves the DSMS problem on overlay trees. We prove that Gnn is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze Gnn for "one-shot" executions, i.e., all requests are invoked simultaneously. We prove that when running Gnn on top of a special family of tree topologies - known as hierarchically well-separated trees (HSTs) - we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies with n processors. From a technical point of view, our main result is that Gnn optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Omega(max {k, log n/log log n}) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.

Abstract: The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network). It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC'03], we obtain a randomized distributed online queueing algorithm with expected competitive ratio O(log n) against an oblivious adversary even on general n-node network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. The main technical result of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees.

Abstract: We study the single-message broadcast problem in dynamic radio networks. We show that the time complexity of the problem depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. More formally, we model communication using the standard graph-based radio network model. To model the dynamic network, we use a variant of the synchronous dynamic graph model introduced in [Kuhn et al., STOC 2010]. For integer parameters T ≥ 1 and k ≥ 1, we call a dynamic graph T-interval k-connected if for every interval of T consecutive rounds, there exists a k-vertex-connected stable subgraph. Further, for an integer parameter τ ≥ 0, we say that the adversary providing the dynamic network is τ-oblivious if for constructing the graph of some round t, the adversary has access to all the randomness (and states) of the algorithm up to round t-τ. As our main result, we show that for any T ≥ 1, any k ≥ 1, and any τ ≥ 1, for a τ-oblivious adversary, there is a distributed algorithm to broadcast a single message in time O((1+n/(k · min{τ,T})) · n log³n ). We further show that even for large interval k-connectivity, efficient broadcast is not possible for the usual adaptive adversaries. For a 1-oblivious adversary, we show that even for any T ≤ (n/k)^(1-ε) (for any constant ε > 0) and for any k ≥ 1, global broadcast in T-interval k-connected networks requires at least Ω(n²/k² log n) time. Further, for a 0-oblivious adversary, broadcast cannot be solved in T-interval k-connected networks as long as T < n-k.

Abstract: We study an online problem in which mobile servers have to be moved in order to efficiently serve a set of online requests. More formally, there is a set of n nodes and a set of k mobile servers that are placed at some of the nodes. Each node can potentially host several servers and the servers can be moved between the nodes. There are requests 1,2, ... that are adversarially issued at nodes one at a time, where a request issued at time t needs to be served at all times t' ≥ t. The cost for serving the requests is a function of the number of servers and requests at the different nodes. The requirements on how to serve the requests are governed by two parameters ɑ ≥ 1 and β ≥ 0. An algorithm needs to guarantee that at all times, the total service cost remains within a multiplicative factor of ɑ and an additive term β of the current optimal service cost. We consider online algorithms for two different minimization objectives. We first consider the natural problem of minimizing the total number of server movements. We show that in this case for every k, the competitive ratio of every deterministic online algorithm needs to be at least Ω(n). Given this negative result, we then extend the minimization objective to also include the current service cost. We give almost tight bounds on the competitive ratio of the online problem where one needs to minimize the sum of the total number of movements and the current service cost. In particular, we show that at the cost of an additional additive term which is roughly linear in k, it is possible to achieve a multiplicative competitive ratio of (1+ε) for every constant ε>0.

Abstract: Resource allocation problems have a large variety of applications in different areas of computer science and operations research. A resource allocation problem seeks to find an optimal allocation of a given type of expensive or limited resource to a set of clients that request the services of the given resource. Some of these problems have an online nature: The requests sequence is not revealed at the beginning, but the requests arrive in an online fashion. An algorithm for an online resource allocation problem must make its decision in response to a newly arriving request in an online fashion, i.e., typically before the subsequent request arrives. Depending on the definition of an online resource allocation problem, it might be allowed to postpone serving a request or to change an already made decision. However in this case, postponing a service and changing a decision come at a cost. In this thesis, we also study online allocation problems in the distributed setting, where in contrast to a centralized system, there is no central unit that controls everything and that is aware of the global state of the system. In addition to the uncertainty about the request sequence arising from the online arrivals, there is also uncertainty at each node in the network because the node does not directly learn about requests arriving in other parts of the network. The nodes of a distributed system therefore need to communicate in order to coordinate their actions and one typically assumes that this communication does not come for free. Two online problems are mainly studied in this thesis. First, we consider the distributed queuing problem as a basic problem that coordinates mutually exclusive access to shared data in distributed systems. We devise a randomized distributed queuing algorithm with an expected competitive ratio of O(log n) on general network topologies. We utilize the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC 2003] that approximates the distances of a general metric space by mapping it to a special family of tree topologies known as hierarchically well-separated trees and often just referred to as HSTs. Our randomized distributed queuing algorithm is obtained by running the ARROW algorithm—a well-known distributed queuing algorithm—on top of the HST that is produced by applying the above embedding to the distances of the underlying network. It is shown that (under some assumptions) the simple and elegant ARROW algorithm outperforms all existing significantly more complicated distributed queueing algorithms. The second main problem that is studied in a centralized setting is the online facility location problem. We introduce the online mobile facility location (OMFL) problem, where the facilities are mobile. A lower bound for the OMFL problem that even holds on uniform metrics is provided. A natural approach to solve the OMFL problem for general metric spaces is to again use the above embedding into an HST and to directly solve the OMFL problem on HSTs. In this thesis, we provide a first step in this direction by solving a generalized version of the OMFL problem on uniform metrics. A simple deterministic online algorithm is devised and a tight analysis is provided for the algorithm. The second step remains as an open question. We further introduce and study another variant of the OMFL problem that is closer to the k-server problem, arguably one of the most influential problem in the area of online algorithms and competitive analysis.

Abstract: This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol GNN that solves the DSMS problem on overlay trees. We prove that GNN is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze GNN for “one-shot” executions, i.e., all requests are invoked simultaneously. We prove that when running GNN on top of a special family of tree topologies — known as hierarchically well-separated trees (HSTs) — we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies with n processors. From a technical point of view, our main result is that GNN optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Omega(max{k, (log n)/(log log n)}) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.