We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objective is to redistribute the tokens such that eventually each node has approximately the same number of tokens. We present results for a general class of simple local balancing schemes where the tokens are balanced via matchings. In each round the process averages the tokens of any two matched nodes. If the sum of their tokens is odd, the node to receive the one excess token is selected at random. Our class covers three popular models: in the matching model a new matching is generated randomly in each round, in the balancing circuit model a fixed sequence of matchings is applied periodically, and in the asynchronous model the load is balanced over a randomly chosen edge.

We consider an infinite balls-into-bins process with deletions where in each discrete step \(t\) a coin is tossed as to whether, with probability \(\beta(t)\in(0,1)\), a new ball is allocated using the Greedy[2] strategy (which places the ball in the lower loaded of two bins sampled uniformly at random) or, with remaining probability \(1-\beta(t)\), a ball is deleted from a non-empty bin chosen uniformly at random. Let \(n\) be the number of bins and \(m(t)\) the total load at time \(t\). We are interested in bounding the discrepancy \(x_{\max}(t)-m(t)/n\) (current maximum load relative to current average) and the overload \(x_{\max}(t)-m_{\max}(t)/n\) (current maximum load relative to highest average observed so far).

This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, Vöcking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA ‘13 (ACM, New York), 280–287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311–324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0430 .

In the general pattern formation (GPF) problem, a swarm of simple autonomous, disoriented robots must form a given pattern. The robots' simplicity imply a strong limitation: When the initial configuration is rotationally symmetric, only patterns with a similar symmetry can be formed [Yamashita, Suzyuki; TCS 2010]. The only known algorithm to form large patterns with limited visibility and without memory requires the robots to start in a near-gathering (a swarm of constant diameter) [Hahn et al.; SAND 2024]. However, not only do we not know any near-gathering algorithm guaranteed to preserve symmetry but most natural gathering strategies trivially increase symmetries [Castenow et al.; OPODIS 2022]. Thus, we study near-gathering without changing the swarm's rotational symmetry for disoriented, oblivious robots with limited visibility (the OBLOT-model, see [Flocchini et al.; 2019]). We introduce a technique based on the theory of dynamical systems to analyze how a given algorithm affects symmetry and provide sufficient conditions for symmetry preservation. Until now, it was unknown whether the considered OBLOT-model allows for any non-trivial algorithm that always preserves symmetry. Our first result shows that a variant of Go-to-the-Average always preserves symmetry but may sometimes lead to multiple, unconnected near-gathering clusters. Our second result is a symmetry-preserving near-gathering algorithm that works on swarms with a convex boundary (the outer boundary of the unit disc graph) and without holes (circles of diameter 1 inside the boundary without any robots).

Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, D{ü}rr et al. \cite{DBLP:journals/algorithmica/DurrEMM20} has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine. For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a $(4+ε)$-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a $(2+ε)$-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time $O(poly(n/ε))$. Lastly, we show that our results are essentially optimal by providing matching lower bounds.

Modern mission-critical systems (MCS) are increasingly softwarized and interconnected. As a result, their complexity increased, and so their vulnerability against cyber-attacks. The current adoption of virtualization and service-oriented architectures (SOA) in MCSs provides additional flexibility that can be leveraged to withstand and mitigate attacks, e.g., by moving critical services or data flows. This enables the deployment of strategies for moving target defense (MTD), which allows stripping attackers of their asymmetric advantage from the long reconnaissance of MCSs. However, it is challenging to design MTD strategies, given the diverse threat landscape, resource limitations, and potential degradation in service availability. In this paper, we combine two optimization models to explore feasible service configurations for SOA-based systems and to derive subsequent MTD actions with their time schedule based on an attacker-defender game. Our results indicate that even for challenging and diverse attack scenarios, our models can defend the system by up to 90% of the system operation time with a limited MTD defender budget.

We present a dataset containing source code solutions to algorithmic programming exercises solved by hundreds of Bachelor-level students at the University of Hamburg. These solutions were collected during the winter semesters 2019/2020, 2020/2021 and 2021/2022. The dataset contains a set of solutions to a total of 21 tasks written in Java as well as Python and a total of over 1500 individual solutions. All solutions were submitted through Moodle and the Coderunner plugin and passed a number of test cases (including randomized tests), such that they can be considered as working correctly. All students whose solutions are included in the dataset gave their consent into publishing their solutions. The solutions are pseudonymized with a random solution ID. Included in this paper is a short analysis of the dataset containing statistical data and highlighting a few anomalies (e.g. the number of solutions per task decreases for the last few tasks due to grading rules). We plan to extend the dataset with tasks and solutions from upcoming courses.

We consider a swarm of $n$ robots in \mathbb{R}^d. The robots are oblivious, disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task gathering requires that all robots reach the same, not predefined position. In the related near-gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, gathering can be solved in $\mathcal{O}(n + Δ^2)$ synchronous rounds both in two and three dimensions, where $Δ$ denotes the initial maximal distance of two robots. In this work, we formalize a key property of efficient gathering protocols and use it to define $λ$-contracting protocols. Any such protocol gathers $n$ robots in the $d$-dimensional space in $\mathcal{O}(Δ^2)$ synchronous rounds. Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside of the local convex hulls of their neighborhoods -- $λ$-contracting protocols have this property -- requires $Ω(Δ^2)$ rounds to gather all robots. Among others, we prove that the $d$-dimensional generalization of the GtC-protocol is $λ$-contracting. Remarkably, our improved and generalized runtime bound is independent of $n$ and $d$. The independence of $d$ answers an open research question. We also introduce an approach to make any $λ$-contracting protocol collisionfree to solve near-gathering. The resulting protocols maintain the runtime of $Θ(Δ^2)$ and work even in the semi-synchronous model.

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1.

We consider the plurality consensus problem for n agents. Initially, each agent has one of k opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a configuration in which all agents agree on the same opinion. If there is initially a sufficiently large bias towards some opinions one of them should prevail. In this paper we consider a synchronized variant of the undecided state dynamics where the agents use so-called phase clocks. The phase clocks divide the time in overlapping phases. Each phase consists of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics both in the sequential population model and the parallel gossip model. In the population model agents interact in randomly chosen pairs, one pair per time step. The runtime is measured in parallel time (number of interactions divided by n). We show that our protocol reaches consensus (w.h.p.) in O(log2 n) parallel time, providing the first polylogarithmic result for k > 2 (w.h.p.) in this model. If there is an initial bias of , then (w.h.p.) that opinion wins. The gossip model assumes parallel rounds. During each round every agent is allowed to communicate with one randomly chosen agent. Here it is known that consensus can be reached fast (in polylogarithmic time) if there is a bias of order towards one opinion [Ghaffari and Parter, PODC'16; Berenbrink et al., ICALP'16]. Without any assumption on the bias, fast consensus has only been shown for k = 2 for the unsynchronized version of the undecided state dynamics [Clementi et al., MFCS'18]. To account for the yet unsolved general case, we show that the synchronized variant of the undecided state dynamics reaches consensus (w.h.p.) in time O(log2 n) for every initial configuration. Again, we guarantee that if there is an initial bias of , then (w.h.p.) that opinion wins. A simple extension of our protocol in the gossip model yields a dynamics that does not depend on n or k, is anonymous, and has (w.h.p.) runtime O(log2 n). This solves an open problem formulated by Becchetti et al. [Distributed Computing, 2017].

Consider a set P of points in the unit square U = [1,0), one of them being the origin. For each point p ∈ P you may draw an axis-aligned rectangle in U with its lower-left corner being p. What is the maximum area such rectangles can cover without overlapping each other? Freedman posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [Adrian Dumitrescu and Csaba D. Tóth, 2015] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm’s coverage to 39%, we extinguish the hope of reaching 50% by giving points for which its coverage stays below 43.3%. Our analysis studies the algorithm’s average and worst-case density of so-called tiles, which represent the staircase polygons in which a point can freely choose its maximum-area rectangle. Our approach is comparatively general and may potentially help in analyzing related algorithms.

We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are$n$bins (servers) with a limited capacity (buffer) of size$c=c(n)\in \mathbb{N}$. Given a fixed arrival rate$\lambda=\lambda(n)\in(0,1)$, in every round$\lambda n$new balls (requests) are generated. Together with possible leftovers from previous rounds, these balls compete to be allocated to the bins. To this end, every ball samples a bin independently and uniformly at random and tries to allocate itself to that bin. Each bin accepts as many balls as possible until its buffer is full, preferring balls of higher age. At the end of the round, every bin deletes the ball it allocated first. We study how the buffer size$c$affects the performance of this process. For this, we analyze both the number of balls competing each round (including the leftovers from previous rounds) as well as the worst-case waiting time of individual balls. We show that (i) the number of competing balls is at any (even exponentially large) time bounded with high probability by$4 \cdot c^{-1} \cdot \ln (1/(1-\lambda))\cdot n + \mathrm{O}(c \cdot n)$and that (ii) the waiting time of a given ball is with high probability at most$(4 \cdot \ln (1/(1-\lambda)))/ (c \cdot (1-1/e)) + \log \log n + \mathrm{O}(c)$. These results indicate a sweet spot for the choice of$c$around$c = \Theta(\sqrt{\log (1/(1-\lambda))})$. Compared to a related process with infinite capacity [Berenbrink et al., PODC'16], for constant$\lambda$the waiting time is reduced from$\mathrm{O}(\log n)$to$\mathrm{O}(\log \log n)$. Even for large$\lambda \approx 1 - 1/n$we reduce the waiting time from$\mathrm{O}(\log n)$to$\mathrm{O}(\sqrt{\log n})$.

Abstract Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. Recently, a significant amount of work has been devoted to the study of the time and space complexity of leader election in this model. It is known that Ω (log log n) states per agent are needed to elect a leader in fewer than [EQUATION] expected interactions (Alistarh et al.; SODA'17) and that Ω (n log n) expected interactions are required regardless of the number of states (Sudo and Masuzawa; 2020). On the positive side, Gasieniec and Stachowiak (SODA'18) gave the first protocol that uses an optimal Θ(log log n) number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n log n log log n) (Gasieniec et al.; SPAA'19). We provide the first leader election population protocol that is both time and space optimal, electing a leader in O(n log n) expected interactions and using Θ(log log n) states per agent. A novel component is a simple protocol that efficiently selects a small set of agents of polylog n size, given O(n∈) initially selected agents. Unlike existing approaches, which monotonically shrink this initially selected set, we first grow it in a controlled way to a specific size before shrinking it again.

Robot coordination problems deal with systems consisting of many autonomous, but simple, mobile agents that try to achieve a common, complex task. The agents' capabilities depend on the exact model and task but are typically very restricted. For example, there is usually no common coordinate system or sense of direction, and agents often have limited sensing capabilities. Among the most basic and well-studied type of tasks are GATHERING problems, in which initially scattered agents must gather at a single point. CHAINFORMATION problems represent another important formation primitive. Here, agents take the role of communication relays that, initially, form a winding chain connecting two base stations. The relays are to move such that the chain becomes straight, allowing for a more energy-efficient communication along the relay chain. Both GATHERING and CHAINFORMATION problems can be described as contracting: starting from an initially scattered formation, they seek to reach a smaller, more efficient structure. A natural complement are extension problems, where agents start in an initially dense formation and seek to reach an extended formation that covers as much area as possible. While there are some results about extension problems if agents move on grids or rings, results in standard discrete and continuous models for the Euclidean plane are scarce. Our work introduces the MAXFORM problem on the Euclidean plane and provides first analytical results for both the discrete and continuous case.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory perform randomly scheduled pairwise interactions. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. A significant amount of work has been devoted to the study of the time and space complexity of this problem. Alistarh et al. (SODA’17) have shown that Ω(loglogn) states per agent are needed in order to elect a leader in fewer than Θ(n 2) expected interactions. Moreover, Ω(nlogn) expected interactions are required regardless of the number of states (Sudo and Masuzawa, 2019). On the upper bound side, Gasieniec and Stachowiak (SODA’18) have presented the first protocol that uses an optimal, Θ(loglogn), number or states and elects a leader in O(n log2 n) expected interactions. This running time was subsequently improved to O(n lognloglogn) (Gasieniec et al., SPAA’19).

Organization and government networks are a target of Advanced Persistent Threats (APTs), i.e., stealthy attackers that infiltrate networks slowly and usually stay undetected for long periods of time. After an attack has been discovered, security administrators have to manually determine which hosts were compromised to clean and restore them. For that, they have to analyze a large number of hosts.

In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.

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 ℓ1and ℓ2be their respective number of tokens. The two nodes exchange tokens such that they have [(ℓ1+ℓ2)/2] and [(ℓ1+ℓ2)/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.

A Coalescing-Branching Random Walk (CoBra) is a natural extension to the standard random walk on a graph. The process starts with one pebble at an arbitrary node. In each round of the process every pebble splits into k pebbles, which are sent to k random neighbors. At the end of the round all pebbles at the same node coalesce into a single pebble. The process is also similar to randomized rumor spreading, with each informed node pushing the rumor to k random neighbors each time it receives a copy of the rumor. Besides its mathematical interest, this process is relevant as an information dissemination primitive and a basic model for the spread of epidemics. We study the cover time of CoBra walks, which is the time until each node has seen at least one pebble. Our main result is a bound of O (φ–1 log n) rounds with high probability on the cover time of a CoBra walk with k = 2 on any regular graph with n nodes and conductance φ. This bound improves upon all previous bounds in terms of graph expansion parameters (Dutta et al. [13], Mitzenmacher et al. [27], Cooper et al. [8, 9]). Moreover, we show that for any connected regular graph the cover time is O (n log n) with high probability, independently of the expansion. Both bounds are asymptotically tight. Since our bounds coincide with the worst-case time bounds for Push rumor spreading on regular graphs until all nodes are informed, this raises the question whether CoBra walks and Push rumor spreading perform similarly in general. We answer this negatively by separating the cover time of CoBra walks and the rumor spreading time of Push by a super-polylogarithmic factor on a family of tree-like regular graphs.

A population protocol can be viewed as a sequence of pairwise interactions of $n$ agents (nodes). During one interaction, two agents selected uniformly at random update their states by applying a specified deterministic transition function. In a long run, the whole system should stabilize at the correct output property. The main performance objectives in designing population protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem which uses $Θ(\log n)$ states (per agent) and stabilizes in $O(\log^{5/3} n)$ parallel time (i.e., $O(n\log^{5/3} n)$ interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that any exact-majority protocol which stabilizes in expected $O(n^{1-ε})$ parallel time, for any constant $ε> 0$, requires $Ω(\log n)$ states. They also showed an $O(\log^2 n)$-time protocol with $O(\log n)$ states, the currently fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on $O(\log n)$ phases and requires that all nodes are well synchronized within each phase, leading naturally to upper bounds of the order of at least $\log^2 n$ because of $Θ(\log n)$ synchronization time per phase. We show how this framework can be tightened with {\em weak synchronization} to break the $O(\log^2 n)$ upper bound of previous protocols.

We consider the following balls-into-bins process with n bins and m balls: Each ball is equipped with a mutually independent exponential clock of rate 1. Whenever a ball's clock rings, the ball samples a random bin and moves there if the number of balls in the sampled bin is smaller than in its current bin. This simple process models a typical load balancing problem where users (balls) seek a selfish improvement of their assignment to resources (bins). From a game theoretic perspective, this is a randomized approach to the well-known KP model [1], while it is known as Randomized Local Search (RLS) in load balancing literature [2], [3]. Up to now, the best bound on the expected time to reach perfect balance was O((ln n)2+ln(n).n2/m) due to [3]. We improve this to an asymptotically tight O(ln(n)+n2/m). Our analysis is based on the crucial observation that performing destructive moves (reversals of RLS moves) cannot decrease the balancing time. This allows us to simplify problem instances and to ignore “inconvenient moves” in the analysis.

We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.

We consider a scheduling problem on m identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20%, 15%, and 65%) and adjust this distribution over time. Each job j comes with a size pj ∈ R and a resource requirement rj > 0. Jobs do not benefit when receiving a share larger than rj of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan. Our main result is an efficient approximation algorithm which achieves an approximation ratio of 2 + 1/(m-2). It can be improved to an (asymptotic) ratio of 1 + 1/(m-1) if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certain types of networks the nodes can be quite cheap and simple, and hence one seeks protocols that are not only time efficient but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are, with probability 1-o(1), both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters.

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication is realized via the Gossip (or random phone call) model. A major open question has been whether there is a protocol for the complete graph that converges (w.h.p.) in polylogarithmic time and uses only polylogarithmic memory per node (local memory). We answer this question affirmatively. We propose two protocols that need only mild assumptions on the bias in favor of the plurality. As an example of our results, consider the complete graph and an arbitrarily small constant multiplicative bias in favor of the plurality. Our first protocol achieves plurality consensus in O(log(k)*log(log(n))) rounds using log(k) + Theta(log(log(k))) bits of local memory. Our second protocol achieves plurality consensus in O(log(n)*log(log(n))) rounds using only log(k) + 4 bits of local memory. This disproves a conjecture by Becchetti et al. (SODA'15) implying that any protocol with local memory log(k)+O(1) has worst-case runtime Omega(k). We provide similar bounds for much weaker bias assumptions. At the heart of our protocols lies an undecided state, an idea introduced by Angluin et al. (Distributed Computing'08).

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast to d=1).

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement rj∈[0,1]. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.

We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.

In this paper we introduce “On-The-Fly Computing”, our vision of future IT services that will be provided by assembling modular software components available on world-wide markets. After suitable components have been found, they are automatically integrated, configured and brought to execution in an On-The-Fly Compute Center. We envision that these future compute centers will continue to leverage three current trends in large scale computing which are an increasing amount of parallel processing, a trend to use heterogeneous computing resources, and — in the light of rising energy cost — energy-efficiency as a primary goal in the design and operation of computing systems. In this paper, we point out three research challenges and our current work in these areas.

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors. Moreover, we provide a tight analysis of the algorithm's competitiveness. Our results generalize and improve upon work by Chan et al. [10], which considers a single speed-scalable processor. Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.

We consider a scenario in which n mobile robots with a limited viewing range are distributed arbitrarily in the plane, such that the visibility graph of the robots is connected. The goal is to gather the robots in one (not predefined) point. Each robot may base its decision where to move only on the current relative positions of the robots which are in its viewing range. That is, besides having a limited viewing range, the robots are oblivious (they do not use information from the past), they do not have IDs, and they do not have a common sense of direction. On the other hand side, we assume that they are points, i.e., have no extent.

Consider two far apart base stations connected by an arbitrarily winding chain of n relay robots to transfer messages between them. Each relay acts autonomously, has a limited communication range, and knows only a small, local part of its environment.