{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:12:48Z","timestamp":1725459168871},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540619949"},{"type":"electronic","value":"9783540495888"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0037411","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T15:15:55Z","timestamp":1138202155000},"page":"286-306","source":"Crossref","is-referenced-by-count":0,"title":["Scalable fault tolerance"],"prefix":"10.1007","author":[{"given":"Shay","family":"Kutten","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,26]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying static network protocols to dynamic networks. In Proc. 28th IEEE Symp. on Foundations of Computer Science, October 1987.","DOI":"10.1109\/SFCS.1987.7"},{"key":"19_CR2","unstructured":"B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour, and D. Peleg, Broadcasting with Partial Knowledge. to appear in SIAM Journal on Computing."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"H. Attiya, C. Dwork, N. Lynch, and L. Stockmeyer. Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. In 23rd ACM Symposium on Theory of Computing, New Orleans, Louisiana, pp. 359\u2013369, May 1991.","DOI":"10.1145\/103418.103457"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"S. Aggarwal. Time optimal selfstabilizing spanning tree algorithms. M.Sc Thesis, MIT, May 1994.","DOI":"10.1007\/3-540-57529-4_72"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Goldberg, M. Luby and S. Plotkin. Network decomposition and locality in distributed computation, Proc. 30th Symp. on Foundations of Computer Science, pp. 364\u2013375, October 1989.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, B. Patt-Shamir, and G. Varghese. Self-stabilization by local checking and correction. In Proc. 32nd IEEE Symp. on Foundation of Computer Science, 268\u2013277, 1991.","DOI":"10.1109\/SFCS.1991.185378"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Y. Afek, S. Kutten, and M. Yung. Memory-efficient self stabilizing protocols for general networks. In Proc. 4th Int. Workshop on Distributed Algorithms, S-V LNCS, September 1990.","DOI":"10.1007\/3-540-54099-7_2"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir and G. Varghese, Time-Optimal Self Stabilizing Synchronization, Proc. 1993 ACM Symp. on Theory of Computing, San Diego, California, pp. 652\u2013661, May 1993.","DOI":"10.1145\/167088.167256"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and R. Ostrovsky. Memory efficient and self stabilizing network reset. In Proc. 14th ACM Symp. on Principles of Distributed Computing (PODC), August 1994.","DOI":"10.1145\/197917.198104"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, B. Patt-Shamir, G. Varghese, and S. Dolev. Self stabilization by local checking and global reset. in the Proc. of WDAG 94, Springer-Verlag LNCS, pages 226\u2013239, October 1994.","DOI":"10.1007\/BFb0020443"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, and G. Varghese. Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In Proc. of the 32nd IEEE Ann. Symp. on Foundation of Computer Science, pages 258\u2013267, October 1991.","DOI":"10.1109\/SFCS.1991.185377"},{"volume-title":"Internetworking with TCP\/IP","year":"1991","author":"D. E. Comer","key":"19_CR12","unstructured":"D. E. Comer. Internetworking with TCP\/IP. Prantice Hall, New Jersey, US, 1991."},{"key":"19_CR13","series-title":"LNCS (647)","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/3-540-56188-9_15","volume-title":"Proceedings of International Workshop on Distributed Algorithms (WDAG)","author":"P. Berman","year":"1992","unstructured":"P. Berman, J. Garay, and K. Perry. Optimal Early Stopping in Distributed Consensus. In Proceedings of International Workshop on Distributed Algorithms (WDAG), Haifa, Israel, LNCS (647), Springer-Verlag, pp. 221\u2013237, November 1992."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy and S. Kipnis, Designing broadcasting algorithms in the postal model for message-passing systems. invited paper, to appear in Mathematical Systems Theory, 1994. Also Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, ACM, June 1992, pp. 13\u201322.","DOI":"10.1145\/140901.140903"},{"key":"19_CR15","first-page":"173","volume-title":"Proc. 2nd Colloq. on Structural Information & Communication Complexity","author":"J-C. Bermond","year":"1995","unstructured":"J-C. Bermond and D. Peleg. The Power of Small Coalitions in Graphs. Proc. 2nd Colloq. on Structural Information & Communication Complexity, Olympia, Greece, June 1995, Carleton Univ. Press, 173\u2013184."},{"key":"19_CR16","unstructured":"J-C. Bermond, J. Bond, D. Peleg, and S. Perennes. Tight bounds on the size of 2-monopolies. Proc. 3rd Colloq. on Structural Information & Communication Complexity, Siena, Italy, June 1996."},{"issue":"5","key":"19_CR17","doi-asserted-by":"crossref","first-page":"1950","DOI":"10.1109\/26.387408","volume":"43","author":"I. Cidon","year":"1995","unstructured":"I. Cidon, I. Gopal, M. Kaplan and S. Kutten. Distributed Control for Fast Networks. IEEE Trans. on Communications, Vol. 43(5), pp. 1950\u20131960, May 1995. 1. D. Culler, R.M. Karp, D. Patterson, A. Sahay, K.E. Schauser, E. Santos, R. Subramonian and T. von Eicken. LogP: towards a realistic model of parallel computation. Proc. 4th SIGPLAN Symp. on Principles and Practices of Parallel Programming, ACM, May 1993.","journal-title":"IEEE Trans. on Communications"},{"key":"19_CR18","unstructured":"S. Ghosh and A. Gupta. An exercise in Fault Containment: Leader Election in a Ring. to appear in Information Processing Letters."},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"S. Ghosh, A. Gupta, T. Herman, and S.V. Pemmaraju Fault-Containing Self-Stabilizing Algorithms. In Proc. 15th Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23\u201326, 1996, pp. 45\u201354.","DOI":"10.1145\/248052.248057"},{"issue":"No.1","key":"19_CR20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/214451.214456","volume":"3","author":"M.M. Chandy","year":"1985","unstructured":"M.M. Chandy and L. Lamport. Distributed Snapshots: Determining Global States of Distributed Systems. Transactions on Computer Systems, Vol. 3, No. 1, 1985, pp. 63\u201375.","journal-title":"Transactions on Computer Systems"},{"issue":"No.1","key":"19_CR21","first-page":"322","volume":"2","author":"S. Ghosh","year":"1996","unstructured":"S. Ghosh, A. Gupta, and S. V. Pemmaraju. A Fault-Containing Self-Stabilizing Spanning Tree Algorithm. Journal of Computing and Information Vol. 2, No. 1, 1996, pp. 322\u2013338 (Special issue on the Proceedings of the Eighth International Conference of Computing and Information, Waterloo, Ontario, Canada, June 18\u201322, 1996.)","journal-title":"Journal of Computing and Information"},{"issue":"NO6","key":"19_CR22","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1109\/TC.1987.1676965","volume":"C-36","author":"I. Chlamtac","year":"1987","unstructured":"I. Chlamtac, and S. Pinter. Distributed Node Organization Algorithm for Channel Access in a Multihop Dynamic Radio Network. IEEE Transactions on Computers, VOL. C-36, NO 6, June 1987, pp. 728\u2013737.","journal-title":"IEEE Transactions on Computers"},{"key":"19_CR23","unstructured":"I. Chlamtac and S. Kutten. A Spatial Reuse TDMA\/FDMA for Mobile Multihop Radio Networks. IEEE INFOCOM 85, Washington, DC, USA, March 1985."},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"S. Dolev and T. Herman. SuperStabilizing Protocols for Dynamic Distributed Systems. In 2nd Workshop on Self-Stabilizing Systems. Las Vegas, Nevada, May 1995.","DOI":"10.1145\/224964.224993"},{"key":"19_CR25","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E. W. Dijkstra","year":"1974","unstructured":"E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communication of the ACM, 17:643\u2013644, November 1974.","journal-title":"Communication of the ACM"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"S. Dolev, A. Israeli, and S. Moran. Self-stabilization of dynamic systems assuming only read\/write atomicity. Distributed Computing Journal, 7, 1994. also In Proc. 9th ACM Symp. on Principles of Distributed Computing, August 1990.","DOI":"10.1145\/93385.93407"},{"issue":"No.4","key":"19_CR27","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 R. Strong, Early Stopping in Byz. Agreement. JACM Vol. 37, No. 4 (1990), pp. 720\u2013741.","journal-title":"JACM"},{"issue":"6","key":"19_CR28","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1109\/TCOM.1979.1094473","volume":"COM-27","author":"S. G. Finn","year":"1979","unstructured":"Steven G. Finn. Resynch procedures and a fail-safe network protocol. IEEE Trans. on Communications, COM-27(6):840\u2013845, June 1979.","journal-title":"IEEE Trans. on Communications"},{"key":"19_CR29","unstructured":"R.E. Gallager. Choosing a Leader in a Network. unpublished memorandum, M.I.T."},{"key":"19_CR30","unstructured":"Eli Gafni. Topology resynchronization: A new paradigm for fault tolerance in distributed algorithms. In Proceedings of the Amsterdam Workshop on Distributed Algorithms. CWI, July 1987."},{"key":"19_CR31","unstructured":"T. Herman. Superstabilizing Mutual Exclusion. International Conference on Parallel and Distributed Systems, Athens, GA, 1995."},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"A. Herzberg and S. Kutten. Fast Isolation of Faults in Data Transfer. Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC 89), Edmonton, Canada, pp. 349\u2013353, August 1989.","DOI":"10.1145\/72981.73006"},{"key":"19_CR33","unstructured":"S. Katz and K. J. Perry. Self-stabilizing extensions. In Proc. 9th ACM Symp. on Principles of Distributed Computing, August 1990."},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"S. Kutten and D. Peleg. Fault-Local Mending. Proceedings of the Fourteenth Annual ACM Symposium on Principle of Distributed Computing (PODC 95), Ottawa, Canada, pp. 20\u201327, August 1995.","DOI":"10.1145\/224964.224967"},{"key":"19_CR35","doi-asserted-by":"crossref","unstructured":"S. Kutten and D. Peleg. Tight Fault-locality. In Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995.","DOI":"10.1109\/SFCS.1995.492672"},{"key":"19_CR36","unstructured":"S. Kutten and B. Patt-Shamir Fault-Local Self-Stabilization, In preparation."},{"key":"19_CR37","doi-asserted-by":"crossref","unstructured":"R.M. Karp, A. Sahay, E. Santos, and K. E. Schauser. Optimal broadcast and summation in the LogP model. Proc. 5th Symp. on Parallel Algorithms and Architectures, ACM, June 1993, pp 142\u2013153.","DOI":"10.1145\/165231.165250"},{"key":"19_CR38","unstructured":"G. Le-Lann Distributed Systemstowards a Formal Approach. Information Processing 77 (ed. B. Gilchrist). pp. 155\u2013160, North-Holland 1977."},{"issue":"4","key":"19_CR39","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 15(4):1036\u20131053, November 1986.","journal-title":"SIAM J. Comput."},{"key":"19_CR40","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"N. Linial, Locality in distributed graph algorithms, SIAM J. Comput., 21:193\u2013201, 1992.","journal-title":"SIAM J. Comput."},{"key":"19_CR41","doi-asserted-by":"crossref","unstructured":"N. Linial, D. Peleg, Y. Rabinovich and M. Saks, Sphere Packing and Local Majorities in Graphs, Proc. 2nd Israel Symp. on Theory of Computing and Systems, Natanya, Israel, June 1993, 141\u2013149.","DOI":"10.1109\/ISTCS.1993.253475"},{"issue":"No.3","key":"19_CR42","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L. Lamport","year":"1982","unstructured":"L. Lamport, R.E. Shostak and M. Pease. The Byzantine Generals Problem. ACM ToPLaS, Vol. 4, No. 3, pp. 382\u2013401, July 1982.","journal-title":"ACM ToPLaS"},{"key":"19_CR43","unstructured":"A. Mayer, S. Naor, and L. Stockmeyer Local Computations on Static and Dynamic Graphs In Proceedings of the 3rd Israel Symposium on Theory and Computing Systems (ISTCS), 1995."},{"key":"19_CR44","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1109\/TCOM.1980.1094721","volume":"COM-28","author":"J. M. McQuillan","year":"1980","unstructured":"J. M. McQuillan, I. Richer and E. C. Rosen, The New Routing Algorithm for the ARPANET. IEEE Trans. on Communications, COM-28, May 1980, pp. 711\u2013719.","journal-title":"IEEE Trans. on Communications"},{"key":"19_CR45","doi-asserted-by":"crossref","unstructured":"M. Naor and L. Stockmeyer, What Can Be Computed Locally? In Proc. of the 25th ACM Symp. on the Theory of Computing, San Diego, California, May 1993, pp. 184\u2013193.","DOI":"10.1145\/167088.167149"},{"key":"19_CR46","unstructured":"R. Perlman. Interconnections: Bridges and Routers. Addison Welsley, 1992."},{"key":"19_CR47","unstructured":"D. Peleg. Local Majority Voting, Small Coalitions and Controlling Monopolies in Graphs: A Review. Proc. 3rd Colloq. on Structural Information & Communication Complexity, Siena, Italy, June 1996."},{"key":"19_CR48","unstructured":"D. Peleg. Local Majority Voting, Small Coalitions and Controlling Monopolies in Graphs: A Review. Proc. 3rd Colloq. on Structural Information & Communication Complexity, June 1996, Siena, Italy."},{"key":"19_CR49","doi-asserted-by":"crossref","unstructured":"S. Ponzio. Network Consensus in the Presence of Timing Uncertainty: Omission and Byzantine Failures. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, pp. 125\u2013138, August 1991.","DOI":"10.1145\/112600.112612"},{"key":"19_CR50","unstructured":"B. Awerbuch, I. Cidon, and S. Kutten, \u201cOptimal Maintenance of Replicated Information\u201d, proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS 90), St. Louis, MO, USA, pp. 492\u2013502, October 1990."},{"key":"19_CR51","doi-asserted-by":"crossref","unstructured":"J. Auerbach, P.M. Gopal, M. Kaplan, and S. Kutten, \u201cMulticast Group Membership Management in High Speed Wide Area Networks\u201d, Proceedings of the 11th International Conference on Distributed Computing Systems (IC DCS), Arlington, Texas, USA, May 1991.","DOI":"10.1109\/ICDCS.1991.148670"},{"issue":"3","key":"19_CR52","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1109\/JSAC.1985.1146222","volume":"SAC-3","author":"A. E. Baratz","year":"1985","unstructured":"A. E. Baratz, J. P. Gray, P. E. Green Jr., J. M. Jaffe, and D.P. Pozefski. Sna networks of small systems. IEEE Journal on Selected Areas in Communications, SAC-3(3):416\u2013426, May 1985.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"issue":"No.3","key":"19_CR53","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/18.382023","volume":"41","author":"I. Cidon","year":"1995","unstructured":"I. Cidon, I. Gopal, and S. Kutten. New Models and Algorithms for Future Networks. IEEE Transactions on Information Theory, Vol. 41, No. 3, pp. 769\u2013780, May 1995.","journal-title":"IEEE Transactions on Information Theory"},{"key":"19_CR54","unstructured":"John M. Spinelli and Robert G. Gallager. Broadcasting topology information in computer networks. IEEE Trans. on Commun., May 1989."},{"key":"19_CR55","unstructured":"A.S. Tanenbaum. Computer Networks. Prentice-Hall, 1981."}],"container-title":["Lecture Notes in Computer Science","SOFSEM'96: Theory and Practice of Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0037411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T08:48:41Z","timestamp":1683362921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0037411"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540619949","9783540495888"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/bfb0037411","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}