{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:33Z","timestamp":1787340633261,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean \u201cflag\u201d variables, each of which can be written by only one process and read by at most one other process.<\/jats:p>\n                  <jats:p>No global bounds in the speeds of processes are assumed. Processes with speed zero are considered dead. However, when their speed is nonzero then they execute their programs correctly. Dead processes do not harm our algorithms\u2019 performance with respect to pairs of other running processes. When the rate of change of the ratio of speeds of neighbour processes (i.e., relative acceleration) is bounded, then any two of these processes will establish communication within a constant number of steps of the slowest process with high likelihood. So, our implementation has the property of achieving relative real time response. We can use our techniques to solve other problems such as resource allocation and implementation of parallel languages such as CSP and Ada. Note that we do not have any probability assumptions about the system behaviour, although our algorithms use the technique of probabilistic choice.<\/jats:p>","DOI":"10.1137\/0214005","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"75-92","source":"Crossref","is-referenced-by-count":3,"title":["Unbounded Speed Variability in Distributed Communications Systems"],"prefix":"10.1137","volume":"14","author":[{"given":"John H.","family":"Reif","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Angluin,  Local and global properties in networks of processors,  12th Annual Symposium on Theory of Computing, Los Angeles, CA,  1980,  82\u201393, April","DOI":"10.1145\/800141.804655"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"E. Arjomandi, M. Fischer, N. Lynch,  A difference in efficiency between synchronous and asynchronous systems,  13th Annual Symposium on Theory of Computing,  1981, April","DOI":"10.21236\/ADA097476"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/357094.357101"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. B. Dennis, D. P. Misunas,  A preliminary architecture for a basic data-flow processor,  Proc. 2nd Annual Symposium on Computer Architecture, ACM, IEEE,  1974,  126\u2013132","DOI":"10.1145\/642089.642111"},{"key":"R5","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","year":"1966"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"N. Francez, Rodeh,  A distributed data type implemented by a probabilistic communication scheme,  21st Annual Symposium on Foundations of Computer Science, Syracuse, NY,  1980,  373\u2013379, Oct.","DOI":"10.1109\/SFCS.1980.2"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"S. Hart, M. Sharir, A. Pnueli,  Termination of probabilistic concurrent programs,  9th ACM Symposium on Principles of Programming Languages, Albuquerque, NM,  1982, January","DOI":"10.1145\/582153.582154"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. Lehmann, M. Rabin,  On the advantages of free choice: a symmetric and fully distributed solution to the dining philosphers' problem,  8th ACM Symposium on Principles of Programming Languages,  1981, January","DOI":"10.1145\/567532.567547"},{"key":"R10","unstructured":"R. Lipton, F. G. Sayward,  Response time of parallel programs, Research Report, 108, Dept. Computer Science, Yale Univ., New Haven, CT,  1977, June"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. A. Lynch,  Fast allocation of nearby resources in a distributed system,  12th Annual Symposium on Theory of Computing, Los Angeles, CA,  1980,  70\u201381, April","DOI":"10.1145\/800141.804654"},{"key":"R12","unstructured":"A. Mahjoub,  Some comments on Ada as a real-time programming language, to appear"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Rabin,  N-process synchronization by a  4log2N-valued shared variable,  21st Annual Symposium on Foundations of Computer Science, Syracuse, NY,  1980,  407\u2013410, October","DOI":"10.1109\/SFCS.1980.26"},{"key":"R14","unstructured":"M. Rabin,  The choice coordination problem, Mem., UCB\/ERL M80\/38, Electronics Research Lab., Univ. California, Berkeley,  1980, August"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. H. Reif, P. Spirakis,  Unbounded speed variability in distributed communication systems,  9th ACM Symposium on Principles of Programming Languages, Albuquerque, NM,  1982, Jan.","DOI":"10.1145\/582153.582159"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/2993.357244"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. H. Reif, P. Spirakis,  Real time resource allocation in a distributed system,  1st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Ottawa, Canada,  1982, August","DOI":"10.1145\/800220.806685"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13345-3_36"},{"key":"R19","unstructured":"J. Schwarz,  Distributed synchronization of communicating sequential processes, DAI Research Report, 56, Univ. Edinburgh,  1980"},{"key":"R20","unstructured":"S. Tonag,  Deadlock and livelock-free packet switching networks,  12th Annual Symposium on Theory of Computing, Los Angeles, CA,  1980,  82\u201393, April"},{"key":"R21","unstructured":"L. G. Valiant,  A scheme for fast parallel communication, Technical Report, Computer Science Dept., Edinburgh, Scotland,  1980, July"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:11Z","timestamp":1787337731000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214005"],"URL":"https:\/\/doi.org\/10.1137\/0214005","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}