{"created":"2023-05-15T12:34:51.024396+00:00","id":3572,"links":{},"metadata":{"_buckets":{"deposit":"adfa948e-120e-4b9f-84f2-59c1c8fe62a1"},"_deposit":{"created_by":91,"id":"3572","owners":[91],"pid":{"revision_id":0,"type":"depid","value":"3572"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00003572","sets":["31"]},"author_link":["8720","8720","9761"],"item_10001_biblio_info_28":{"attribute_name":"bibliographic_information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2006","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"7","bibliographicPageEnd":"853","bibliographicPageStart":"843","bibliographicVolumeNumber":"55","bibliographic_titles":[{"bibliographic_title":"IEEE Transactions on Computers","bibliographic_titleLang":"en"}]}]},"item_10001_description_36":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"The condition-based approach is one of sophisticated methods to overcome several impossibilityresults in distributed consensus problem (e.g., impossibility of fault tolerance inasynchronous consensus, or time complexity lower bounds in synchronous consensus). Itintroduces conditions on input vectors to specify subsets of all possible input vectors to consensusalgorithms, and condition-based algorithms can circumvent the impossibility if actualinput vectors satisfy a particular condition. In this paper, we present a new condition-basedparadigm for synchronous consensus. We newly introduce the concept of adaptation on thetime complexity of condition-based algorithms, and present the adaptive condition-basedapproach to synchronous consensus. In our approach, all possible input vectors are classifiedinto hierarchical conditions according to their difficulty called the legality level. Executiontime of adaptive condition-based algorithms depends on the legality level of input vectors.We propose two adaptive condition-based algorithms for synchronous consensus. Thefirst algorithm requires that the majority of processes are correct, and terminates withinmin{f + 2; t + 1} ? l rounds if l < f, where f and t is the actual and the maximum numbersof faults respectively, and l is the legality level of the input vector. Moreover, thealgorithm terminates in one round if l ? t and f = 0, and terminates within two roundsif l ? f holds. Compared with previous algorithms, this algorithm achieves the best timecomplexity. The second algorithm can tolerate any number of faults, and terminates withinmax{3; min{f + 3; t + 2} ? l} rounds if l < f holds, terminates in one round if l ? t andf = 0, and terminates within three rounds if l ? f holds.Index Terms : distributed algorithm, synchronous system, consensus problem, fault-tolerance,crash fault, condition-based approach, adaptive algorithm","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_10001_full_name_27":{"attribute_name":"著者別名","attribute_value_mlt":[{"familyNames":[{"familyName":"Izumi","familyNameLang":"en"},{"familyName":"泉","familyNameLang":"ja"},{"familyName":"イズミ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Taisuke","givenNameLang":"en"},{"givenName":"泰介","givenNameLang":"ja"},{"givenName":"タイスケ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"8720","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"1000020432461","nameIdentifierScheme":"NRID","nameIdentifierURI":"http://rns.nii.ac.jp/nr/1000020432461"}],"names":[{"name":"Izumi, Taisuke","nameLang":"en"},{"name":"泉, 泰介","nameLang":"ja"},{"name":"イズミ, タイスケ","nameLang":"ja-Kana"}]}]},"item_10001_publisher_29":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electrical and Electronics Engineers","subitem_publisher_language":"en"}]},"item_10001_relation_34":{"attribute_name":"item_10001_relation_34","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1109/TC.2006.99"}],"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://dx.doi.org/10.1109/TC.2006.99","subitem_relation_type_select":"DOI"}}]},"item_10001_source_id_30":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0018-9340","subitem_source_identifier_type":"ISSN"}]},"item_10001_source_id_32":{"attribute_name":"item_10001_source_id_32","attribute_value_mlt":[{"subitem_source_identifier":"AA00667762","subitem_source_identifier_type":"NCID"}]},"item_10001_version_type_33":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorAffiliations":[{"affiliationNameIdentifiers":[{"affiliationNameIdentifierScheme":"ISNI","affiliationNameIdentifierURI":"http://www.isni.org/isni/"}],"affiliationNames":[{"affiliationNameLang":"ja"}]}],"creatorNames":[{"creatorName":"Izumi, Taisuke","creatorNameLang":"en"},{"creatorName":"泉, 泰介","creatorNameLang":"ja"},{"creatorName":"イズミ, タイスケ","creatorNameLang":"ja-Kana"}],"familyNames":[{"familyName":"Izumi","familyNameLang":"en"},{"familyName":"泉","familyNameLang":"ja"},{"familyName":"イズミ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Taisuke","givenNameLang":"en"},{"givenName":"泰介","givenNameLang":"ja"},{"givenName":"タイスケ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"8720","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"1000020432461","nameIdentifierScheme":"NRID","nameIdentifierURI":"http://rns.nii.ac.jp/nr/1000020432461"}]},{"creatorNames":[{"creatorName":"Masuzawa, Toshimitsu","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"9761","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-01-20"}],"displaytype":"detail","filename":"izumi_2006_IEEETC_1.pdf","filesize":[{"value":"155.6 kB"}],"format":"application/pdf","license_note":"c 2006 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"本文_fulltext","url":"https://nitech.repo.nii.ac.jp/record/3572/files/izumi_2006_IEEETC_1.pdf"},"version_id":"7e14d173-f293-4b7a-ba77-262998379630"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"item_resource_type","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Condition Adaptation in Synchronous Consensus","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Condition Adaptation in Synchronous Consensus","subitem_title_language":"en"}]},"item_type_id":"10001","owner":"91","path":["31"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-06-25"},"publish_date":"2013-06-25","publish_status":"0","recid":"3572","relation_version_is_last":true,"title":["Condition Adaptation in Synchronous Consensus"],"weko_creator_id":"91","weko_shared_id":-1},"updated":"2025-03-11T04:42:56.124700+00:00"}