{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T18:53:38Z","timestamp":1648925618655},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p> The abstract problem of using P failure-prone processors to cooperatively update all locations of an N-element shared array is called Write-All. Solutions to Write-All can be used iteratively to construct efficient simulations of PRAM algorithms on failure-prone PRAMS. Such use of Write-All in simulations is abstracted in terms of the iterative Write-All problem. The efficiency of the algorithmic solutions for Write-All and iterative Write-All is measured in terms of work complexity where all processing steps taken by the processors are counted. This paper considers determinitic solutions for the Write-All and iterative Write-All problems in the fail-stop synchronous CRCW PRAM model where memory access concurrency needs to be controlled. A deterministic algorithm of Kanellakis, Michailidis, and Shvartsman [16] efficiently solves the Write-All problem in this model, while controlling read and write memory access concurrency. However it was not shown how the number of processor failures f affects the work efficiency of the algorithm. The results herein give a new analysis of the algorithm [16] that obtain failure-sensitive work bounds, while retaining the known memory access concurrency bounds. Specifically, the new result expresses the work bound as a function of N, Pandf. Another contribution in this paper is the new failure-sensitive analysis for iterative Write-All with controlled memory access concurrency. This result yields tighter bounds on work (vs. [16]) for simulations of PRAM algorithms on fail-stop PRAMS. <\/jats:p>","DOI":"10.1142\/s0129626407002946","type":"journal-article","created":{"date-parts":[[2007,7,2]],"date-time":"2007-07-02T05:44:20Z","timestamp":1183355060000},"page":"153-168","source":"Crossref","is-referenced-by-count":1,"title":["FAILURE-SENSITIVE ANALYSIS OF PARALLEL ALGORITHMS WITH CONTROLLED MEMORY ACCESS CONCURRENCY"],"prefix":"10.1142","volume":"17","author":[{"given":"CHRYSSIS","family":"GEORGIOU","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, University of Cyprus, 75 Kallipoleos Str., CY-1678 Nicosia, Cyprus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER","family":"RUSSELL","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER A.","family":"SHVARTSMAN","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, University of Connecticut, 371 Fairfield Rd., Unit 2155, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.8.756"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794319126"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0003"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.cs.03.060188.001313"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008930"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00193-X"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-003-0099-3"},{"key":"rf15","series-title":"Cambridge International Series on Parallel Computation","volume-title":"Lectures on Parallel Computation","author":"Gibbons A. M.","year":"1993"},{"key":"rf16","first-page":"146","volume":"2","author":"Kanellakis P. C.","journal-title":"Nordic Journal of Computing"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02277667"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5210-6"},{"key":"rf19","unstructured":"R. M.\u00a0Karp and V.\u00a0Ramachandran, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (1990)\u00a0pp. 869\u2013941."},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/s002240010009"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1137\/0221063"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90156-C"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626407002946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:14:33Z","timestamp":1565093673000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626407002946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":16,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1142\/S0129626407002946"],"URL":"https:\/\/doi.org\/10.1142\/s0129626407002946","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]}}}