{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:37:22Z","timestamp":1742989042723,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540552840"},{"type":"electronic","value":"9783540470120"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/bfb0023830","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T06:17:40Z","timestamp":1132381060000},"page":"204-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Leaders election without conflict resolution rule"],"prefix":"10.1007","author":[{"given":"Joseph","family":"Gil","sequence":"first","affiliation":[]},{"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"P. Beame and J. H\u00e5stad. Optimal bounds for decision problems on the CRCW PRAM. In STOC '87, pages 83\u201393, 1987.","DOI":"10.1145\/28395.28405"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"O. Berkman, D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin. Highly parallelizable problems. In STOC '89, pages 309\u2013319, 1989.","DOI":"10.1145\/73007.73036"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In FOCS '89, pages 196\u2013202, 1989.","DOI":"10.1109\/SFCS.1989.63478"},{"key":"19_CR4","unstructured":"P. C. Bhatt, K. Diks, T. Hagerup, V. C. Prasad, T. Radzik, and S. Saxena. Improved de-terministic parallel integer sorting. Technical Report 15\/1989, Fachbereich 14, Universit\u00e4t des Saarlandes, Nov. 1989."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"R. B. Boppana. Optimal separations between concurrent-write parallel machines. In STOC '89, pages 320\u2013326, 1989.","DOI":"10.1145\/73007.73037"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. Efficient simulations between concurrent-read concurrent-write PRAM models. In MFCS '88, pages 231\u2013239, 1988.","DOI":"10.1007\/BFb0017146"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik. New simulations between CRCW PRAMs. In FCT '89, pages 95\u2013104, 1989.","DOI":"10.1007\/3-540-51498-8_9"},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. A. Cook","year":"1986","unstructured":"S. A. Cook, C. Dwork, and R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J, Comput., 15:87\u201397, 1986.","journal-title":"SIAM J, Comput."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. Submitted for publication, Nov. 1991.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. SIAM J. Comput., 17:606\u2013627, June 1988.","journal-title":"SIAM J. Comput."},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01762109","volume":"3","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Simulations among concurrent-write PRAMs. Algorithmica, 3:43\u201351, 1988.","journal-title":"Algorithmica"},{"issue":"3","key":"19_CR12","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538\u2013544, July 1984.","journal-title":"J. ACM"},{"key":"19_CR13","unstructured":"J. Gil. Fast load balancing on PRAM, Manuscript, November 1990. Also in the Third IEEE Symposium on Parallel and Distributed Processing (SPDP '91)."},{"key":"19_CR14","volume-title":"PhD thesis","author":"J. Gil","year":"1990","unstructured":"J. Gil. Lower Bounds and Algorithms for Hashing and Parallel Processing. PhD thesis, The Hebrew University of Jerusalem, Givat Ram 91904, Jerusalem, Israel, Nov. 1990."},{"key":"19_CR15","unstructured":"J. Gil and Y. Matias. Fast and efficient simulations among CRCW models. Manuscript, 1990."},{"key":"19_CR16","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM-designing by expectation. In SODA '91, pages 271\u2013280, Jan. 1991."},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"J. Gil and Y. Matias. Leaders election without a conflict resolution rule-fast and efficient randomized simulations among CRCW PRAMs. Technical Report 91\u2013147, Inst. for Adv. Comp. Sc., Univ. of Maryland, 1991. Submitted for publication.","DOI":"10.1007\/BFb0023830"},{"key":"19_CR18","unstructured":"J. Gil and Y. Matias. Polynomial hash functions are reliable. Manuscript, Aug. 1991."},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In FOCS '91, pages 698\u2013710, Oct. 1991. (Revised version).","DOI":"10.1109\/SFCS.1991.185438"},{"key":"19_CR20","unstructured":"J. Gil and L. Rudolph. Counting and packing in parallel. In ICPP '86, pages 1000\u20131002, 1986."},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"V. Grolmusz and P. L. Ragde. Incomparability in parallel computation. In FOCS '87, pages 89\u201398, 1987.","DOI":"10.1109\/SFCS.1987.34"},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0166-218X(90)90082-N","volume":"29","author":"V. Grolmusz","year":"1990","unstructured":"V. Grolmusz and P. L. Ragde. Incomparability in parallel computation. Discrete Applied Mathematics, 29:63\u201378, 1990.","journal-title":"Discrete Applied Mathematics"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Radzik. Every robust CRCW PRAM can efficiently simulate a Priority PRAM. In SPAA '90, pages 117\u2013124, 1990.","DOI":"10.1145\/97444.97677"},{"key":"19_CR24","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"C-32","author":"C. P. Kruskal","year":"1983","unstructured":"C. P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. on Comp, C-32:942\u2013946, 1983.","journal-title":"IEEE Trans. on Comp"},{"key":"19_CR25","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Ku\u010dera","year":"1982","unstructured":"L. Ku\u010dera. Parallel computation and conflicts in memory access. Inf. Process. Lett., 14:93\u201396, 1982.","journal-title":"Inf. Process. Lett."},{"key":"19_CR26","unstructured":"P. D. MacKenzie and Q. F. Stout. Ultra-fast expected time parallel algorithms. In SODA '91, pages 414\u2013423, 1991."},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. On parallel hashing and integer sorting. In ICALP '90, pages 729\u2013743, 1990.","DOI":"10.1007\/BFb0032070"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time-with applications to parallel hashing. In STOC '91, pages 307\u2013316, 1991. Also in UMIACS-TR-91\u201365, Inst. for Adv. Comp. Studies, Univ. of Maryland, April 1991.","DOI":"10.1145\/103418.103453"},{"issue":"4","key":"19_CR29","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1016\/0196-6774(91)90034-V","volume":"12","author":"Y. Matias","year":"1991","unstructured":"Y. Matias and U. Vishkin. On parallel hashing and integer sorting. J. of Alg., 12(4):573\u2013606, 1991.","journal-title":"J. of Alg."},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"P. L. Ragde. The parallel simplicity of compaction and chaining. In ICALP '90, pages 744\u2013751, 1990.","DOI":"10.1007\/BFb0032071"},{"issue":"3","key":"19_CR31","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/0401040","volume":"1","author":"P. L. Ragde","year":"1988","unstructured":"P. L. Ragde, W. L. Steiger, E. Szemer\u00e9di, and A. Wigderson. The parallel complexity of element distinctness is \u03a9(\u221alg n). SIAM J. Disc. Math., 1(3):399\u2013410, Aug. 1988.","journal-title":"SIAM J. Disc. Math."},{"issue":"2","key":"19_CR32","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput., 14(2):396\u2013409, May 1985.","journal-title":"SIAM J. Comput."},{"key":"19_CR33","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. J. of Alg., 2:88\u2013102, 1981.","journal-title":"J. of Alg."},{"key":"19_CR34","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant. Parallelism in comparison problems. SIAM J. Comput., 4:348\u2013355, 1975.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","LATIN '92"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T18:53:46Z","timestamp":1736103226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023830"}},"subtitle":["Fast and efficient randomized simulations among CRCW PRAMs"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540552840","9783540470120"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/bfb0023830","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}