Joshua Miller

Harvey Mudd College Mathematics 2018

Thesis Proposal: Sequential Probing with a Random Start
Thesis Advisor: Prof. Nicholas Pippenger
Second Reader: Prof. Susan E. Martonosi

Sequential Probing with a Random Start

Many will be familiar with the problem of collision resolution in hash tables. One option for collision resolution is open addressing, in which the collision is resolved by searching (commonly called probing) for alternative empty bins in the hash table, rather than placing the table entry into the bin to which it was originally hashed. One way to search for empty bins is via linear probing, where we have a fixed number of bins between probes.

A somewhat analogous problem is that of server queueing. Picture a collection of servers and a stream of requests going into those servers. Each server can process one request at a time, and while doing so, is considered to be in a busy state. After processing the request, the server returns to an idle state. A natural question to ask is "how do we find an idle server as quickly as possible?" Algorithms for searching for idle servers are similar in nature to algorithms meant for searching for empty bins in hash tables. However, the key difference between the two problems is that servers can return to an "empty" (idle) state, whereas we do not remove entries from hash tables.

For my senior thesis, I will be investigating an algorithm that begins with a uniformly random probe then proceeds via linear probing with a step size of 1. This approach sits between the two extremes of linear probing with a fixed start (studied by Patrick Eschenfeldt, Ben Gross, and Nicholas Pippenger) and purely random probing. While I do not expect this algorithm to outperform algorithms such as random probing, it's worth investigating because little is known about the performance of algorithms between these two extremes.