{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:23:38Z","timestamp":1725459818697},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354017219X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0039627","type":"book-chapter","created":{"date-parts":[[2006,1,31]],"date-time":"2006-01-31T16:55:52Z","timestamp":1138726552000},"page":"456-467","source":"Crossref","is-referenced-by-count":2,"title":["On the expected complexity of distributed selection"],"prefix":"10.1007","author":[{"given":"Nicola","family":"Santoro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey B.","family":"Sidney","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stuart J.","family":"Sidney","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"37_CR1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1145\/322186.322200","volume":"27","author":"H. Abelson","year":"1980","unstructured":"H. Abelson, \"Lower bounds on information transfer in distributed systems\", J. ACM 27, 2, April 1980, 384\u2013392.","journal-title":"J. ACM"},{"unstructured":"F. Chin, H.F. Ting, \"A near-optimal algorithm for finding the median distributively\", Proc. 5th IEEE Conf. on Distributed Computing Systems, Denver, May 1985.","key":"37_CR2"},{"doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, \"Tradeoffs for selection in distributed networks\", Proc. 2nd ACM Symp. on Principles of Distributed Computing, Montreal, Aug. 1983, 154\u2013160.","key":"37_CR3","DOI":"10.1145\/800221.806718"},{"issue":"2","key":"37_CR4","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"G.N. Frederickson and D.B. Johnson, \"The complexity of selection and ranking in X+Y and matrices with sorted columns\", J. Computer and System Science 24, 2, April 1982, 197\u2013208.","journal-title":"J. Computer and System Science"},{"unstructured":"E. Korach, D. Rotem, N. Santoro, \"Distributed algorithms for ranking the nodes of a network\", Proc. 13th SE Conf. on Combinatorics, Graph Theory and Computing, Boca Raton, Feb. 1982, 235\u2013246.","key":"37_CR5"},{"unstructured":"J.M. Marberg, E. Gafni, \"An optimal shout-echo algorithm for selection in distributed sets\", Proc. 23rd Allerton Conf. on Comm., Control and Computing, Monticello, Oct. 1985.","key":"37_CR6"},{"key":"37_CR7","volume-title":"Distributed algorithms for selection","author":"T.A. Matsushita","year":"1983","unstructured":"T.A. Matsushita, \"Distributed algorithms for selection\", Master Thesis, Department of Computer Science, University of Illinois, Urbana, July 1983."},{"issue":"2","key":"37_CR8","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0022-0000(82)90045-9","volume":"24","author":"M. Rodeh","year":"1982","unstructured":"M. Rodeh, \"Finding the median distributively\", J. Computer and System Science 24, 2, April 1982, 162\u2013167.","journal-title":"J. Computer and System Science"},{"key":"37_CR9","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1109\/TC.1985.5009389","volume":"4","author":"D. Rotem","year":"1985","unstructured":"D. Rotem, N. Santoro, J.B. Sidney, \"Distributed sorting\", IEEE Transactions on Computers C-34, 4, April 1985, 372\u2013376.","journal-title":"IEEE Transactions on Computers C-34"},{"key":"37_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1002\/net.3230160108","volume":"16","author":"D. Rotem","year":"1986","unstructured":"D. Rotem, N. Santoro, J.B. Sidney, \"Shout-echo selection in distributed files\", Networks 16, 1986, 77\u201386.","journal-title":"Networks"},{"unstructured":"N. Santoro, M. Scheutzow, J.B. Sidney, \"New bounds on the communication complexity of distributed selection\", J. Parallel and Distributed Computing, to appear.","key":"37_CR11"},{"unstructured":"N. Santoro, J.B. Sidney, \"Order statistics on distributed sets\", Proc. 20th Allerton Conf. on Communication, Control and Computing, Monticello, Oct. 1982, 251\u2013256.","key":"37_CR12"},{"key":"37_CR13","series-title":"Tech. Rep.","volume-title":"On the expected complexity of distributed selection","author":"N. Santoro","year":"1985","unstructured":"N. Santoro, J.B. Sidney, S.J. Sidney, \"On the expected complexity of distributed selection\", Tech. Rep. SCS-TR-69, School of Computer Science, Carleton University, Ottawa, Feb. 1985."},{"unstructured":"N. Santoro, E. Suen, \"Reduction techniques for selection in distributed files\", Proc. Int. Conf. on Parallel Processing, St. Charles, 1986, 1003\u20131009.","key":"37_CR14"},{"doi-asserted-by":"crossref","unstructured":"L. Shrira, N. Francez, M. Rodeh, \"Distributed k-selection: from a sequential to a distributed algorithm\", Proc. 2nd ACM Symp. on Principles of Distributed Computing, Montreal, Aug. 1983, 143\u2013153.","key":"37_CR15","DOI":"10.1145\/800221.806717"},{"doi-asserted-by":"crossref","unstructured":"A.C.C. Yao, \"Some complexity questions related to distributive computing\", Proc. 11th ACM Symp. on Theory of Computing, Atlanta, 1979, 209\u2013213.","key":"37_CR16","DOI":"10.1145\/800135.804414"},{"key":"37_CR17","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1109\/TC.1985.5009390","volume":"4","author":"S. Zaks","year":"1985","unstructured":"S. Zaks, \"Optimal distributed algorithms for sorting and ranking\", IEEE Transactions on Computers C-34, 4, April 1985, 376\u2013379.","journal-title":"IEEE Transactions on Computers C-34"}],"container-title":["Lecture Notes in Computer Science","STACS 87"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0039627.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:25:57Z","timestamp":1607552757000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0039627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354017219X"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0039627","relation":{},"subject":[]}}