  A renewal system divides the slotted timeline into back to back time periods
called renewal frames. At the beginning of each frame, it chooses a policy from
a set of options for that frame. The policy determines the duration of the
frame, the penalty incurred during the frame (such as energy expenditure), and
a vector of performance metrics (such as instantaneous number of jobs served).
The starting points of this line of research are Chapter 7 of the book
[Nee10a], the seminal work [Nee13a], and Chapter 5 of the PhD thesis of
Chih-ping Li [Li11]. These works consider stochastic optimization over a single
renewal system. By way of contrast, this thesis considers optimization over
multiple parallel renewal systems, which is computationally more challenging
and yields much more applications. The goal is to minimize the time average
overall penalty subject to time average overall constraints on the
corresponding performance metrics. The main difficulty, which is not present in
earlier works, is that these systems act asynchronously due to the fact that
the renewal frames of different renewal systems are not aligned. The goal of
the thesis is to resolve this difficulty head-on via a new asynchronous
algorithm and a novel supermartingale stopping time analysis which shows our
algorithms not only converge to the optimal solution but also enjoy fast
convergence rates. Based on this general theory, we further develop novel
algorithms for data center server provision problems with performance
guarantees as well as new heuristics for the multi-user file downloading
problems.
