{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:58:37Z","timestamp":1787497117730,"version":"build-2736575974"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1992,4,1]],"date-time":"1992-04-01T00:00:00Z","timestamp":702086400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib Comput"],"published-print":{"date-parts":[[1992,4]]},"DOI":"10.1007\/bf02277667","type":"journal-article","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T12:44:56Z","timestamp":1138193096000},"page":"201-217","source":"Crossref","is-referenced-by-count":43,"title":["Efficient parallel algorithms can be made robust"],"prefix":"10.1007","volume":"5","author":[{"given":"Paris C.","family":"Kanellakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex A.","family":"Shvartsman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02277667_CR1","doi-asserted-by":"crossref","unstructured":"Afek Y, Awerbuch B, Gafni E: Applying static network protocols to dynamic networks. Proceedings of 28th IEEE Symp on Foundation of Computer Science, 1987, pp 358\u2013370","DOI":"10.1109\/SFCS.1987.7"},{"key":"BF02277667_CR2","doi-asserted-by":"crossref","unstructured":"Afek Y, Awerbuch B, Plotkin S, Saks M: Local management of a global resource in a communication network. Proceedings of 28th IEEE Symp on Foundation of Computer Science, 1987a, pp 347\u2013357","DOI":"10.1109\/SFCS.1987.38"},{"key":"BF02277667_CR3","doi-asserted-by":"crossref","unstructured":"Assaf S, Upfal E: Fault tolerant sorting network. Proceedings of 31st IEEE Symp on Foundation of Computer Science, 1990, pp 275\u2013284","DOI":"10.1109\/FSCS.1990.89546"},{"key":"BF02277667_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch B: On the effects of feedback in dynamic network protocols. Proceedings of 29th IEEE Symp on Foundation of Computer Science, 1988, pp 231\u2013242","DOI":"10.1109\/SFCS.1988.21940"},{"key":"BF02277667_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Sipser M: Dynamic networks are as fast as static networks. Proceedings of 29th IEEE Symp on Foundation of Computer Science, 1988, pp 206\u2013219","DOI":"10.1109\/SFCS.1988.21938"},{"key":"BF02277667_CR6","first-page":"307","volume":"32","author":"KE Batcher","year":"1968","unstructured":"Batcher KE: Sorting networks and their applications. Proceedings of Spring Joint Computer Conference 32:307\u2013314 (1968)","journal-title":"Proceedings of Spring Joint Computer Conference"},{"issue":"2","key":"BF02277667_CR7","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/65950.65958","volume":"36","author":"P Beame","year":"1989","unstructured":"Beame P, Hastad J: Optimal bounds for decision problems on the CRCW PRAM. J Assoc Comput Mach 36(2):643\u2013670 (1989)","journal-title":"J Assoc Comput Mach"},{"issue":"12","key":"BF02277667_CR8","doi-asserted-by":"crossref","first-page":"1506","DOI":"10.1109\/12.9729","volume":"37","author":"B Bloom","year":"1988","unstructured":"Bloom B: Constructing two-writer atomic registers. IEEE Trans Comput 37(12):1506\u20131514 (1988)","journal-title":"IEEE Trans Comput"},{"key":"BF02277667_CR9","doi-asserted-by":"crossref","unstructured":"Cole R, Zajicek O: The APRAM: incorporating asynchrony into the PRAM model. Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, 1989, pp 170\u2013178","DOI":"10.1145\/72935.72954"},{"key":"BF02277667_CR10","doi-asserted-by":"crossref","unstructured":"Cole R, Zajicek O: The expected advantage of asynchrony. Proceedings of 2nd ACM Symposium on Parallel Algorithms and Architectures, 1990, pp 85\u201394","DOI":"10.1145\/97444.97673"},{"key":"BF02277667_CR11","unstructured":"Dijkstra EW: The discipline of programming. Prentice-Hall 1976"},{"key":"BF02277667_CR12","doi-asserted-by":"crossref","unstructured":"Dolev D, Dwork C, Stockmeyer L: On the minimal synchronism needed for distributed consensus. Proceedings of 24th IEEE Symp on Foundation of Computer Science, 1983, pp 393\u2013402","DOI":"10.1109\/SFCS.1983.41"},{"key":"BF02277667_CR13","doi-asserted-by":"crossref","unstructured":"Dwork C, Peleg D, Pippinger N, Upfal E: Fault tolerance in networks of bounded degree. Proceedings of 18th ACM STOC, 1986, pp 370\u2013379","DOI":"10.1145\/12130.12169"},{"key":"BF02277667_CR14","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D Eppstein","year":"1988","unstructured":"Eppstein D, Galil Z: Parallel techniques for combinatorial computation. Annual Computer Science Review 3:233\u201383 (1988)","journal-title":"Annual Computer Science Review"},{"key":"BF02277667_CR15","doi-asserted-by":"crossref","unstructured":"Fischer MJ: The consensus problem in unreliable distributed systems (a brief survey). Yale University Tech Rep, DCS\/RR-273, 1983","DOI":"10.1007\/3-540-12689-9_99"},{"issue":"4","key":"BF02277667_CR16","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(82)90033-3","volume":"14","author":"MJ Fischer","year":"1982","unstructured":"Fischer MJ, Lynch NA: A lower bound for the time to assure interactive consistency. IPL 14(4):183\u2013186 (1982)","journal-title":"IPL"},{"issue":"2","key":"BF02277667_CR17","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer MJ, Lynch NA, Paterson MS: Impossibility of distributed consensus with one faulty process. J Assoc Comput Mach 32(2):374\u2013382 (1985)","journal-title":"J Assoc Comput Mach"},{"key":"BF02277667_CR18","doi-asserted-by":"crossref","unstructured":"Fortune S, Wyllie J: Parallelism in random access machines. Proceedings of 10th ACM STOC, 1978, pp 114\u2013118","DOI":"10.1145\/800133.804339"},{"key":"BF02277667_CR19","doi-asserted-by":"crossref","unstructured":"Gibbons P: A more practical PRAM model. Proceedings of 1989 ACM Symposium on Parallel Algorithms and Architectures, 1989, pp 158\u2013168","DOI":"10.1145\/72935.72953"},{"key":"BF02277667_CR20","doi-asserted-by":"crossref","unstructured":"Graham R, Knuth D, Patashnik O: Concrete mathematics: a foundation for computer science. Addison-Wesley, 1989","DOI":"10.1063\/1.4822863"},{"key":"BF02277667_CR21","doi-asserted-by":"crossref","unstructured":"Hornick SW, Preparata FP: Deterministic P-RAM: simulation with constant redundancy. Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Arch 1989, pp 103\u2013109","DOI":"10.1145\/72935.72947"},{"key":"BF02277667_CR22","doi-asserted-by":"crossref","unstructured":"Kaklamanis C, Karlin A, Leighton T, Milenkovic V, Raghavan P, Rao S, Thomborson C, Tsantilas A: Asymptotically tight bounds for computing with arrays of processors. Proceedings of 31st IEEE Symp on Foundation of Computer Science, 1990, pp 285\u2013296","DOI":"10.1109\/FSCS.1990.89547"},{"key":"BF02277667_CR23","doi-asserted-by":"crossref","unstructured":"Kanellakis PC, Shvartsman AA: Efficient parallel algorithms can be made robust. Proceedings of 8th ACM PODC, 1989, pp 211\u2013222","DOI":"10.1145\/72981.72996"},{"key":"BF02277667_CR24","doi-asserted-by":"crossref","unstructured":"Kanellakis PC, Shvartsman AA: Efficient parallel algorithms on restartable fail-stop processors. Proceedings of 10th ACM PODC, 1991, pp 23\u201336","DOI":"10.21236\/ADA236249"},{"key":"BF02277667_CR25","volume-title":"Handbook of theoretical computer science","author":"RM Karp","year":"1990","unstructured":"Karp RM, Ramachandran V: A Survey of parallel algorithms for shared-memory machines. In: van Leeuwen J (ed) Handbook of theoretical computer science. Elsevier, Amsterdam 1990"},{"key":"BF02277667_CR26","doi-asserted-by":"crossref","unstructured":"Kedem ZM, Palem KV, Spirakis P: Efficient robust parallel computations. Proceedings of 22nd ACM STOC, 1990, pp 138\u2013148","DOI":"10.1145\/100216.100231"},{"key":"BF02277667_CR27","doi-asserted-by":"crossref","unstructured":"Kedem ZM, Palem KV, Raghunathan A, Spirakis P: Combining tentative and definite executions for dependable parallel computing. Proceedings of 23d ACM STOC 1991, pp 381\u2013390","DOI":"10.1145\/103418.103459"},{"key":"BF02277667_CR28","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0019-9958(86)80028-6","volume":"68","author":"NA Lynch","year":"1986","unstructured":"Lynch NA, Griffeth ND, Fischer MJ, Guibas LJ: Probabilistic analysis of a network resource allocation algorithm. Inf Control 68:47\u201385 (1986)","journal-title":"Inf Control"},{"key":"BF02277667_CR29","doi-asserted-by":"crossref","unstructured":"Lynch NA: A hundred impossibility proofs for distributed computing. Proceedings of 8th ACM PODC, 1989, pp 1\u201327","DOI":"10.1145\/72981.72982"},{"key":"BF02277667_CR30","unstructured":"Martel C: Personal communication, March, 1991"},{"key":"BF02277667_CR31","doi-asserted-by":"crossref","unstructured":"Martel C, Subramonian R, Park A: Asynchronous PRAMs are (almost) as good as synchronous PRAMs. Proceedings of 32d IEEE Symposium on Foundation of Computer Sciences, 1990, pp 590\u2013599","DOI":"10.1109\/FSCS.1990.89580"},{"key":"BF02277667_CR32","doi-asserted-by":"crossref","unstructured":"Nishimura N: Asynchronous shared memory parallel computation. Proceedings of 3rd ACM Symposium on Parallel Algorithms and Architectures, 1990, pp 76\u201384","DOI":"10.1145\/97444.97672"},{"issue":"2","key":"BF02277667_CR33","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M Pease","year":"1980","unstructured":"Pease M, Shostak R, Lamport L: Reaching agreement in the presence of faults. J Assoc Comput Mach 27(2):228\u2013234 (1980)","journal-title":"J Assoc Comput Mach"},{"key":"BF02277667_CR34","doi-asserted-by":"crossref","unstructured":"Pippinger N: On networks of noisy gates. Proceedings of 26th IEEE Symp on Foundation of Computer Science, 1985, pp 30\u201338","DOI":"10.1109\/SFCS.1985.41"},{"key":"BF02277667_CR35","doi-asserted-by":"crossref","unstructured":"Ranade A: How to emulate shared memory. Proceedings of 28th IEEE Symp on Foundation of Computer Science, 1987, pp 185\u2013194","DOI":"10.1109\/SFCS.1987.32"},{"issue":"4","key":"BF02277667_CR36","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1109\/TC.1985.5009383","volume":"34","author":"L Rudolph","year":"1985","unstructured":"Rudolph L: A robust sorting network. IEEE Trans Comp c-34(4):326\u2013335 (1985)","journal-title":"IEEE Trans Comp"},{"issue":"3","key":"BF02277667_CR37","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1145\/357369.357371","volume":"1","author":"RD Schlichting","year":"1983","unstructured":"Schlichting RD, Schneider FB: Fail-stop processors: an approach to designing fault-tolerant computing systems. ACM Trans Comput Syst 1(3):222\u2013238 (1983)","journal-title":"ACM Trans Comput Syst"},{"key":"BF02277667_CR38","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0020-0190(91)90156-C","volume":"39","author":"AA Shvartsman","year":"1991","unstructured":"Shvartsman AA: Achieving optimal CRCW PRAM fault-tolerance. Inf Process Lett 39:59\u201366 (1991)","journal-title":"Inf Process Lett"},{"key":"BF02277667_CR39","doi-asserted-by":"crossref","unstructured":"Tarjan RE, Vishkin U: Finding biconnected components and computing tree functions in logarithmic parallel time. Proceedings of 25th IEEE Symp on Foundation of Computer Science, 1984, pp 12\u201322","DOI":"10.1109\/SFCS.1984.715896"},{"key":"BF02277667_CR40","doi-asserted-by":"crossref","unstructured":"Upfal E: AnO(logN) deterministic packet routing scheme. Proceedings of 21st ACM STOC, 1989, pp 241\u2013250","DOI":"10.1145\/73007.73030"},{"key":"BF02277667_CR41","volume-title":"Handbook of theoretical computer science","author":"L Valiant","year":"1990","unstructured":"Valiant L: General purpose parallel architectures. In: van Leeuwen J (ed) Handbook of theoretical computer science. Elsevier, Amsterdam 1990"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02277667.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02277667\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02277667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T07:38:32Z","timestamp":1736235512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02277667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,4]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,4]]}},"alternative-id":["BF02277667"],"URL":"https:\/\/doi.org\/10.1007\/bf02277667","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,4]]}}}