Access Restriction

Author Tsitsiklis, John N. ♦ Papadimitriou, Christos H. ♦ Humblet, Pierre
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1986
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs $\textit{i}$ and $\textit{j}$ in the system, such that $\textit{i}$ arrived later than $\textit{j},$ there is a fixed probability $\textit{p}$ that $\textit{i}$ will have to wait for $\textit{j}'s$ execution to terminate before $\textit{i}$ starts executing. This queuing system is a very simple model for database concurrency control via “static” locking, as well as of parallel execution of programs consisting of several interdependent processes. The problem of determining the maximum arrival rate (as a function of $\textit{p})$ that can be sustained before this system becomes unstable is studied. It is shown that this rate is inversely proportional to $\textit{p},$ and close upper and lower bounds on the constant for the case of deterministic departures are found. The result suggests that the degree of multiprogramming of multiuser databases, or the level of parallelism of concurrent programs, is inversely proportional to the probability of conflict, and that the constant is small and known within a factor of 2. The technique used involves the computation of certain asymptotic parameters of a random infinite directed acyclic graph (dag) that seem of interest by themselves.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1986-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 33
Issue Number 3
Page Count 10
Starting Page 593
Ending Page 602

Open content in new tab

   Open content in new tab
Source: ACM Digital Library