Graduation Year
2018
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Nick Pippenger
Reader 2
Susan Martonosi
Terms of Use & License Information
Rights Information
@2018 Joshua A. Miller
Abstract
Processing user requests quickly requires not only fast servers, but also demands methods to quickly locate idle servers to process those requests. Methods of finding idle servers are analogous to open addressing in hash tables, but with the key difference that servers may return to an idle state after having been busy rather than staying busy. Probing sequences for open addressing are well-studied, but algorithms for locating idle servers are less understood. We investigate sequential probing with a random start as a method for finding idle servers, especially in cases of heavy traffic. We present a procedure for finding the distribution of the number of probes required for finding an idle server by using a Markov chain and ideas from enumerative combinatorics, then present numerical simulation results in lieu of a general analytic solution.
Recommended Citation
Miller, Joshua, "Sequential Probing With a Random Start" (2018). HMC Senior Theses. 115.
https://scholarship.claremont.edu/hmc_theses/115
