A problem arising in the everyday usage of Cloud Computing is "To use or not to use?" and going slightly further it is the question of in when to use own resources and when to use cloud resources. In contrast to using the cloud, own equipment has some initial capital expense (capex) for the purchase of the equipment. On the other hand, its operational cost (opex) in general is supposed to be lower than that of using the cloud - after all, the cloud provider needs to spend comparable energy to maintain the same system and still earn something.

In the formulation of our problem there are three parameters: the cost of buying own equipment, the cost of maintaining it in a unit of time and the cost of renting the cloud for a unit of time. In order to operate with minimal number of constants in calculations, we are going to treat the energy cost in a unit of time of own equipment as a unit cost and express the other two costs in terms of this one

Problem statement

We consider a problem of renting computing resources for the cost of C per time unit or buying them for the cost of B and later using them at a cost of 1 per time unit. We do not know in advance for how long we are going to need these resources and we have to decide how long to rent them and whether and when to buy them.

Lower bound for deterministic algorithm

Similarly as in the classic ski-rental problem, any solution will be defined as the number of round, after which we decide to buy own equipment. We start from short analysis of the off-line solution for any length of the input sequence. Then we consider an example of bad input sequence for every deterministic algorithm. From bounds for all algorithms we have to choose the weakest one in order to obtain the most general one.

The offline algorithm has only to take the decision whether to buy the equipment, or not. If it decides to buy it should do it in the first round, as then it saves C-1 in each round. If the length of the whole computation is D, then the offline algorithm may spend either C*D for always renting the equipment or B+D for buying it in the first round. The decision depends only on which of these two values is smaller and after some transformations we get that one should buy if D > B/(C-1). Notice that we use the assumption that C>1, which expresses the fact that cloud rental in a unit of time is more expensive than using already owned equipment in a unit of time.

For an algorithm that decides to buy the equipment in round K, let us define a malicious input as lasting exactly K rounds. Using the knowledge from previous analysis, let us look at what happens when the algorithm decides to buy below or above the threshold defined in the offline algorithm. If it decides to buy early, i.e., B/(C-1) > K, then its total cost is C(K-1)+B+1, which is larger than C(K-1) + K(C-1) = 2KC - C - K > 2KC - C - B/(C-1), where the cost of the optimal offline solution OPT = CK, thus it is almost 2-competitive. If it buys after the above threshold, then again its cost is ALG = C(K-1)+B+1 but this time OPT = B+K and we compare these two values as follows: ALG = C(K-1) + B +1 = CK - C + B +1 = (C-1)K -C + B + K +1 > B - C + (B + K) = (B+K) - C - K + (B+K) = 2OPT - C - K > 2 OPT - C - K which is again almost 2 competitive.

Deterministic algorithm

In considering the algorithm for cloud rental we assume that time is continuous, i.e., we can stop renting at any time and not after a round of some granularity. Let us consider an obviously imposing algorithm, which decides to buy exactly at the threshold from previous analysis, i.e., as soon time B/(C-1) has passed. Now let K be the number of rounds being the input for this algorithm. If K is smaller than our threshold, then both our algorithm and the optimal offline algorithm will only rent the cloud resources and their cost will be the same. If K is larger than our threshold, then the cost of buying will be the largest in comparison to the cost of renting when the whole process will be the shortest, i.e., exactly at the threshold. In this case OPT = B + K = C*K and ALG = (C-1)*K + B = CK + B + K - C - K = 2OPT - C - K, which matches exactly our results for the lower bounds.

1. Show calculations of the expected value for the randomized algorithm
2. Show that the function from randomized analysis indeed has its maximum equal to 1.75
3. Devise and analyse a randomized algorithm for the cloud-rental problem