Stochastic Contention Resolution with Short Delays

Copyright [©] [1999] by The Society for Industrial and Applied Mathematics. All rights reserved

We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the maximum arrival rate for which the protocol is stable and the expected delay of a request from arrival to service. Known solutions %(such as backoff protocols) are either unstable for any constant injection rate, or have polynomial (in the number of contenders) expected delay. Our main contribution is a protocol that is stable for a constant injection rate, while achieving logarithmic expected delay. We extend our results to the case of multiple servers, with each request being targeted for a specific server. This is related to the {\em optically connected parallel computer} (or {\em OCPC}) model. Finally, we prove a lower bound showing that long delays are inevitable in a class of protocols including backoff-style protocols, if the arrival rate is large enough (but still smaller than 1).

By: Prabhakar Raghavan and Eli Upfal (The Weizmann Inst., Israel)

Published in: SIAM Journal on Computing, volume 28, (no 2), pages 709-19 in 1999

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .