William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
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 are either unstable for any constant injection rate or have at least 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 optically connected parallel computer (or 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).
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Yigal Hoffner, Simon Field, et al.
EDOC 2004
B.K. Boguraev, Mary S. Neff
HICSS 2000
Khaled A.S. Abdel-Ghaffar
IEEE Trans. Inf. Theory