{"id":1040,"date":"2024-04-02T10:30:28","date_gmt":"2024-04-02T17:30:28","guid":{"rendered":"https:\/\/labs.engineering.asu.edu\/sops\/?page_id=1040"},"modified":"2024-04-02T10:30:28","modified_gmt":"2024-04-02T17:30:28","slug":"improved-leader-election","status":"publish","type":"page","link":"https:\/\/labs.engineering.asu.edu\/sops\/improved-leader-election\/","title":{"rendered":"Improved Leader Election for Self-Organizing Programmable Matter"},"content":{"rendered":"\n<div style=\"height:30px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"wp-block-paragraph\">Joshua J. Daymude, Robert Gmyr, Andr\u00e9a W. Richa, Christian Scheideler, and Thim Strothmann.<br>[<a href=\"https:\/\/arxiv.org\/abs\/1701.03616\">arXiv<\/a>] [<a href=\"https:\/\/link.springer.com\/chapter\/10.1007\/978-3-319-72751-6_10\">Springer<\/a>] \u2014 Conference paper in\u00a0<em>Algorithms for Sensor Systems\u00a0(ALGOSENSORS \u201917),\u00a0<\/em>pp. 127-140, 2017.<\/p>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n\n\n\n<div style=\"height:20px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h2 class=\"wp-block-heading\">Overview<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Leader election<\/strong>&nbsp;is a well-studied problem in distributed computing. In our setting, each particle in a connected system (under the usual constraints of the&nbsp;<a href=\"https:\/\/sops.engineering.asu.edu\/sops\/amoebot\/\">amoebot model<\/a>) must cooperate to eventually elect a&nbsp;<strong>single, unique leader<\/strong>. Said more formally, there must exist some time in the future at which a particle declares itself the leader, after which no other particle may ever do the same.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This paper improves on the algorithm given in the original&nbsp;<a href=\"https:\/\/sops.engineering.asu.edu\/sops\/leader-election\/\">Leader Election paper<\/a>&nbsp;(2015) in several ways:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>This algorithm is entirely defined within the constraints of the amoebot model. All information is local, and the particles\u2019 actions are asynchronous.<\/li>\n\n\n\n<li>This algorithm\u2019s analysis examines the fully local, asynchronous setting (instead of the simplified synchronous setting) and is able to obtain strong with high probability guarantees.<\/li>\n\n\n\n<li>The algorithm is conceptually simpler to understand and implement.<\/li>\n<\/ul>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n\n\n\n<div style=\"height:20px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"669\" height=\"484\" src=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaries.png\" alt=\"\" class=\"wp-image-667\" srcset=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaries.png 669w, https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaries-500x362.png 500w\" sizes=\"auto, (max-width: 669px) 100vw, 669px\" \/><\/figure>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"669\" height=\"484\" src=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-agents.png\" alt=\"\" class=\"wp-image-665\" srcset=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-agents.png 669w, https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-agents-500x362.png 500w\" sizes=\"auto, (max-width: 669px) 100vw, 669px\" \/><\/figure>\n<\/div>\n<\/div>\n\n\n\n<div style=\"height:20px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"wp-block-paragraph\">This improved algorithm works in six phases:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Boundary setup<\/strong>. The particles first organize into cycles on the system\u2019s boundaries, as in the original algorithm.<\/li>\n\n\n\n<li><strong>Segment setup<\/strong>. Each particle then flips a fair coin: heads means that particle is a candidate for leadership, and tails means it is immediately demoted. Each candidate claims the run of non-candidates behind it as its segment for use in the competition for leadership.<\/li>\n\n\n\n<li><strong>Identifier setup<\/strong>. Each candidate then generates an identifier for its segment by signalling to each of its non-candidates that they should generate a random bit. The sequence of these bits forms the segment\u2019s identifier.<\/li>\n\n\n\n<li><strong>Identifier comparison<\/strong>. Using a carefully coordinated scheme, segments then compare identifiers. Candidates with larger identifiers continue to compete, while candidates with smaller identifiers are demoted. In some cases, two identifiers will be equal, triggering the next phase.<\/li>\n\n\n\n<li><strong>Solitude verification<\/strong>. It is possible that two identifiers are equal because there is only one candidate remaining on the boundary. To test for this, a careful scheme that uses geometric information from the lattice checks if the start and end of the candidate\u2019s segment are the same (meaning it is the only candidate left). If this is the case, the candidate proceeds to the final phase, otherwise, it continues with identifier comparison.<\/li>\n\n\n\n<li><strong>Boundary identification<\/strong>. Again using geometric information (in particular, the angles along the boundary), the candidate checks whether it is on an inner boundary or the unique outer boundary. As in the original algorithm, it becomes the unique leader only if it is on the outer boundary; otherwise, it demotes itself.<\/li>\n<\/ol>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n\n\n\n<div style=\"height:20px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"1409\" height=\"190\" src=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaryid.png\" alt=\"\" class=\"wp-image-666\" srcset=\"https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaryid.png 1409w, https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaryid-500x67.png 500w, https:\/\/labs.engineering.asu.edu\/sops\/wp-content\/uploads\/sites\/181\/2020\/01\/paper-improvedleaderelection-boundaryid-1000x135.png 1000w\" sizes=\"auto, (max-width: 1409px) 100vw, 1409px\" \/><\/figure>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n\n\n\n<div style=\"height:20px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-930feb06 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h2 class=\"wp-block-heading\">Resources<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">None.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Press<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">None.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">BibTeX<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">@inproceedings{Daymude2017, <br>title = {Improved Leader Election for Self-Organizing Programmable Matter}, <br>author = {Daymude, Joshua J. and Gmyr, Robert and Richa, Andr\\&#8217;ea W. and Scheideler, Christian and Strothmann, Thim}, <br>booktitle = {Algorithms for Sensor Systems}, <br>series = {ALGOSENSORS &#8217;17}, <br>pages = {127&#8211;140}, <br>year = {2017} }<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Related Publications<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">As discussed in the Overview, this paper supplants the original&nbsp;<a href=\"https:\/\/sops.engineering.asu.edu\/sops\/leader-election\/\">Leader Election paper<\/a>&nbsp;(2015).<\/p>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p class=\"mb-2\">Joshua J. Daymude, Robert Gmyr, Andr\u00e9a W. Richa, Christian Scheideler, and Thim Strothmann.[arXiv] [Springer] \u2014 Conference paper in\u00a0Algorithms for Sensor Systems\u00a0(ALGOSENSORS \u201917),\u00a0pp. 127-140, 2017. Overview Leader election&nbsp;is a well-studied problem in distributed computing. In our setting, each particle in a connected system (under the usual constraints of the&nbsp;amoebot model) must cooperate to eventually elect a&nbsp;single,&#8230;<\/p>\n","protected":false},"author":338,"featured_media":0,"parent":0,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-1040","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages\/1040","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/users\/338"}],"replies":[{"embeddable":true,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/comments?post=1040"}],"version-history":[{"count":0,"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/pages\/1040\/revisions"}],"wp:attachment":[{"href":"https:\/\/labs.engineering.asu.edu\/sops\/wp-json\/wp\/v2\/media?parent=1040"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}