Perlen der Theoretischen Informatik: Themen
Überblick
- Online Service with Delay
- Plurality Consensus
- Balanced Allocations
- Minimum Manhattan Network
- Interval Scheduling
- The space complexity of approximating the frequency moments
- Randomized Rumor Spreading
- Simple and Efficient Leader Election
- Load Balancing
- The Small-World Phenomenon
- Balls into Bins
- Clock Synchronization with 3-Bit Messages
- Formal Properties of Petri’s Cycloid Systems
- PTAS for Euclidean TSP
1. Online Service with Delay
In the Online Service with Delay (OSD) problem, there is a metric space consisting of n points and one server located in this metric space. Over time, requests appear in the metric space and must be served. To serve such a request, the server must be moved in the metric space from its current location to the location where the request resides. This movement incurs cost Cm proportional to the distance the server is moved. It is not required that a request is served immediately. Instead, serving may be delayed, e.g., when there is reason to belief more requests will appear in the near future near the current location of the server. However, dallying incurs additional cost Cw proportional to the waiting time of a given request. The overall goal is to serve all requests while minimizing the sum the movement cost Cm and the waiting cost Cw. This must be done without prior knowledge of how many and which requests arrive.
This abstract problem has many real world applications, ranging from the coordination of a technician (the server) who is called into customer homes on demand (requests) to modeling the movement, cost, and wear of a hard disk head.
The goal of this seminar thesis is to present and explain the formal model and known results for the OSD problem in general as well as the mathematical correctness and quality proofs for the special case where the metric space is a line.
Literatur
M. Bienkowski, A. Kraska, P. Schmidt - Online Service with Delay on a Line [2018]
Y. Azar, A. Ganesh, R. Ge, D. Panigrahi - Online Service with Delay [2017]
Betreuung
Peter Kling
2. Plurality Consensus
The Consensus problem is defined in the following manner. We are given n nodes( processors). Each has an opinion( a color) out of k possible opinions( colors). Our aim is to reach a state in which all nodes support the same opinion. To do this, time is divided into rounds. Every node accomplishes one specific update rule based on the round. In our problem, we are utilizing two simple randomized update rules. In the following, we present a brief summery of recent works realted to our problem.
- Stabilizing consensus with the power of two choices: A simple randomized update rule named median−rule is used such that with high probability in O(log n) time the goal is reached. The update rule is defined in this course. Every node in any round chooses two of its neighbours uniformly at random and request their values. This node then updates its value to the median of these values and its value.
- A tight analysis of the parallel Undecided State Dynamics with two Colors: The complete graph and the two colored case is examined. Their update rule is the same per round. Every node, either with undecieded or real color, chooses uniformly at random one neighbour. If this node selects a colored node with different color it turns to undecided otherwise it keeps its color. They show, starting from any initiall configuration, the process reaches a monochromatic configuration within O(log n) rounds, with high probability.
- Efficient plurality consensus, or: the benefits of the cleaning up from time to time. This paper is the most related work to our problem. We use the same updates rules. The underlying network is a complete graph. Time is partitioned into phases and each of those consists of 5 + 2 log k rounds (k is the number of initial colors). First round of a phase is the clean-up round and the rest are decision-accomolation rounds. In former, every color loses a fraction of its support such as they will be added to the undecided nodes and during the latter, reamining undecieded nodes takes each color with probability corredponded to the fraction of nodes having that color. Every remaining color increases its support while undecided nodes adopt this color. They proved, in O(log k. log log n) the goal is reached when there is a mild assumption on the bias.
Literatur
B. Doerr, L. Goldberg, L. Minder, T. Sauerwald, C. Scheideler - Stabilizing Consensus With the Power of Two Choices [2011]
A. Clementi, M. Ghaffari, L. Gualà, E. Natale, F. Pasquale, G. Scornavacca [2018]
P. Berenbrink, T. Friedetzky, G. Giakkoupis, P. Kling - Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time [2016]
Betreuung
Hamed Hosseinpour
3. Balanced Allocations
Balls and Bins are a common model to examine load balancing on uniform servers without a centralized controller. Assume, we distribute m balls over n bins by placing each ball into a bin selected uniformly at random. The strategy GREEDY[d] sequentially places each ball in the least loaded of d bins chosen uniformly at random. For d=1 and m=n, the load of the fullest bin is (1+o(1)) ln(n) / ln(ln(n)) with high probability. For d=2 the highest load is reduced to ln(ln(n)) / ln(2) + O(1).
- Self-stabilizing Balls & Bins in Batches: This paper adapts the model to an infinite process. In each round, every non-empty bin removes one of its balls. Afterwards, up to n new balls (with an expected number < n) are generated and distributed in parallel using the GREEDY[d] strategy for every ball. The bounds for the system loads derived for d=1 and d=2 are invariant of the number of rounds and exhibit the same exponential decrease for d=2.
- The (1+beta)-Choice Process and Weighted Balls-into-Bins: This paper examines a strategy closely related to GREEDY[d] for m balls thrown sequentially into n bins. With a fixed probability each ball is placed according to either GREEDY[1] or GREEDY[2]. The model is further extended to the weighted case, where the load of a bin is defined by the sum of the weights of its balls. The load difference between the fullest bin and the average is shown to be independent of m for a large class of weight distributions.
Literatur
P. Berenbrink, T. Friedetzky, P. Kling, F. Mallmann-Trenn, L. Nagel, C. Wastell - Self-stabilizing Balls & Bins in Batches [2016]
Y. Peres, K. Talwar, U. Wieder - The (1 + β)-Choice Process and Weighted Balls-into-Bins [2010]
Betreuung
Christopher Hahn
4. Minimum Manhattan Network
Given a set T of n points in R2, a Manhattan Network G is a network with all its edges horizontal or vertical segments, such that for all p,q ∈ T, in G there exists a path (named a Manhattan path) of the length exactly the Manhattan distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of the
minimum length, i.e., the total length of the segments of the network is to be minimized. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves the 2-approximation algorithm with time complexity O(n2). Moreover, compared with other 2-approximation algorithms employing linear programming or dynamic programming technique, it was first discovered that only greedy strategy suffices to get 2-approximation network.
Literatur
Z. Guo, H. Sun, H. Zhu - Greedy Construction of 2-Approximation Minimum Manhattan Network [2008]
Betreuung
Christoph Damerius
5. Interval Scheduling
We consider a general interval scheduling problem. The problem is a natural generalization of finding a maximum independent set in an interval graph. We show that, unless P=NP, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the other hand, we present a simple greedy algorithm that delivers a solution with a value of at least 1/2 times the value of an optimal solution. Finally, we investigate the quality of an LP-relaxation of a formulation for the problem, by establishing an upper bound on the ratio between the value of the LP-relaxation and the value of an optimal solution.
Literatur
F. Spieksma - On the approximability of an interval scheduling problem [1999]
Betreuung
Christoph Damerius
6. The space complexity of approximating the frequency moments
The frequency moments of a sequence containing mi elements of type i, for 1 ≤ i ≤ n, are the numbers Fk = Σi=1n mki. We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0, F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k ≥ 6 requires nΩ(1) space. Applications to data bases are mentioned as well.
Literatur
N. Alon, Y. Matias, M. Szegedy - The space complexity of approximating the frequency moments (1996)
Betreuung
Felix Biermeier
7. Randomized Rumor Spreading
1. Broadcasting (One-to-all communication): We investigate the class of so-called epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem (arising due to the randomization)is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor from the calling to the called players for O(ln n) rounds needs to transmit the rumor O(n ln n) times in order to ensure that every player finally receives the rumor with high probability.
We investigate whether such a large communication overhead is inherent to epidemic algorithms.
2. Gossipping (All-to-all communication): We consider the gossiping problem in the classical random phone-call model: We are given a complete graph, in which every node has an initial message to be disseminated to all other nodes. In each step every node is allowed to establish a communication channel with a randomly chosen neighbour. It is possible to design a randomized procedure performing O(n log log n) transmissions that accomplishes broadcasting in time O(log n), with high probability. We provide a lower bound argument that proves Ω(n log n) message complexity for any O(log n)-time randomized gossiping algorithm, with probability 1-o(1). This should be seen as a separation result between broadcasting and gossiping in the random phone-call model.
Literatur
R. Karp, C. Schindelhauer, S. Shenker, B. Vocking - Randomized Rumor Spreading [2000]
Betreuung
Petra Berenbrink
8. Simple and Efficient Leader Election
We provide a simple and efficient population protocol for leader election that uses O(log n) states and elects exactly one leader in O(n · (log n)2 ) interactions with high probability and in expectation. Our analysis is simple and based on fundamental stochastic arguments. Our protocol combines the tournament based leader elimination by Alistarh and Gelashvili, ICALP’15, with the synthetic coin introduced by Alistarh et al., SODA’17.
Literatur
P. Berenbrink, D. Kaaser, P. Kling, L. Otterbach - Simple and Efficient Leader Election [2018]
Betreuung
Dominik Kaaser
9. Load Balancing
We consider the following load balancing process for m tokens distributed arbitrarily among n nodes connected by a complete graph. In each time step a pair of nodes is selected uniformly at random. Let l1 and l2 be their respective number of tokens. The two nodes exchange tokens such that they have ceil((l1 + l2/2)) and floor((l1 + l2/2)) tokens, respectively. We provide a simple analysis showing that this process reaches almost perfect balance within O(n log n + n log ∆) steps with high probability, where ∆ is the maximal initial load difference between any two nodes. This bound is asymptotically tight.
Literatur
P. Berenbrink, T. Friedetzky, D. Kaaser, P. Kling - Tight & Simple Load Balancing [2019]
Betreuung
Dominik Kaaser
10. The Small-World Phenomenon
Long a matter of folklore, the “small-world phenomenon” — the principle that we are all linked by short chains of acquaintances — was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960’s. This work was among the first to make the phenomenon quantitative, allowing people to speak of the “six degrees of separation” between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web.
But existing models are insufficient to explain the striking algorithmic component of Milgram’s original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. Although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. We then define an infinite family of network models that naturally generalizes the Watts-Strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. More generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.
Literatur
J. Kleinberg - The Small-World Phenomenon: An Algorithmic Perspective [2000]
Betreuung
Petra Berenbrink
11. Balls into Bins
Suppose we sequentially throw m balls into n bins. It is a natural question to ask for the maximum number of balls in any bin. In this paper we shall derive sharp upper and lower bounds which are reached with high probability. We prove bounds for all values of m(n) ≥ n/polylog(n) by using the simple and well-known method of the first and second moment.
Literatur
M. Raab, A. Steger -Balls into Bins - A Simple and Tight Analysis [1998]
Betreuung
Dominik Kaaser
12. Clock Synchronization with 3-Bit Messages
This paper is motivated by the aspiration to identify the weakest computational models that allow for efficient, robust distributed computation. We focus on one of the most fundamental building-blocks in distributed computing, namely, Broadcast. In this problem, a unique source agent s needs to disseminate a bit b to the rest of the population. To account for unpredictability issues that may result from uncoordinated executions, we consider a self-stabilizing setting, in which a correct configuration must be reached eventually, despite processors starting the execution with arbitrary initial states (that do not violate the requirement for the existence of a unique source). Similarly to many works on broadcast, we consider a synchronous communication model on a complete anonymous network, in which in each round, each agent can extract information from two other agents, chosen uniformly at random. Our focus is on identifying the smallest message size that is required in order to achieve fast selfstabilizing broadcast. We first observe that with an extra bit added to the message-size and a small additive penalty to the running time, the self-stabilizing broadcast problem can be reduced to a self-stabilizing clock-synchronization problem, where agents aim to synchronize their clocks modulo some integer T. Our main technical contribution lies in solving the latter problem in poly-logarithmic time using only 3 bits per interaction. This allows for a self-stabilizing broadcast protocol that uses only 4 bits per interaction and converges in O~(log n) time.
Literatur
L. Boczkowski, A. Korman, E. Natale - Brief Announcement: Self-Stabilizing Clock Synchronization with 3-bit Messages [2016]
L. Boczkowski, A. Korman, E. Natale - Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits [2016]
Betreuung
Dominik Kaaser
13. Formal Properties of Petri’s Cycloid Systems
Cycloids are particular Petri nets for modelling processes of actions or events. They belong to the fundaments of Petri’s general systems theory and have very different interpretations, ranging from Einstein’s relativity theory to elementary information processing gates. Despite their simple definitions, their properties are still not completely understood. This contribution provides for the first time a formal definition together with new results concerning their structure. Cycloids are proved to be live and safe. It is shown that the minimal length of a cycle is the length of a local basic circuit, possibly decreased by an integer multiple of the number of semi-active transitions. These results allow to find the defining parameters of a cycloid from the static properties of the net system. Similar results are obtained for degenerate cycloids.
Literatur
R. Valk - Formal Properties of Petri’s Cycloid Systems [2019]
Betreuung
Daniel Moldt
14. PTAS for Euclidean TSP
We present a polynomial time approximation scheme for Euclidean TSP in /spl Rfr//sup 2/. Given any n nodes in the plane and /spl epsiv/>0, the scheme finds a (1+/spl epsiv/)-approximation to the optimum traveling salesman tour in time n/sup 0(1//spl epsiv/)/. When the nodes are in /spl Rfr//sup d/, the running time increases to n(O/spl tilde/(log/sup d-2/n)//spl epsiv//sup d-1/) The previous best approximation algorithm for the problem (due to Christofides (1976)) achieves a 3/2-approximation in polynomial time. We also give similar approximation schemes for a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k, spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as l/sub p/ for p/spl ges/1 or other Minkowski norms).
Literatur
S. Arora - Polynomial time approximation schemes for Euclidean TSP and other geometric problems [1996]
Betreuung
Peter Kling