{"created":"2023-05-15T11:59:52.977023+00:00","id":6499,"links":{},"metadata":{"_buckets":{"deposit":"71d2de66-e2b5-4d0f-b5cf-aec8fb1cefd6"},"_deposit":{"created_by":3,"id":"6499","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"6499"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00006499","sets":["8:24"]},"author_link":["27408","25091","27405","27406","27407"],"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2018-04-20","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"106","bibliographicPageStart":"92","bibliographicVolumeNumber":"119","bibliographic_titles":[{"bibliographic_title":"Journal of Parallel and Distributed Computing"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is in striking contrast to the rendezvous problem which requires the agents to meet at the same node. While rendezvous aims to break the symmetry, uniform deployment aims to attain the symmetry. It is well known that the symmetry breaking is difficult in distributed systems and the rendezvous problem cannot be solved from some initial configurations. Hence, we are interested in clarifying what difference the uniform deployment problem has on the solvability and the number of agent moves compared to the rendezvous problem. We consider two problem settings, with knowledge of k (or n) and without knowledge of k or n where k is the number of agents and n is the number of nodes. First, we consider agents with knowledge of k (or n since k and n can be easily obtained if one of them is given). In this case, we propose two algorithms. The first algorithm solves the uniform deployment problem with termination detection. This algorithm requires O(k log n) memory space per agent, O(n) time, and O(kn) total moves. The second algorithm also solves the uniform deployment problem with termination detection. This algorithm reduces the memory space per agent to O(log n), but uses O(n log k) time, and requires O(kn) total moves. Both algorithms are asymptotically optimal in terms of total moves since there are some initial configurations such that agents re- quire Ω(kn) total moves to solve the problem. Next, we consider agents with no knowledge of k or n. In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O((k/l) log(n/l)) memory space per agent, O(n/l) time, and O(kn/l) total moves when the initial configuration has symmetry degree l. This means that the algorithm can solve the problem more efficiently when the initial configuration has higher symmetric degree (i.e., is closer to uniform deployment). Note that all the proposed algorithms achieve uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations.","subitem_description_type":"Abstract"}]},"item_21_description_60":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"subitem_description":"Journal Article","subitem_description_type":"Other"}]},"item_21_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Elsevier"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1016/j.jpdc.2018.03.008","subitem_relation_type_select":"DOI"}}]},"item_21_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 2018 Elsevier Inc. All rights reserved."}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0743-7315","subitem_source_identifier_type":"ISSN"}]},"item_21_text_36":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Kyushu Institute of Technology, 680-4, Kawadu, Iizuka, Fukuoka, 820-8502, Japan"},{"subitem_text_value":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"},{"subitem_text_value":"Graduate School of Information Science, NAIST, Takayama 8916-5, Ikoma, Nara 630-0192, Japan"},{"subitem_text_value":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"},{"subitem_text_value":"Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan"}]},"item_21_text_63":{"attribute_name":"連携ID","attribute_value_mlt":[{"subitem_text_value":"7896"}]},"item_21_version_type_58":{"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":[],"affiliationNames":[{"affiliationName":""}]}],"creatorNames":[{"creatorName":"Shibata, Masahiro","creatorNameLang":"en"},{"creatorName":"柴田, 将拡","creatorNameLang":"ja"},{"creatorName":"シバタ, マサヒロ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{},{}]},{"creatorNames":[{"creatorName":"Mega,  Toshiya"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Ooshita,  Fukuhito"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kakugawa,  Hirotsugu"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Masuzawa,  Toshimitsu"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2020-04-21"}],"displaytype":"detail","filename":"RECN_2018-53.pdf","filesize":[{"value":"713.9 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"RECN_2018-53.pdf","url":"https://kyutech.repo.nii.ac.jp/record/6499/files/RECN_2018-53.pdf"},"version_id":"9e12d2f6-5da2-4c2f-93f5-99a61f5d4e28"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Distributed system","subitem_subject_scheme":"Other"},{"subitem_subject":"Mobile agent","subitem_subject_scheme":"Other"},{"subitem_subject":"Uniform deployment","subitem_subject_scheme":"Other"},{"subitem_subject":"Ring networks","subitem_subject_scheme":"Other"},{"subitem_subject":"Token","subitem_subject_scheme":"Other"},{"subitem_subject":"Symmetry degree","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":"Uniform deployment of mobile agents in asynchronous rings","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Uniform deployment of mobile agents in asynchronous rings"}]},"item_type_id":"21","owner":"3","path":["24"],"pubdate":{"attribute_name":"公開日","attribute_value":"2020-04-21"},"publish_date":"2020-04-21","publish_status":"0","recid":"6499","relation_version_is_last":true,"title":["Uniform deployment of mobile agents in asynchronous rings"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-10-25T09:01:39.666231+00:00"}