Back to search

University of British Columbia

Balancing latency and efficiency in computing systems

Abstract

dc:description

Modern cloud platforms and serverless computing frameworks must balance two competing objectives: maintaining low request latency while minimizing the cost of provisioning computational resources. In many practical systems, these trade-offs are further complicated by startup overheads such as container cold starts, runtime initialization, or switching between classes of workloads that require shared setup. These effects arise across multiple layers of computing infrastructure, from serverless function provisioning to processor scheduling with setup-dependent tasks. This thesis studies two online scheduling problems motivated by these challenges. The first problem considers dynamic container provisioning where additional containers can be launched on demand but incur a fixed startup delay. The objective is to characterize and approximate the trade-off between operational cost, measured by the total time containers remain active, and system performance, measured by queueing delay. We develop online algorithms that achieve cost within (1+ϵ) of the optimal offline solution while guaranteeing worst-case response times bounded by O(1/ϵ) times the optimal delay. Empirical evaluation using synthetic and production-inspired workloads demonstrates that the proposed algorithms closely approximate the Pareto frontier between cost and latency while exhibiting favorable average-case behavior. The second problem examines uniprocessor scheduling of unit-length jobs that belong to families, where processing a family requires incurring a family-specific setup time. Jobs arrive online and have deadlines, and the objective is to minimize the number of missed deadlines. We show that classical policies such as Earliest Deadline First fail in this setting and that the offline version of the problem is NP-hard even under restricted assumptions. We introduce a new online policy, Interval Buffer EDF, which approaches 1-competitiveness as job slack increases, along with additional heuristic policies that provide provable competitive guarantees and strong empirical performance. Together, these results provide theoretical foundations and practical algorithms for scheduling and resource allocation in systems with startup overheads. By establishing provable competitive guarantees and empirically validating algorithmic behavior, this work contributes toward the design of predictable, cost-efficient computing platforms that must operate under uncertainty in dynamic environments.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Thompson, Grady
Contributors dc:contributor
  • Gopalakrishnan, Sathish

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/94550

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Thompson, Grady. Balancing latency and efficiency in computing systems. master's thesis, University of British Columbia, 2026. http://hdl.handle.net/2429/94550