<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-285
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
M.S. Paterson and A. Srinavasan,
Contention Resolution with Bounded Delay
(May 1, 1995).
Abstract
When many distributed processes contend for a single shared resource
that can service at most one process per time slot, the key problem is
devising a good distributed protocol for contention resolution. This has
been studied in the context of multiple-access channels (e.g. ALOHA,
Ethernet), and recently for PRAM emulation and routing in optical
computers. Under a stochastic model of continuous request generation
from a set of n synchronous processes, Raghavan and Upfal have recently
shown a protocol which is stable if the request rate is at most lambda_0
for some fixed lambda_0 < 1; their main result is that for any given
resource request, its expected delay (expected time to get serviced) is
O(log n). Assuming further that the initial clock times of the processes
are within a known bound B of each other, we present a stable protocol,
again for some fixed positive request rate lambda_1, 0 < lambda_1 <
1, wherein the expected delay for each request is O(1), independent of
n. We derive this by showing an analogous result for an infinite number
of processes, assuming that all processes agree on the time; this is
the first such result. We also present tail bounds which show that for
every given resource request, it is unlikely to remain unserviced for
much longer than expected, and extend our results to other classes of
input distributions.
<%@ include file="cited.html" %>
M.S. Paterson and A. Srinivasan,
"Contention Resolution with Bounded Delay",
Annual Symposium on Foundations of Computer Science,
IEEE Computer Society Press,
pp. 104-113
(1995)
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>