{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T06:43:53Z","timestamp":1707374633785},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf02523194","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:41:28Z","timestamp":1162960888000},"page":"308-321","source":"Crossref","is-referenced-by-count":0,"title":["The complexity of almost-optimal simultaneous coordination"],"prefix":"10.1007","volume":"17","author":[{"given":"R. A.","family":"Bazzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Neiger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523194_CR1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1145\/135419.135460","volume-title":"Proceedings of the Eleventh ACM Symposium on Principles of Distributed Computing","author":"R. A. Bazzi","year":"1992","unstructured":"R. A. Bazzi and G. Neiger. The complexity and impossibility of achieving fault-tolerant coordination. InProceedings of the Eleventh ACM Symposium on Principles of Distributed Computing, pages 203\u2013214. ACM Press, New York, August 1992."},{"key":"BF02523194_CR2","doi-asserted-by":"crossref","unstructured":"R. A. Bazzi and G. Neiger. Simplifying fault-tolerance: Providing the abstraction of crash failures. Technical Report 93\/12, College of computing, Georgia Institute of Technology, February 1993. Earlier versions of parts of this paper appeared as \u201cOptimally Simulating Crash Failures in a Byzantine Environment\u201d in S. Toeug, P. G. Spirakis, and L. Kirousis, editors,Proceedings of the Fifth International Workshop on Distributed Algorithms, of Lecture Notes on Computer Science, volume 579, pages 108\u2013128. Springer-Verlag, Berlin, October 1991, and as \u201cSimulating Crash Failures with Many Faulty Processors\u201d in A. Segall and S. Zaks, editors,Proceedings of the Sixth International Workshop on Distributed Algorithms, Lecture Notes on Computer Science, volume 647, pages 166\u2013184. Springer-Verlag, Berlin, November 1992.","DOI":"10.1007\/BFb0022441"},{"issue":"1","key":"BF02523194_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01187072","volume":"26","author":"P. Berman","year":"1993","unstructured":"P. Berman and J. A. Garay. Cloture votes:n\/4-resilient, polynomial time distributed consensus int+1 rounds.Mathematical Systems Theory, 26 (1): 3\u201320, 1993.","journal-title":"Mathematical Systems Theory"},{"key":"BF02523194_CR4","first-page":"147","volume":"4","author":"J. E. Burns","year":"1987","unstructured":"J. E. Burns and N. A. Lynch. The Byzantine firing squad problem.Advances in Computing Research: Parallel and Distributed Computing, 4: 147\u2013161, 1987. Also appears as Technical Report 275, MIT Laboratory for Computer Science.","journal-title":"Advances in Computing Research: Parallel and Distributed Computing"},{"key":"BF02523194_CR5","doi-asserted-by":"crossref","unstructured":"B. A. Coan. A communication-efficient canonical form for fault-tolerant distributed protocols. InProceedings of the Fifth ACM Symposium on Principles of Distributed Computing, pages 63\u201372, August 1986. A revised version appears in Coan's Ph.D. dissertation [6].","DOI":"10.1145\/10590.10596"},{"key":"BF02523194_CR6","unstructured":"B. A. Coan. Achieving Consensus in Fault-Tolerant Distributed Computer Systems: Protocols, Lower Bounds and Simulations. Ph.D. dissertation, Massachusetts Institute of Technology, June 1987."},{"issue":"5","key":"BF02523194_CR7","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1137\/0218068","volume":"18","author":"B. A. Coan","year":"1989","unstructured":"B. A. Coan, D. Dolev, C. Dwork, and L. Stockmeyer. The distributed firing squad problem.SIAM Journal on Computing, 18 (5): 990\u20131012, October 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"BF02523194_CR8","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/96559.96565","volume":"37","author":"D. Dolev","year":"1990","unstructured":"D. Dolev, R. Reischuk, and H. R. Strong. Early stopping in Byzantine agreement.Journal of the ACM, 37 (4): 720\u2013741, October 1990.","journal-title":"Journal of the ACM"},{"issue":"2","key":"BF02523194_CR9","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0890-5401(90)90014-9","volume":"88","author":"C. Dwork","year":"1990","unstructured":"C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: Crash failures.Information and Computation, 88 (2): 156\u2013186, October 1990.","journal-title":"Information and Computation"},{"key":"BF02523194_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"BF02523194_CR11","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1145\/28659.28672","volume-title":"Proceedings of the Sixth ACM Symposium on Principles of Database Systems","author":"V. Hadzilacos","year":"1987","unstructured":"V. Hadzilacos. A knowledge theoretic analysis of atomic commitment protocols. InProceedings of the Sixth ACM Symposium on Principles of Database Systems, pages 129\u2013134. ACM Press, New York, March 1987."},{"issue":"3","key":"BF02523194_CR12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/79147.79161","volume":"37","author":"J. Y. Halpern","year":"1990","unstructured":"J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment.Journal of the ACM, 37 (3): 549\u2013587, July 1990.","journal-title":"Journal of the ACM"},{"key":"BF02523194_CR13","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/93385.93437","volume-title":"Proceedings of the Ninth ACM Symposium on Principles of Distributed Computing","author":"J. Y. Halpern","year":"1990","unstructured":"J. Y. Halpern, Y. Moses, and O. Waarts. A characterization of eventual Byzantine agreement. InProceedings of the Ninth ACM Symposium on Principles of Distributed Computing, pages 333\u2013346. ACM Press, New York, August 1990."},{"issue":"3","key":"BF02523194_CR14","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L. Lamport","year":"1982","unstructured":"L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem.ACM Transactions on Programming Languages and Systems, 4 (3): 382\u2013401, July 1982.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"BF02523194_CR15","first-page":"309","volume-title":"Proceedings of the Second Conference on Theoretical Aspects of Reasoning about Knowledge","author":"M. S. Mazer","year":"1988","unstructured":"M. S. Mazer. A knowledge theoretic account of recovery in distributed systems: The case of negotiated commitment. In M. Y. Vardi, editor,Proceedings of the Second Conference on Theoretical Aspects of Reasoning about Knowledge, pages 309\u2013324. Morgan-Kaufmann, Los Altos, CA, March 1988."},{"key":"BF02523194_CR16","unstructured":"R. Michel. Knowledge in Distributed Byzantine Environments. Ph.D. dissertation, Yale University, December 1989."},{"issue":"1","key":"BF02523194_CR17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01762112","volume":"3","author":"Y. Moses","year":"1988","unstructured":"Y. Moses and M. R. Tuttle. Programming simultaneous actions using common knowledge.Algorithmica, 3 (1): 121\u2013169, 1988.","journal-title":"Algorithmica"},{"key":"BF02523194_CR18","first-page":"43","volume-title":"Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning about Knowledge","author":"G. Neiger","year":"1992","unstructured":"G. Neiger and R. Bazzi. Using knowledge to optimally achieve coordination in distributed systems. In Y. Moses, editor,Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning about Knowledge, pages 43\u201359. Morgan-Kaufmann, Los Altos, CA, March 1992."},{"issue":"3","key":"BF02523194_CR19","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0196-6774(90)90019-B","volume":"11","author":"G. Neiger","year":"1990","unstructured":"G. Neiger and S. Toueg. Automatically increasing the fault-tolerance of distributed algorithms.Journal of Algorithms, 11 (3): 374\u2013419, September 1990.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"BF02523194_CR20","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1145\/151261.151267","volume":"40","author":"G. Neiger","year":"1993","unstructured":"G. Neiger and S. Toueg. Simulating synchronized clocks and common knowledge in distributed systems.Journal of the ACM, 40 (2): 334\u2013367, April 1993.","journal-title":"Journal of the ACM"},{"issue":"3","key":"BF02523194_CR21","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02242706","volume":"6","author":"G. Neiger","year":"1993","unstructured":"G. Neiger and M. R. Tuttle. Common knowledge and consistent simultaneous coordination.Distributed Computing, 6 (3): 181\u2013192, April 1993.","journal-title":"Distributed Computing"},{"issue":"2","key":"BF02523194_CR22","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M. Pease","year":"1980","unstructured":"M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults.Journal of the ACM, 27 (2): 228\u2013234, April 1980.","journal-title":"Journal of the ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523194.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523194\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T05:58:43Z","timestamp":1707371923000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02523194"],"URL":"https:\/\/doi.org\/10.1007\/bf02523194","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}