STOCHASTIC CONTENTION RESOLUTION WITH SHORT DELAYS

We study contention resolution protocols under a stochastic model of c ontinuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the maximum ar rival rate for which the protocol is stable and the expected delay of a request from arrival to service. Known solutions are either unstable for any constant injection rate or have at least polynomial (in the n umber of contenders) expected delay. Our main contribution is a protoc ol that is stable for a constant injection rate, while achieving logar ithmic expected delay. We extend our results to the case of multiple s ervers, with each request being targeted for a specific server. This i s related to the optically connected parallel computer (or OCPC) model . Finally, we prove a lower bound showing that long delays are inevita ble in a class of protocols including backoff-style protocols, if the arrival rate is large enough (but still smaller than 1).