{"created":"2023-05-15T12:34:46.402101+00:00","id":3414,"links":{},"metadata":{"_buckets":{"deposit":"bf9db921-2e6c-4445-8c13-e9bbe42efed9"},"_deposit":{"created_by":91,"id":"3414","owners":[91],"pid":{"revision_id":0,"type":"depid","value":"3414"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00003414","sets":["31"]},"author_link":["8720","8926","8966","8720","8926"],"item_5_biblio_info_5":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2010","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"125","bibliographicPageStart":"113","bibliographicVolumeNumber":"5869/2010","bibliographic_titles":[{"bibliographic_title":"Structural Information and Communication Complexity, Lecture Notes in Computer Science","bibliographic_titleLang":"en"}]}]},"item_5_description_4":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing leader election in population protocols without any kind of oracles. We identify the necessary and sufficient condition to solve the self-stabilizing leader election in population protocols from the aspects of local memory complexity and fairness assumptions. This paper shows that under the assumption of global fairness, no protocol using only n???1 states can solve the self-stabilizing leader election in complete interaction graphs, where n is the number of agents in the system. To prove this impossibility, we introduce a novel proof technique, called closed-set argument. In addition, we propose a self-stabilizing leader election protocol using n states that works even under the unfairness assumption. This protocol requires the exact knowledge about the number of agents in the system. We also show that such knowledge is necessary to construct any self-stabilizing leader election protocol.","subitem_description_language":"en","subitem_description_type":"Other"},{"subitem_description":"Proceeding of the 16th International Colloquium, SIROCCO 2009, Piran, Slovenia, May 25-27, 2009","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_5_full_name_3":{"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":"和田, 幸一"}]}]},"item_5_publisher_6":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer Verlag","subitem_publisher_language":"en"}]},"item_5_relation_10":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1007/978-3-642-11476-2_10"}],"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://dx.doi.org/10.1007/978-3-642-11476-2_10","subitem_relation_type_select":"DOI"}}]},"item_5_version_type_13":{"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":[{"creatorNames":[{"creatorName":"Shukai, Cai","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"8966","nameIdentifierScheme":"WEKO"}]},{"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-17"}],"displaytype":"detail","filename":"ssle.pdf","filesize":[{"value":"200.4 kB"}],"format":"application/pdf","license_note":"Copyright 2010 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/3414/files/ssle.pdf"},"version_id":"17d46b6a-2430-437e-942b-29325faa72ea"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Self-Stabilizing","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Leader","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Election","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Passively-Mobile","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Anonymous","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Agent","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":"conference paper","resourceuri":"http://purl.org/coar/resource_type/c_5794"}]},"item_title":"Space Complexity of Self-Stabilizing Leader Election in Passively-Mobile Anonymous Agents","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Space Complexity of Self-Stabilizing Leader Election in Passively-Mobile Anonymous Agents","subitem_title_language":"en"}]},"item_type_id":"5","owner":"91","path":["31"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-06-25"},"publish_date":"2013-06-25","publish_status":"0","recid":"3414","relation_version_is_last":true,"title":["Space Complexity of Self-Stabilizing Leader Election in Passively-Mobile Anonymous Agents"],"weko_creator_id":"91","weko_shared_id":-1},"updated":"2025-03-11T01:11:37.086703+00:00"}