Graduation Year


Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science



Reader 1

Nick Pippenger

Reader 2

Susan Martonosi

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

@2018 Joshua A. Miller


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.