{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T05:02:47Z","timestamp":1698037367591},"reference-count":11,"publisher":"Wiley","issue":"12","license":[{"start":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T00:00:00Z","timestamp":1174521600000},"content-version":"vor","delay-in-days":5924,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems & Computers in Japan"],"published-print":{"date-parts":[[1991,1]]},"abstract":"Abstract<\/jats:title>Consider a directed Hamilton cycle H<\/jats:italic> on a complete network. If each processor can distinguish its incident links by the distance on H<\/jats:italic>, the Hamilton cycle is said to have the sense of direction. It is known that the communication complexity of the leader election problem can be reduced by using the sense of direction when there exists no failure in the network.<\/jats:p>This paper considers the complete network with the sense of direction where at most fp<\/jats:sub> processors (fp<\/jats:sub> < n\/2, where n<\/jats:italic> is the total number of processors in the network) are in the fail\u2010stop condition and presents an algorithm which solves the leader election problem with the communication complexity O(n + k.fp<\/jats:sub>) (k is the number of initiating processors). The result implies that the sense of direction can be used to reduce the communication complexity of the leader election problem also in the complete network with fail\u2010stop processors. It is shown also that the communication complexity of the presented algorithm is optimal within a constant factor.<\/jats:p>","DOI":"10.1002\/scj.4690221202","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T20:03:25Z","timestamp":1183838605000},"page":"11-23","source":"Crossref","is-referenced-by-count":4,"title":["A fault\u2010tolerant algorithm for election in complete networks with a sense of direction"],"prefix":"10.1002","volume":"22","author":[{"given":"Toshimitsu","family":"Masuzawa","sequence":"first","affiliation":[]},{"given":"Naoki","family":"Nishikawa","sequence":"additional","affiliation":[]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[]},{"given":"Nobuki","family":"Tokura","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,22]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"Y.AfekandE.Gafni.Time and message bound for election in synchronous and asynchronous complete networks. Proc. 4th PODC pp.186\u2013195(1985).","DOI":"10.1145\/323596.323613"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_5_2","unstructured":"K.Hagiwara.Complexity of distributed algorithm. Proc. The Logic Programming Conference \u203287 pp.11\u201320(1987)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"E.Korach S.Moran andS.Zaks.Tight lower and upper bounds for some distributed algorithms for a complete network of processors. Proc. 3rd PODC pp.199\u2013207(1984).","DOI":"10.1145\/800222.806747"},{"key":"e_1_2_1_7_2","unstructured":"S.Kutten Y.Wolfstahl andS.Zaks.Optimal distributed t\u2010resilient election in complete networks. Tech. Rep. #430 Department of Computer Science Technion (1986)."},{"key":"e_1_2_1_8_2","unstructured":"S.Kutten.Optimal fault\u2010tolerant distributed construction of a spanning tree. The final version of [6]."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90025-6"},{"issue":"6","key":"e_1_2_1_10_2","first-page":"1092","article-title":"Distributed algorithm for fault diagnosis of processors","volume":"70","author":"Masuzawa T.","year":"1987","journal-title":"Trans. (D), I.E.I.C.E., Japan"},{"key":"e_1_2_1_11_2","unstructured":"T.Masuzawa N.Nishikawa K.Hagihara N.Tokura andK.Fujita.Leader election problem considering link fault in a complete network with a sense of direction. Tech. Rep. I.E.I.C.E. Japan COMP88\u201098 (1989)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1008959.1008961"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690221202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690221202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T22:04:39Z","timestamp":1698012279000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690221202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,1]]},"references-count":11,"journal-issue":{"issue":"12","published-print":{"date-parts":[[1991,1]]}},"alternative-id":["10.1002\/scj.4690221202"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690221202","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,1]]}}}