{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T10:38:34Z","timestamp":1756895914743,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T00:00:00Z","timestamp":1474329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2016,9,20]]},"abstract":"<jats:p>Self-stabilizing systems tolerate transient faults by always returning to a legitimate system state within a finite time. This goal is challenged by several system features such as arbitrary system states after faults, various process execution models, and constrained process communication means. This work designs self-stabilizing distributed algorithms from the perspective of game theory, achieving an intended system goal through private goals of processes. We propose a generic game design for identifying a maximal independent set (MIS) or a maximal weighted independent set (MWIS) among all processes in a distributed system. From the generic game several specific games can be defined which differ in whether and how neighboring players influence each other. Turning the game designs into self-stabilizing algorithms, we obtain the first algorithms for the MWIS problem and also the first self-stabilizing MIS algorithm that considers node degree (including an analysis of its performance ratio). We also show how to handle simultaneous moves of processes in some process execution models. Simulation results indicate that, for various representative network topologies, the new algorithm outperforms existing methods in terms of MIS size and convergence rate. For the MWIS problem, the new algorithms performed only slightly worse than centralized greedy counterparts.<\/jats:p>","DOI":"10.1145\/2957760","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T12:42:46Z","timestamp":1474461766000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Designing Self-Stabilizing Systems Using Game Theory"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2518-1728","authenticated-orcid":false,"given":"Li-Hsing","family":"Yen","sequence":"first","affiliation":[{"name":"National Chiao Tung University, Hsinchu, Taiwan"}]},{"given":"Jean-Yao","family":"Huang","sequence":"additional","affiliation":[{"name":"National University of Kaohsiung, Kaohsiung, Taiwan"}]},{"given":"Volker","family":"Turau","sequence":"additional","affiliation":[{"name":"Hamburg University of Technology, Hamburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2016,9,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","volume-title":"Emergence of scaling in random networks. Science 286 (Oct","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. Science 286 (Oct . 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286 (Oct. 1999), 509--512."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016747704458"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9417-x"},{"volume-title":"Modern Graph Theory","author":"Bollob\u00e1s B.","key":"e_1_2_1_5_1","unstructured":"B. Bollob\u00e1s . 1998. Modern Graph Theory . Springer-Verlag , New York . B. Bollob\u00e1s. 1998. Modern Graph Theory. Springer-Verlag, New York."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452001.1452005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/361179.361202"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360975"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u00f6s P.","year":"1959","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi . 1959 . On random graphs I . Publ. Math. Debr. 6 (1959), 290 -- 297 . P. Erd\u00f6s and A. R\u00e9nyi. 1959. On random graphs I. Publ. Math. Debr. 6 (1959), 290--297.","journal-title":"Publ. Math. Debr."},{"key":"e_1_2_1_11_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626408003314"},{"volume-title":"Proc. 17th Int\u2019l Parallel and Distributed Processing Symp.","author":"Goddard Wayne","key":"e_1_2_1_13_1","unstructured":"Wayne Goddard , Stephen T. Hedetniemi , David P. Jacobs , and Pradip K. Srimani . 2003. A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph . In Proc. 17th Int\u2019l Parallel and Distributed Processing Symp. Wayne Goddard, Stephen T. Hedetniemi, David P. Jacobs, and Pradip K. Srimani. 2003. A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph. In Proc. 17th Int\u2019l Parallel and Distributed Processing Symp."},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science 2194","volume-title":"The theory of weak stabilization","author":"Gouda Mohamed G.","unstructured":"Mohamed G. Gouda . 2001. The theory of weak stabilization . In Lecture Notes in Computer Science 2194 , A. K. Datta and T. Herman (Eds.). Springer-Verlag , 114--123. Mohamed G. Gouda. 2001. The theory of weak stabilization. In Lecture Notes in Computer Science 2194, A. K. Datta and T. Herman (Eds.). Springer-Verlag, 114--123."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.027"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2002.805812"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.11.006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(02)00529-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(03)90143-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxs128"},{"volume-title":"Proc. 11th IEEE Int\u2019l Conf. on Networks. 603--609","author":"Hekmat R.","key":"e_1_2_1_22_1","unstructured":"R. Hekmat and P. Van Meighem . 2003. Degree distribution and hopcount in wireless ad-hoc networks . In Proc. 11th IEEE Int\u2019l Conf. on Networks. 603--609 . R. Hekmat and P. Van Meighem. 2003. Degree distribution and hopcount in wireless ad-hoc networks. In Proc. 11th IEEE Int\u2019l Conf. on Networks. 603--609."},{"volume-title":"Proc. 3rd Int\u2019l Conf. on Parallel and Distributed Computing, Applications and Technologies.","author":"Ikeda M.","key":"e_1_2_1_23_1","unstructured":"M. Ikeda , S. Kamei , and H. Kakugawa . 2002. A space-optimal self-stabilizing algorithm for the maximal independent set problem . In Proc. 3rd Int\u2019l Conf. on Parallel and Distributed Computing, Applications and Technologies. M. Ikeda, S. Kamei, and H. Kakugawa. 2002. A space-optimal self-stabilizing algorithm for the maximal independent set problem. In Proc. 3rd Int\u2019l Conf. on Parallel and Distributed Computing, Applications and Technologies."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/s00446-002-0078-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898699.1898777"},{"volume-title":"Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies.","author":"Kamei S.","key":"e_1_2_1_26_1","unstructured":"S. Kamei and H. Kakugawa . 2003. A self-stabilizing algorithm for the distributed minimal k-redundant dominating set problem in tree network . In Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies. S. Kamei and H. Kakugawa. 2003. A self-stabilizing algorithm for the distributed minimal k-redundant dominating set problem in tree network. In Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e88-a.5.1109"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4226"},{"key":"e_1_2_1_29_1","volume-title":"An experimental study of the coloring problem on human subject networks. Science 313 (Aug","author":"Kearns Michael","year":"2006","unstructured":"Michael Kearns , Siddharth Suri , and Nick Montfort . 2006. An experimental study of the coloring problem on human subject networks. Science 313 (Aug . 2006 ), 824--827. Michael Kearns, Siddharth Suri, and Nick Montfort. 2006. An experimental study of the coloring problem on human subject networks. Science 313 (Aug. 2006), 824--827."},{"volume-title":"Proc. 17th Conf. in Uncertainty in Artificial Intelligence. 253--260","author":"Kearns Micheal J.","key":"e_1_2_1_30_1","unstructured":"Micheal J. Kearns , Michael L. Littman , and Satinder P. Singh . 2001. Graphical models for game theory . In Proc. 17th Conf. in Uncertainty in Artificial Intelligence. 253--260 . Micheal J. Kearns, Michael L. Littman, and Satinder P. Singh. 2001. Graphical models for game theory. In Proc. 17th Conf. in Uncertainty in Artificial Intelligence. 253--260."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7402929"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1004098107"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00205-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0797"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.010"},{"volume-title":"Proc. 2nd Workshop on Self-Stabilizing Systems.","author":"Shukla Sandeep K.","key":"e_1_2_1_40_1","unstructured":"Sandeep K. Shukla , Daniel J. Rosenkrantz , and S. S. Ravi . 1995. Observations on self-stabilizing graph algorithms for anonymous networks . In Proc. 2nd Workshop on Self-Stabilizing Systems. Sandeep K. Shukla, Daniel J. Rosenkrantz, and S. S. Ravi. 1995. Observations on self-stabilizing graph algorithms for anonymous networks. In Proc. 2nd Workshop on Self-Stabilizing Systems."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2182779"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.02.013"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626410000132"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.032"},{"key":"e_1_2_1_46_1","volume-title":"Strogatz","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H . Strogatz . 1998 . Collective dynamics of \u2018small-world\u2019 networks. Nature 393 (June 1998), 440--442. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 (June 1998), 440--442."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Z. Xu S. T. Hedetniemi W. Goddard and P. K. Srimani. 2003. A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph. In Lecture Notes in Computer Science 2918. Springer-Verlag 26--32.  Z. Xu S. T. Hedetniemi W. Goddard and P. K. Srimani. 2003. A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph. In Lecture Notes in Computer Science 2918. Springer-Verlag 26--32.","DOI":"10.1007\/978-3-540-24604-6_3"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.2297100"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951778"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2957760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2957760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:30Z","timestamp":1750220610000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2957760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,20]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9,20]]}},"alternative-id":["10.1145\/2957760"],"URL":"https:\/\/doi.org\/10.1145\/2957760","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2016,9,20]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}