{"id":{"repo_id":"mtu","oai_identifier":"oai:digitalcommons.mtu.edu:etdr-1162"},"canonical_url":"https://search.ndltd.org/etd/mtu/oai:digitalcommons.mtu.edu:etdr-1162","repository":{"repo_id":"mtu","name":"Michigan Technological University","base_url":"https://digitalcommons.mtu.edu/do/oai/"},"display":{"title":"On the Limits and Practice of Automatically Designing Self-Stabilization","abstract":"A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, we develop an algorithm to synthesize a self-stabilizing protocol given its desired topology, legitimate states, and behavior. By analogy to shadow puppetry, where a puppeteer may design a complex puppet to cast a desired shadow, a protocol may need to be designed in a complex way that does not even resemble its specification. Our shadow/puppet synthesis algorithm addresses this concern and, using a complete backtracking search, has automatically designed 4 new self-stabilizing protocols with minimal process space requirements: 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, 3-state token passing on bidirectional chains, and 4-state orientation on daisy chains.","abstract_html":"A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, we develop an algorithm to synthesize a self-stabilizing protocol given its desired topology, legitimate states, and behavior. By analogy to shadow puppetry, where a puppeteer may design a complex puppet to cast a desired shadow, a protocol may need to be designed in a complex way that does not even resemble its specification. Our shadow/puppet synthesis algorithm addresses this concern and, using a complete backtracking search, has automatically designed 4 new self-stabilizing protocols with minimal process space requirements: 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, 3-state token passing on bidirectional chains, and 4-state orientation on daisy chains.","abstract_has_math":false,"creators":["Klinkhamer, Alex"],"institution":null,"degree_name":"Doctor of Philosophy in Computer Science (PhD)","degree_level":"Open Access Dissertation","degree_discipline":"Department of Computer Science","degree_department":null,"school":null,"contributors":["Ali Ebnenasir"],"advisors":[],"committee_chairs":[],"committee_members":["Melissa Keranen","Jean Mayo","Charles Wallace"],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:16:45Z","subjects":["self-stabilization","distributed computing","program synthesis","OS and Networks","Software Engineering","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.mtu.edu/etdr/90"],"render_values":[{"text":"https://digitalcommons.mtu.edu/etdr/90","href":"https://digitalcommons.mtu.edu/etdr/90","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.37099/mtu.dc.etdr/90","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/10.37099/mtu.dc.etdr/90","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.mtu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.mtu.edu%3Aetdr-1162","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ali Ebnenasir"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Melissa Keranen","Jean Mayo","Charles Wallace"]},{"key":"dc:creator","label":"Author","values":["Klinkhamer, Alex"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.created","label":"Dc Date Created","values":["2016-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Department of Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Open Access Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy in Computer Science (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["self-stabilization","distributed computing","program synthesis","OS and Networks","Software Engineering","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.37099/mtu.dc.etdr/90","https://digitalcommons.mtu.edu/etdr/90"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, we develop an algorithm to synthesize a self-stabilizing protocol given its desired topology, legitimate states, and behavior. By analogy to shadow puppetry, where a puppeteer may design a complex puppet to cast a desired shadow, a protocol may need to be designed in a complex way that does not even resemble its specification. Our shadow/puppet synthesis algorithm addresses this concern and, using a complete backtracking search, has automatically designed 4 new self-stabilizing protocols with minimal process space requirements: 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, 3-state token passing on bidirectional chains, and 4-state orientation on daisy chains."]},{"key":"dc:title","label":"Title","values":["On the Limits and Practice of Automatically Designing Self-Stabilization"]}]}],"canonical_facts":{"dc:contributor":["Ali Ebnenasir"],"dc:contributor.committeemember":["Melissa Keranen","Jean Mayo","Charles Wallace"],"dc:creator":["Klinkhamer, Alex"],"dc:date.created":["2016-01-01T08:00:00Z"],"dc:description.abstract":["A protocol is said to be self-stabilizing when the distributed system executing it is guaranteed to recover from any fault that does not cause permanent damage. Designing such protocols is hard since they must recover from all possible states, therefore we investigate how feasible it is to synthesize them automatically. We show that synthesizing stabilization on a fixed topology is NP-complete in the number of system states. When a solution is found, we further show that verifying its correctness on a general topology (with any number of processes) is undecidable, even for very simple unidirectional rings. Despite these negative results, we develop an algorithm to synthesize a self-stabilizing protocol given its desired topology, legitimate states, and behavior. By analogy to shadow puppetry, where a puppeteer may design a complex puppet to cast a desired shadow, a protocol may need to be designed in a complex way that does not even resemble its specification. Our shadow/puppet synthesis algorithm addresses this concern and, using a complete backtracking search, has automatically designed 4 new self-stabilizing protocols with minimal process space requirements: 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, 3-state token passing on bidirectional chains, and 4-state orientation on daisy chains."],"dc:identifier":["10.37099/mtu.dc.etdr/90","https://digitalcommons.mtu.edu/etdr/90"],"dc:subject":["self-stabilization","distributed computing","program synthesis","OS and Networks","Software Engineering","Theory and Algorithms"],"dc:title":["On the Limits and Practice of Automatically Designing Self-Stabilization"],"thesis:degree_discipline":["Department of Computer Science"],"thesis:degree_level":["Open Access Dissertation"],"thesis:degree_name":["Doctor of Philosophy in Computer Science (PhD)"]},"updated_at":"2026-11-19T08:16:45Z"}