We study the wake-up problem in distributed networks, where an adversary awakens a subset of nodes at arbitrary times, and the goal is to wake up all other nodes as quickly as possible by sending only few messages. We prove the following lower bounds:

We consider leader election in clique networks, where n nodes are connected by point-to-point communication links. For the synchronous clique under simultaneous wake-up, i.e., where all nodes start executing the algorithm in round 1, we show a tradeoff between the number of messages and the amount of time. The previous lower bound side of such a tradeoff, in the seminal paper of Afek and Gafni (1991), was shown only assuming adversarial wake-up. Interestingly, our new tradeoff also improves the previous lower bounds for a large part of the spectrum, even under simultaneous wake-up. More specifically, we show that any deterministic algorithm with a message complexity of n f(n) requires Ω((log n) / (log f(n)+1)) rounds, for f(n) > 1. Our result holds even if the node IDs are chosen from a relatively small set of size Θ(n log n), as we are able to avoid using Ramsey's theorem, in contrast to many existing lower bounds for deterministic algorithms. We also give an upper bound that improves over the previously-best tradeoff achieved by the algorithm of Afek and Gafni. Our second contribution for the synchronous clique under simultaneous wake-up is to show that Ω (n log n) is in fact a lower bound on the message complexity that holds for any deterministic algorithm with a termination time T(n) (i.e., any function of n), for a sufficiently large ID space. We complement this result by giving a simple deterministic algorithm that achieves leader election in sublinear time while sending only o(n log n) messages, if the ID space is of at most linear size. We also show that Las Vegas algorithms (that never fail) require Θ(n) messages. This exhibits a gap between Las Vegas and Monte Carlo algorithms.

We consider a scheduling problem for running jobs on machines rented from the cloud. Cloud service providers such as Amazon EC2 and Google Cloud offer machines to rent on demand, and charge the rental usage by a specific interval of time, say at an hourly rate. This pricing model creates an interesting optimization problem called Interval Scheduling with Discrete Charging Units (ISDCU) which assigns jobs to run on the machines with the objective of minimizing the rental cost. In this paper, we study the problem of ISDCU where each machine can process a maximum of g jobs simultaneously. We focus on interval jobs where each job must be assigned to a machine upon its arrival and run for a required processing length. We show that ISDCU is NP-hard even for the case of g = 1. We also show that no deterministic online algorithm can achieve a competitive ratio better than max{2, g} in the non-clairvoyant setting, and better than max{3/2, g} in the clairvoyant setting. Lastly, we develop and analyze several online algorithms, most of which achieve a competitive ratio of O(g).

Regular diurnal patterns are often seen in the workloads of cloud-based online applications. This kind of non-stationary workloads changes the processing demands over time. To run application services with minimum costs, the number of cloud instances can be dynamically adjusted according to the workload variations. Recently, a new type of scheduled instances has emerged in the Infrastructure-as-a-Service market to facilitate such configurations. Scheduled instances can be reserved based on a recurring schedule and they offer price discounts. Meanwhile, cloud vendors require minimum scheduled durations to avoid the overhead of frequently launching and terminating cloud instances. Coupled with traditional on-demand and reserved instances, it becomes more complicated for users to find the optimal combination of these three pricing options to minimize their monetary costs. For the new scheduled instances, not only the number of instances but also their start and stop times have to be decided. In this paper, we develop a fast and effective strategy to solve this problem. Based on the hourly workload distributions, we first compute the optimal number of instances to acquire for each pricing option. Then, we design a scheduling algorithm to arrange the scheduled instances in compliance with the restriction of their scheduled durations. Using the workloads of the LOL online game and the Wikipedia Mobile service as two case studies, the efficacy of our strategy is demonstrated.