{"created":"2023-05-15T12:34:51.396391+00:00","id":3581,"links":{},"metadata":{"_buckets":{"deposit":"7a53a530-e480-435b-a12f-825ea3b4deb9"},"_deposit":{"created_by":91,"id":"3581","owners":[91],"pid":{"revision_id":0,"type":"depid","value":"3581"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00003581","sets":["31"]},"author_link":["8720","8926","8720","8926"],"item_10001_biblio_info_28":{"attribute_name":"bibliographic_information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2007","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"371","bibliographicPageStart":"357","bibliographicVolumeNumber":"4838/2007","bibliographic_titles":[{"bibliographic_title":"Proceedings of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science","bibliographic_titleLang":"en"}]}]},"item_10001_description_36":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"This paper newly proposes a novel round-based synchronoussystem suffering crash and probabilistic omission failures. In this model,a novel class of adversaries, called p-probabilistic omission adversary (p-POA) is introduced. In addition to the ability of complete control of thecrash-failure behavior, p-POA can select any subset of all transmittedmessages as omission candidates. Then, each message in the omissioncandidates is lost with probability p. This paper investigates the feasiblityand complexity of the consensus problem under p-POA. We firstshow two impossibility results that (1) for any p > 0, there exists nouniform consensus algorithm tolerating more than or equal to n/2 crashfailures, and that (2) for any p > 0, any uniform consensus algorithmcannot halt. We also show two consensus algorithms CPO and F-CPO.Both algorithms work under (1/2)-POA and respectively have distinctadvantages. The algorithm CPO can tolerate at most n/2 ! 1 crash failuresand achieves O(f) expected round complexity, where f is the actualnumber of crash failures. This implies that CPO has maximum crashfailureresiliency. While the second algorithm F-CPO assumes the maximumnumber of crash failures less than n/3, it achieves f + O(1) roundcompexity in expectation. Since it is known that the lower bound forcrash-tolerant consensus is f +1, this result implies that only a constantnumber of extra rounds is nessesary to tolerate a drastic number of messageomissions.","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"}]},{"nameIdentifiers":[{"nameIdentifier":"8926","nameIdentifierScheme":"WEKO"}],"names":[{"name":"wada, koichi"}]}]},"item_10001_publisher_29":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer Verlag","subitem_publisher_language":"en"}]},"item_10001_relation_31":{"attribute_name":"ISBN","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"9783540766261","subitem_relation_type_select":"ISBN"}}]},"item_10001_relation_32":{"attribute_name":"item_10001_relation_32","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"BA83981944","subitem_relation_type_select":"NCID"}}]},"item_10001_relation_34":{"attribute_name":"item_10001_relation_34","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1007/978-3-540-76627-8_27"}],"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://dx.doi.org/10.1007/978-3-540-76627-8_27","subitem_relation_type_select":"DOI"}}]},"item_10001_source_id_30":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0302-9743","subitem_source_identifier_type":"ISSN"}]},"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":"Wada, Koichi","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"8926","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_2007_LNCS_2.pdf","filesize":[{"value":"138.7 kB"}],"format":"application/pdf","license_note":"Copyright 2007 Springer-Verlag  The final publication is available at www.springerlink.com.","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"本文_fulltext","url":"https://nitech.repo.nii.ac.jp/record/3581/files/izumi_2007_LNCS_2.pdf"},"version_id":"657245af-a2ff-424d-a9d4-31f084a6f9e1"}]},"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":"On the probabilistic omission adversary","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"On the probabilistic omission adversary","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":"3581","relation_version_is_last":true,"title":["On the probabilistic omission adversary"],"weko_creator_id":"91","weko_shared_id":-1},"updated":"2025-03-11T04:44:35.518691+00:00"}