{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:35:54Z","timestamp":1725496554090},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583295"},{"type":"electronic","value":"9783540486541"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/978-3-540-48654-1_21","type":"book-chapter","created":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T09:34:34Z","timestamp":1462872874000},"page":"242-266","source":"Crossref","is-referenced-by-count":0,"title":["Efficient parallelism vs reliable distribution: a trade-off for concurrent computations"],"prefix":"10.1007","author":[{"given":"Paris C.","family":"Kanellakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Michailidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex A.","family":"Shvartsman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","volume-title":"C","author":"M Ajtai","year":"1994","unstructured":"M. Ajtai, J. Aspnes, C. Dwork, O. Waarts, \u201cThe Competitive Analysis of Wait-Free Algorithms and its Application to the Cooperative Collect Problem\u201d, to appear in PODC, 1994."},{"issue":"6","key":"21_CR2","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/MC.1987.1663586","volume":"20","author":"GB Adams III","year":"1987","unstructured":"G. B. Adams III, D. P. Agrawal, H. J. Seigel, \u201cA Survey and Comparison of Fault-tolerant Multistage Interconnection Networks\u201d, IEEE Computer, 20, 6, pp. 14\u201329, 1987.","journal-title":"IEEE Computer"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"R. Anderson, H. Woll, \u201cWait-Free Parallel Algorithms for the Union-Find Problem\u201d, Proc. of the 23rd ACM Symp. on Theory of Computing, pp. 370\u2013380, 1991.","DOI":"10.1145\/103418.103458"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/SFCS.1992.267777","volume-title":"Proc. of the 33rd IEEE Symposium on Foundations of Computer Science","author":"Y Aumann","year":"1992","unstructured":"Y. Aumann and M.O. Rabin, \u201cClock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation\u201d, in Proc. of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 147\u2013156, 1992."},{"key":"21_CR5","first-page":"271","volume-title":"Proc. of the 34th IEEE Symposium on Foundations of Computer Science","author":"Y Aumann","year":"1993","unstructured":"Y. Aumann, Z.M. Kedem, K.V. Palem, M.O. Rabin, \u201cHighly Efficient Asynchronous Execution of Large-Grained Parallel Programs\u201d, in Proc. of the 34th IEEE Symposium on Foundations of Computer Science, pp. 271\u2013280, 1993."},{"key":"21_CR6","doi-asserted-by":"crossref","DOI":"10.21236\/ADA242764","volume-title":"Parallel algorithms with processor failures and delays","author":"J Buss","year":"1991","unstructured":"J. Buss, P.C. Kanellakis, P. Ragde, A.A. Shvartsman, \u201cParallel algorithms with processor failures and delays\u201d, Brown Univ. TR CS-91\u201354, August 1991."},{"key":"21_CR7","first-page":"170","volume-title":"Proc. of the 1989 ACM Symp. on Parallel Algorithms and Architectures","author":"R Cole","year":"1989","unstructured":"R. Cole and O. Zajicek, \u201cThe APRAM: Incorporating Asynchrony into the PRAM Model,\u201d in Proc. of the 1989 ACM Symp. on Parallel Algorithms and Architectures, pp. 170\u2013178, 1989."},{"key":"21_CR8","first-page":"85","volume-title":"Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures","author":"R Cole","year":"1990","unstructured":"R. Cole and O. Zajicek, \u201cThe Expected Advantage of Asynchrony,\u201d in Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, pp. 85\u201394, 1990."},{"key":"21_CR9","volume-title":"Faults","author":"R Deprisco","year":"1994","unstructured":"R. DePrisco, A. Mayer, M. Yung, \u201cTime-Optimal Message-Efficient Work Performance in the Presence of Faults,\u201d to appear in PODC, 1994."},{"key":"21_CR10","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/135419.135439","volume-title":"Proc. 11th ACM Symposium on Principles of Distributed Computing","author":"C Dwork","year":"1992","unstructured":"C. Dwork, J. Halpern, O. Waarts, \u201cAccomplishing Work in the Presence of Failures\u201d in Proc. 11th ACM Symposium on Principles of Distributed Computing, pp. 91\u2013102, 1992."},{"key":"21_CR11","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D Eppstein","year":"1988","unstructured":"D. Eppstein and Z. Galil, \u201cParallel Techniques for Combinatorial Computation\u201d, Annual Computer Science Review, 3 (1988), pp. 233\u201383.","journal-title":"Computer Science Review"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie, \u201cParallelism in Random Access Machines\u201d, Proc. the 10th ACM Symposium on Theory of Computing, pp. 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"key":"21_CR13","first-page":"158","volume-title":"Proc. of the Symposium on Parallel Algorithms","author":"P Gibbons","year":"1989","unstructured":"P. Gibbons, \u201cA More Practical PRAM Model,\u201d in Proc. of the 1989 ACM Symposium on Parallel Algorithms and Architectures, pp. 158\u2013168, 1989."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis, D. Michailidis, A. A. Shvartsman, \u201cControlling Memory Access Concurrency in Efficient Fault-Tolerant Parallel Algorithms\u201d, 7th Intl Workshop on Distributed Algorithms pp. 99\u2013114, 1993. An extended version appears as TR CS-94\u201323, Brown University.","DOI":"10.1007\/3-540-57271-6_30"},{"key":"21_CR15","first-page":"211","volume-title":"Proc. of the 8th ACM PODC","author":"PC Kanellakis","year":"1989","unstructured":"P. C. Kanellakis and A. A. Shvartsman, \u201cEfficient Parallel Algorithms Can Be Made Robust\u201d, Distributed Computing, vol. 5, no. 4, pp. 201\u2013217, 1992; prelim. vers. in Proc. of the 8th ACM PODC, pp. 211\u2013222, 1989."},{"key":"21_CR16","volume-title":"Proc. of the 10th ACM Symposium on Principles of Distributed Computing","author":"PC Kanellakis","year":"1991","unstructured":"P. C. Kanellakis and A. A. Shvartsman, \u201cEfficient Parallel Algorithms On Restartable Fail-Stop Processors\u201d, in Proc. of the 10th ACM Symposium on Principles of Distributed Computing, 1991."},{"key":"21_CR17","first-page":"55","volume-title":"Proc. of the Second Annual ONR Workshop on Ultradependable Multicomputers, Office of Naval Research","author":"PC Kanellakis","year":"1991","unstructured":"P. C. Kanellakis and A. A. Shvartsman, \u201cRobust Computing with Fail-Stop Processors\u201d, in Proc. of the Second Annual ONR Workshop on Ultradependable Multicomputers, Office of Naval Research, pp. 55\u201360, 1991."},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis and A. A. Shvartsman, \u201cFault Tolerance and Efficiency in Massively Parallel Algorithms\u201d, in Foundations of Dependable Computing vol. II, chapter 2.2, G. Koob, C. Lau (editors), Kluwer, 1994 (to appear).","DOI":"10.21236\/ADA283255"},{"key":"21_CR19","volume-title":"Handbook of Theoretical Computer Science (ed. J. van Leeuwen), vol. 1, North-Holland","author":"RM Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran, \u201cA Survey of Parallel Algorithms for Shared-Memory Machines\u201d, in Handbook of Theoretical Computer Science (ed. J. van Leeuwen), vol. 1, North-Holland, 1990."},{"key":"21_CR20","first-page":"306","volume-title":"Proc. 24th ACM Symp. on Theory of Comp.","author":"ZM Kedem","year":"1992","unstructured":"Z. M. Kedem, K. V. Palem, M. O. Rabin, A. Raghunathan, \u201cEfficient Program Transformations for Resilient Parallel Computation via Randomization,\u201d in Proc. 24th ACM Symp. on Theory of Comp., pp. 306\u2013318, 1992."},{"key":"21_CR21","first-page":"381","volume-title":"Proc 23d ACM. Symposium on Theory of Computing","author":"ZM Kedem","year":"1991","unstructured":"Z. M. Kedem, K. V. Palem, A. Raghunathan, and P. Spirakis, \u201cCombining Tentative and Definite Executions for Dependable Parallel Computing,\u201d in Proc 23d ACM. Symposium on Theory of Computing, pp. 381\u2013390, 1991."},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Z. M. Kedem, K. V. Palem, and P. Spirakis, \u201cEfficient Robust Parallel Computations,\u201d Proc. 22nd ACM Symp. on Theory of Computing, pp. 138\u2013148, 1990.","DOI":"10.1145\/100216.100231"},{"key":"21_CR23","first-page":"579","volume-title":"ACM Trans. on Programming Languages and Systems, vol. 10, no. 4","author":"CP Kruskal","year":"1988","unstructured":"C. P. Kruskal, L. Rudolph, M. Snir, \u201cEfficient Synchronization on Multiprocessors with Shared Memory,\u201d in ACM Trans. on Programming Languages and Systems, vol. 10, no. 4, pp. 579\u2013601 1988."},{"key":"21_CR24","volume-title":"March","author":"C","year":"1991","unstructured":"C. Martel, personal communication, March, 1991."},{"key":"21_CR25","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1137\/0221063","volume":"21","author":"C Martel","year":"1992","unstructured":"C. Martel, A. Park, and R. Subramonian, \u201cWork-optimal Asynchronous Algorithms for Shared Memory Parallel Computers,\u201d SIAM Journal on Computing, vol. 21, pp. 1070\u20131099, 1992","journal-title":"SIAM Journal on Computing"},{"key":"21_CR26","volume-title":"\u201cOn the Complexity of Certified Write-All Algorithms\u201d, to appear in Journal of Algorithms (a prel. version in the Proc. of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"C Martel","year":"1992","unstructured":"C. Martel and R. Subramonian, \u201cOn the Complexity of Certified Write-All Algorithms\u201d, to appear in Journal of Algorithms (a prel. version in the Proc. of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, December 1992 )."},{"key":"21_CR27","first-page":"590","volume-title":"Proc. 32d IEEE Symposium on Foundations of Computer Science","author":"C Martel","year":"1990","unstructured":"C. Martel, R. Subramonian, and A. Park, \u201cAsynchronous PRAMs are (Almost) as Good as Synchronous PRAMs,\u201d in Proc. 32d IEEE Symposium on Foundations of Computer Science, pp. 590\u2013599, 1990."},{"key":"21_CR28","volume-title":"Measuresmanuscript","author":"J Naor","year":"1993","unstructured":"J. Naor, R.M. Roth, \u201cConstructions of Permutation Arrays for Ceratin Scheduling Cost Measures\u201d, manuscript, 1993."},{"key":"21_CR29","first-page":"76","volume-title":"Proc Symp. on Parallel Algor","author":"N Nishimura","year":"1990","unstructured":"N. Nishimura, \u201cAsynchronous Shared Memory Parallel Computation,\u201d in Proc. 3rd ACM Symp. on Parallel Algor. and Architect., pp. 76\u201384, 1990."},{"issue":"2","key":"21_CR30","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/62044.62050","volume":"36","author":"MO Rabin","year":"1989","unstructured":"M.O. Rabin, \u201cEfficient Dispersal of Information for Security, Load Balancing and Fault Tolerance\u201d, J. of ACM, vol. 36, no. 2, pp. 335\u2013348, 1989.","journal-title":"J. of ACM"},{"issue":"8","key":"21_CR31","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1109\/MC.1984.1659217","volume":"17","author":"DB Sarrazin","year":"1984","unstructured":"D. B. Sarrazin and M. Malek, \u201cFault-Tolerant Semiconductor Memories\u201d, IEEE Computer, vol. 17, no. 8, pp. 49\u201356, 1984.","journal-title":"IEEE Computer"},{"issue":"3","key":"21_CR32","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1145\/357369.357371","volume":"1","author":"RD Schlichting","year":"1983","unstructured":"R. D. Schlichting and F. B. Schneider, \u201cFail-Stop Processors: an Approach to Designing Fault-tolerant Computing Systems\u201d, ACM Transactions on Computer Systems, vol. 1, no. 3, pp. 222\u2013238, 1983.","journal-title":"ACM Transactions on Computer Systems"},{"issue":"4","key":"21_CR33","first-page":"484","volume":"2","author":"JT Schwartz","year":"1980","unstructured":"J. T. Schwartz, \u201cUltracomputers\u201d, ACM Transactions on Programming Languages and Systems, vol. 2, no. 4, pp. 484\u2013521, 1980.","journal-title":"Systems"},{"issue":"2","key":"21_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(91)90156-C","volume":"39","author":"AA Shvartsman","year":"1991","unstructured":"A. A. Shvartsman, \u201cAchieving Optimal CRCW PRAM Fault Tolerance\u201d, Information Processing Letters, vol. 39, no. 2, pp. 59\u201366, 1991.","journal-title":"Information Processing Letters"},{"key":"21_CR35","unstructured":"A. A. Shvartsman, Fault-Tolerant and Efficient Parallel Computation, Ph.D. dissertation, Brown University, Tech. Rep. CS-92\u201323, 1992."},{"issue":"6","key":"21_CR36","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0020-0190(92)90090-I","volume":"44","author":"AA Shvartsman","year":"1992","unstructured":"A. A. Shvartsman, \u201cEfficient Write-All Algorithm for Fail-Stop PRAM Without Initialized Memory\u201d, Information Processing Letters, vol. 44, no. 6, pp. 223\u2013231, 1992.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","CONCUR '94: Concurrency Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-48654-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T00:47:49Z","timestamp":1692319669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-48654-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583295","9783540486541"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-48654-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}