Sid Chi-Kin Chau

This book addresses the urgent issue of massive and inefficient energy consumption by data centers, which have become the largest co-located computing systems in the world and process trillions of megabytes of data every second. Dynamic provisioning algorithms have the potential to be the most viable and convenient of approaches to reducing data center energy consumption by turning off unnecessary servers, but they incur additional costs from being unable to properly predict future workload demands that have only recently been mitigated by advances in machine-learned predictions.This book explores whether it is possible to design effective online dynamic provisioning algorithms that require zero future workload information while still achieving close-to-optimal performance. It also examines whether characterizing the benefits of utilizing the future workload information can then improve the design of online algorithms with predictions in dynamic provisioning. The book specifically develops online dynamic provisioning algorithms with and without the available future workload information. Readers will discover the elegant structure of the online dynamic provisioning problem in a way that reveals the optimal solution through divide-and-conquer tactics. The book teaches readers to exploit this insight by showing the design of two online competitive algorithms with competitive ratios characterized by the normalized size of a look-ahead window in which exact workload prediction is available.

This book addresses the urgent issue of massive and inefficient energy consumption by data centers, which have become the largest co-located computing systems in the world and process trillions of megabytes of data every second. Dynamic provisioning algorithms have the potential to be the most viable and convenient of approaches to reducing data center energy consumption by turning off unnecessary servers, but they incur additional costs from being unable to properly predict future workload demands that have only recently been mitigated by advances in machine-learned predictions.This book explores whether it is possible to design effective online dynamic provisioning algorithms that require zero future workload information while still achieving close-to-optimal performance. It also examines whether characterizing the benefits of utilizing the future workload information can then improve the design of online algorithms with predictions in dynamic provisioning. The book specifically develops online dynamic provisioning algorithms with and without the available future workload information. Readers will discover the elegant structure of the online dynamic provisioning problem in a way that reveals the optimal solution through divide-and-conquer tactics. The book teaches readers to exploit this insight by showing the design of two online competitive algorithms with competitive ratios characterized by the normalized size of a look-ahead window in which exact workload prediction is available.

The electric power grid which has been an indispensable part of our society is being put under increasing pressure to meet the demands of a major surge in global energy consumption. As a result, the power grid needs to undergo transformations to meet the new challenges for a more sustainable society. One of these transformations is the need for continuous optimization in the smart grid so that it can react rapidly to dynamic situations in presence of fluctuating demands and uncertain renewable energy. In the past, the operations of power grid relied on careful a-priori planning, under the assumptions of static demands and predictable circumstances. In the era of dynamic smart grid, self-optimization with adaptive control is more crucial to its operations. Many of the ideas developed by the theoretical computer science community can be applied in such cases.This monograph establishes an interdisciplinary bridge between power systems engineering and theoretical computer science by relating the practical and challenging problems in electric power systems with the modern theoretical tools from computer science. The proper understanding of these hard problems in electric power systems can advance the frontiers of both communities. This monograph introduces Power System Engineers to the concepts and results of approximation algorithms, and applies them to solve electric power systems problems as well as providing Computer Scientists with an exposition of a class of challenging combinatorial problems in electric power systems.