{"created":"2024-04-26T08:26:41.396028+00:00","id":2000210,"links":{},"metadata":{"_buckets":{"deposit":"d3fa4bdf-8e37-4fa7-b873-4e02076d168f"},"_deposit":{"created_by":4,"id":"2000210","owner":"4","owners":[4],"pid":{"revision_id":0,"type":"depid","value":"2000210"},"status":"published"},"_oai":{"id":"oai:naist.repo.nii.ac.jp:02000210","sets":["34:35"]},"author_link":["36","109"],"item_7_biblio_info_9":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2022-03-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicNumberOfPages":"555","bibliographicPageEnd":"541","bibliographicVolumeNumber":"E105.D","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Information and Systems","bibliographic_titleLang":"en"}]}]},"item_7_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n4·|Λgood|·X(n)) rounds, where |Λgood| is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f2+9f+4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f+|&Lambdagood|)·X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f+|&Lambdaall|)·X(N)) rounds, where |&Lambdaall| is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and |&Lambdaall|=O(|&Lambdagood|) holds.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_7_publisher_10":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers","subitem_publisher_language":"en"}]},"item_7_relation_17":{"attribute_name":"出版者版DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1587/transinf.2021FCP0011","subitem_relation_type_select":"DOI"}}]},"item_7_relation_22":{"attribute_name":"出版者版URI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/bin/summary.php?id=e105-d_3_541","subitem_relation_type_select":"URI"}}]},"item_7_rights_18":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright c 2022 The Institute of Electronics, Information and Communication Engineers","subitem_rights_language":"en"}]},"item_7_source_id_12":{"attribute_name":"EISSN/PISSN","attribute_value_mlt":[{"subitem_source_identifier":"1745-1361","subitem_source_identifier_type":"EISSN"}]},"item_7_version_type_20":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"HIROSE, Jion","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"NAKAMURA, Junya","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"大下, 福仁","creatorNameLang":"ja"},{"creatorName":"オオシタ, フクヒト","creatorNameLang":"ja-Kana"},{"creatorName":"Ooshita,  Fukuhito","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"36","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"20362650","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://kaken.nii.ac.jp/ja/search/?qm=20362650"}]},{"creatorNames":[{"creatorName":"井上, 美智子","creatorNameLang":"ja"},{"creatorName":"イノウエ, ミチコ","creatorNameLang":"ja-Kana"},{"creatorName":"Inoue, Michiko","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"109","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"30273840","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://kaken.nii.ac.jp/ja/search/?qm=30273840"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_access","date":[{"dateType":"Available","dateValue":"2024-04-26"}],"filename":"paper_e105-d_3_541_20240424_113404_DU.pdf","filesize":[{"value":"572 KB"}],"format":"application/pdf","url":{"label":"fulltext","objectType":"fulltext","url":"https://naist.repo.nii.ac.jp/record/2000210/files/paper_e105-d_3_541_20240424_113404_DU.pdf"},"version_id":"451be945-c60e-4b8d-b21c-6f059ff37ec2"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"distributed algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"deterministic algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"mobile agents","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"gathering","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Byzantine faults","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Weakly Byzantine Gathering with a Strong Team","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Weakly Byzantine Gathering with a Strong Team","subitem_title_language":"en"}]},"item_type_id":"7","owner":"4","path":["35"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2024-04-30"},"publish_date":"2024-04-30","publish_status":"0","recid":"2000210","relation_version_is_last":true,"title":["Weakly Byzantine Gathering with a Strong Team"],"weko_creator_id":"4","weko_shared_id":-1},"updated":"2024-04-30T05:41:38.500637+00:00"}