{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:02:22Z","timestamp":1787385742293,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random times by the processors, and the transit times spent by packets on the ring are also random. Packets being forwarded, i.e., packets already on the ring, have priority over waiting packets. The objective of this paper is to analyze packet waiting times under a greedy policy within a discrete Markov model that retains the overall structure of a practical system but is simple enough so that explicit results can be proved. Independent, identical Bernoulli processes model message generation at the processors, and independently and identically distributed (i.i.d.) geometric random variables model the transit times. Our emphasis is on asymptotic behavior for large ring sizes, N, when the respective rate parameters have the scaling $\\lambda \/N$ and $\\mu \/N$. Our main result shows that, if the traffic intensity is fixed at $\\rho = \\lambda \/ \\mu &lt; 1$, then as $N \\to \\infty$ the expected time a message waits to be put on the ring is bounded by a constant. This result verifies that the expected waiting time under the greedy policy is within a constant factor of that under an optimal policy.<\/jats:p>","DOI":"10.1137\/s0097539794268637","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1221-1236","source":"Crossref","is-referenced-by-count":4,"title":["Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times"],"prefix":"10.1137","volume":"27","author":[{"suffix":"Jr.","given":"E. G.","family":"Coffman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nabil","family":"Kahale","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. T.","family":"Leighton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"N. Alon and J. H. Spencer (1991),\n                      The Probabilistic Method\n                      , John Wiley, New York."},{"key":"R2","unstructured":"S. Asmussen (1987),\n                      Applied Probability and Queues\n                      , John Wiley, New York."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"L. A. Barroso and M. Dubois (1992),\n                      The performance of Cache\u2010Coherent ring\u2010based multiprocessors\n                      , in Proc. 20th Ann. Internat. ACM Symp. Comp. Arch., ACM, New York, pp. 268\u2013277.","DOI":"10.1109\/ISCA.1993.698567"},{"key":"R4","unstructured":"P. Billingsley (1986),\n                      Probability and Measure\n                      , 2nd ed., John Wiley, New York."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/15326349508807351"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/18.568702"},{"key":"R7","unstructured":"N. Kahale and F. T. Leighton (1995),\n                      Greedy dynamic routing on arrays\n                      , in Proc. 6th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, pp. 558\u2013566."},{"key":"R8","unstructured":"L. Kleinrock (1975),\n                      Queueing Systems, Vol\n                      . I, John Wiley, New York."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"F. T. Leighton (1990),\n                      Average case analysis of greedy routing algorithms on arrays\n                      , in Proc. 2nd Ann. ACM Symp. Parallel Algs. Arch., ACM, New York, pp. 2\u201310.","DOI":"10.1145\/97444.97448"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"F. T. Leighton (1992),\n                      Introduction To Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes\n                      , Morgan Kaufmann, San Mateo, CA.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher (1994),\n                      Bounds on the greedy algorithm for array networks\n                      , in Proc. 6th Ann. ACM Symp. Parallel Alg. Arch., ACM, New York, pp. 346\u2013353.","DOI":"10.1145\/181014.181446"},{"key":"R12","unstructured":"N. U. Prabhu (1965),\n                      Stochastic Processes\n                      , Macmillan, New York."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(90)90039-U"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794268637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:04Z","timestamp":1787336044000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794268637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":13,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794268637"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794268637","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}