{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:34:01Z","timestamp":1787387641705,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1981,8]]},"abstract":"<jats:p>Deadlock states have been observed in existing computer networks, emphasizing the need for carefully designed flow control procedures (controllers) to avoid deadlocks. Such a deadlock-free controller is readily found if we allow it global information about the overall network state. Generally, this assumption is not realistic, and we must resort to deadlock-free local controllers using only packet and node information. We present here several types of such controllers, we study their relationship and give a proof of their optimality with respect to deadlock-free controllers using the same set of local parameters.<\/jats:p>","DOI":"10.1137\/0210044","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:24:20Z","timestamp":1109226260000},"page":"594-611","source":"Crossref","is-referenced-by-count":30,"title":["Deadlock-Free Packet Switching Networks"],"prefix":"10.1137","volume":"10","author":[{"given":"Sam","family":"Toueg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey D.","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAK","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1965.264176"},{"key":"RAL","unstructured":"B. W. Arden, H. Lee,  A multitree structured network,  Proc. IEEE COMPCON 78, Washington, DC,  1978,  201\u2013210, September"},{"key":"RFR","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1966.264310"},{"key":"RG","unstructured":"K. D. Gunther,  Prevention of buffer deadlocks in packet switching networks,  IFIP-IIASA Workshop on Data Communications, Ladenberg, Austria,  1975, g.15-g.19, September"},{"key":"RGD","unstructured":"M. G. Gouda, Ph.D. Thesis,  Protocol machines, Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ontario, Canada,  1977"},{"key":"RGHKP","doi-asserted-by":"publisher","DOI":"10.1016\/0376-5075(78)90028-4"},{"key":"RKL","volume-title":"Queueing Systems Vol. II: Computer Applications","author":"Kleinrock L.","year":"1976"},{"key":"RKN","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1967.264615"},{"key":"RKS","doi-asserted-by":"publisher","DOI":"10.1145\/356651.356653"},{"key":"RMES","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094552"},{"key":"RMS","unstructured":"P. M. Merlin, P. J. Schweitzer,  Deadlock-avoidance in store-and-forward networks. I: Store-and-Forward Deadlock, IBM RC 6624 Yorktown Hts., NY"},{"key":"RMT","unstructured":"D. E. Morgan, D. J. Taylor,  Computer network reliability and availability: the state of the art,  Conference Record, 14th IEEE International Conference on Communications, Vol. 1, Toronto,  1978, 3.3.1\u20133.3.5, June"},{"key":"RRH","unstructured":"E. Raubold, J. Haenle,  A method of deadlock-free resource allocation and flow control in packet networks,  Proc. ICCC 76, Toronto, Ont., Canada,  1976,  483\u2013487, Aug."},{"key":"RSE1","unstructured":"A. Segall,  Optimal distributed routing in data-communication networks,  Proc. 10th IEEE Conference Electrical and Electronics Engineers in Israel, Tel-Aviv, Israel,  1977,  4\u20136, Oct."},{"key":"RSMG","unstructured":"A. Segal, P. M. Merlin, R. G. Gallager,  A recoverable protocol for loop-free distributed routing,  Conference Record, 14th IEEE International Conference on Communications, Vol. 1, Toronto,  1978, 3.5.1\u20133.5.5, June"},{"key":"RSTONE","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223205"},{"key":"RSTOR","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1970.222861"},{"key":"RTS1","doi-asserted-by":"publisher","DOI":"10.1137\/0210053"},{"key":"RTS2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675402"},{"key":"RT","doi-asserted-by":"crossref","unstructured":"S. Toueg,  Deadlock- and livelock-free packet switching networks,  Proc. 12th ACM Symposium on Theory of Computing, Los Angeles, California,  1980,  94\u201399, April","DOI":"10.1145\/800141.804656"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0210044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:46Z","timestamp":1787337286000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0210044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,8]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1981,8]]}},"alternative-id":["10.1137\/0210044"],"URL":"https:\/\/doi.org\/10.1137\/0210044","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,8]]}}}