Skip navigation
Please use this identifier to cite or link to this item:
Title: An Introduction to Scheduling Problems
Authors: Fitzpatrick, David "Davey"
Advisors: Sly, Allan
Department: Mathematics
Class Year: 2021
Abstract: In this paper we examine several examples of scheduling problems, in which given sequences must be interleaved so that certain propeerties hold. We begin by examining the idea of a self-stabilizing system in distributed computing, which is a set of computers that settle into a regular sequence of activations when begun in an arbitrary initial con guration, and considering some examples presented by Dijkstra. Next, we examine a self-stabilizing system design that works for an arbitrary network, via abstract tokens that perform random walks on the network graph. Then, we describe two scheduling problems with connections to percolation theory, the discrete Lipschitz embedding problem and the compatible sequences problem, which were solved by an inductive multi-scale approach, and we explain how this approach was later adapted to solve a problem related to the aforementioned token passing scheme.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
FITZPATRICK-DAVEY-THESIS.pdf236.63 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.