Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01tx31qm782
 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. URI: http://arks.princeton.edu/ark:/88435/dsp01tx31qm782 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

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