{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:13Z","timestamp":1750307713183,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0347485"],"award-info":[{"award-number":["CNS-0347485"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>\n            We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm\u2014\n            <jats:italic>GDP<\/jats:italic>\n            that solves this generalized problem. Our algorithm is terminating. We formally prove\n            <jats:italic>GDP<\/jats:italic>\n            correct and evaluate its performance. We extend the algorithm to handle a similarly generalized drinking philosophers and the committee coordination problem. We describe how\n            <jats:italic>GDP<\/jats:italic>\n            can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.\n          <\/jats:p>","DOI":"10.1145\/1462187.1462194","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Self-stabilizing philosophers with generic conflicts"],"prefix":"10.1145","volume":"4","author":[{"given":"Praveen","family":"Danturi","sequence":"first","affiliation":[{"name":"Kent State University"}]},{"given":"Mikhail","family":"Nesterenko","sequence":"additional","affiliation":[{"name":"Kent State University"}]},{"given":"S\u00e9bastien","family":"Tixeuil","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Pierre et Marie Curie"}]}],"member":"320","published-online":{"date-parts":[[2009,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1606"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0111-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Arumugam M. and Kulkarni S. 2005. Self-stabilizing deterministic TDMA for sensor networks. Tech. rep. MSU-CSE-05-19 Michigan State University.  Arumugam M. and Kulkarni S. 2005. Self-stabilizing deterministic TDMA for sensor networks. Tech. rep. MSU-CSE-05-19 Michigan State University.","DOI":"10.21236\/ADA455715"},{"volume-title":"Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1521--1531","author":"Banerjee S.","key":"e_1_2_1_4_1","unstructured":"Banerjee , S. , Kommareddy , C. , Kar , K. , Bhattacharjee , S. , and Khuller , S . 2003. Construction of an efficient overlay multicast infrastructure for real-time applications . In Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1521--1531 . Banerjee, S., Kommareddy, C., Kar, K., Bhattacharjee, S., and Khuller, S. 2003. Construction of an efficient overlay multicast infrastructure for real-time applications. In Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 1521--1531."},{"volume-title":"Proceedings of the 12th International Symposium on Distributed Computing. Springer, 223--237","author":"Beauquier J.","key":"e_1_2_1_5_1","unstructured":"Beauquier , J. , Datta , A. , Gradinariu , M. , and Magniette , F . 2000. Self-stabilizing local mutual exclusion and daemon refinement . In Proceedings of the 12th International Symposium on Distributed Computing. Springer, 223--237 . Beauquier, J., Datta, A., Gradinariu, M., and Magniette, F. 2000. Self-stabilizing local mutual exclusion and daemon refinement. In Proceedings of the 12th International Symposium on Distributed Computing. Springer, 223--237."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 6th International Symposium on Self-Stabilizing Systems, (SSS03)","volume":"2704","author":"Blin L.","unstructured":"Blin , L. , Cournier , A. , and Villain , V . 2003. An improved snap-stabilizing PIF algorithm . In Proceedings of the 6th International Symposium on Self-Stabilizing Systems, (SSS03) , S.-T. Huang and T. Herman, Eds. Lecture Notes in Computer Science , vol. 2704 . Springer, 199--214. Blin, L., Cournier, A., and Villain, V. 2003. An improved snap-stabilizing PIF algorithm. In Proceedings of the 6th International Symposium on Self-Stabilizing Systems, (SSS03), S.-T. Huang and T. Herman, Eds. Lecture Notes in Computer Science, vol. 2704. Springer, 199--214."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011790"},{"volume-title":"Proceedings of the Forth Workshop on Self-Stabilizing Systems. IEEE, 78--85","author":"Bui A.","key":"e_1_2_1_8_1","unstructured":"Bui , A. , Datta , A. , Petit , F. , and Villain , V . 1999. State-optimal snap-stabilizing PIF in tree networks . In Proceedings of the Forth Workshop on Self-Stabilizing Systems. IEEE, 78--85 . Bui, A., Datta, A., Petit, F., and Villain, V. 1999. State-optimal snap-stabilizing PIF in tree networks. In Proceedings of the Forth Workshop on Self-Stabilizing Systems. IEEE, 78--85."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th International Symposium on Self-Stabilizing Systems. Lecture Notes in Computer Science","volume":"2704","author":"Cantarell S.","unstructured":"Cantarell , S. , Datta , A. , and Petit , F . 2003. Self-stabilizing atomicity refinement allowing neighborhood concurrency . In Proceedings of the 6th International Symposium on Self-Stabilizing Systems. Lecture Notes in Computer Science , vol. 2704 . Springer, 102--112. Cantarell, S., Datta, A., and Petit, F. 2003. Self-stabilizing atomicity refinement allowing neighborhood concurrency. In Proceedings of the 6th International Symposium on Self-Stabilizing Systems. Lecture Notes in Computer Science, vol. 2704. Springer, 102--112."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1780.1804"},{"key":"e_1_2_1_11_1","unstructured":"Chandy K. and Misra J. 1988. Parallel Program Design: a Foundation. Addison-Wesley Reading MA.   Chandy K. and Misra J. 1988. Parallel Program Design: a Foundation. Addison-Wesley Reading MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.006"},{"volume-title":"Cooperating Sequential Processes","author":"Dijkstra E.","key":"e_1_2_1_13_1","unstructured":"Dijkstra , E. 1968. Cooperating Sequential Processes . Academic Press . Dijkstra, E. 1968. Cooperating Sequential Processes. Academic Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Dolev S. 2000. Self-Stabilization. MIT Press.   Dolev S. 2000. Self-Stabilization. MIT Press.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626404001970"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_27"},{"volume-title":"Elements of Network Protocol Design","author":"Gouda M.","key":"e_1_2_1_17_1","unstructured":"Gouda , M. 1998. Elements of Network Protocol Design . John Wiley & amp; Sons, Inc. Gouda, M. 1998. Elements of Network Protocol Design. John Wiley &amp; Sons, Inc."},{"volume-title":"Proceedings of the 4th Workshop on Self-Stabilizing Systems. IEEE Computer Society, 48--53","author":"Gouda M.","key":"e_1_2_1_18_1","unstructured":"Gouda , M. and Haddix , F . 1999. The alternator . In Proceedings of the 4th Workshop on Self-Stabilizing Systems. IEEE Computer Society, 48--53 . Gouda, M. and Haddix, F. 1999. The alternator. In Proceedings of the 4th Workshop on Self-Stabilizing Systems. IEEE Computer Society, 48--53."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.88464"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2007.95"},{"volume-title":"Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 45--58","author":"Herman T.","key":"e_1_2_1_22_1","unstructured":"Herman , T. and Tixeuil , S . 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks . In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 45--58 . Herman, T. and Tixeuil, S. 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 45--58."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 8.1--8.15","author":"Hoover H.","year":"1995","unstructured":"Hoover , H. 1995 . On the self-stabilization of processors with continuous states . In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 8.1--8.15 . Hoover, H. 1995. On the self-stabilization of processors with continuous states. In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 8.1--8.15."},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 15th International Parallel and Distributed Processing Symposium Workshops, J. R. et al., Ed","author":"Huang S.","unstructured":"Huang , S. 2000. The fuzzy philosophers . In Proceedings of the 15th International Parallel and Distributed Processing Symposium Workshops, J. R. et al., Ed . Lecture Notes in Computer Science , vol. 1800 , 130--136. Huang, S. 2000. The fuzzy philosophers. In Proceedings of the 15th International Parallel and Distributed Processing Symposium Workshops, J. R. et al., Ed. Lecture Notes in Computer Science, vol. 1800, 130--136."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872079"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626402001026"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760548.1760550"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804654"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.47"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2006.47"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Mitton N. Paroux K. Sericola B. and Tixeuil S. 2008. Ascending runs in dependent uniformly distributed random variables: Application to wireless networks. Methodology and Computing in Applied Probability.  Mitton N. Paroux K. Sericola B. and Tixeuil S. 2008. Ascending runs in dependent uniformly distributed random variables: Application to wireless networks. Methodology and Computing in Applied Probability.","DOI":"10.1007\/s11009-008-9088-0"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00069-6"},{"volume-title":"Proceedings of the SRDS Workshop on Reliability in Embedded Systems, 16--22","author":"Nesterenko M.","key":"e_1_2_1_33_1","unstructured":"Nesterenko , M. and Arora , A . 2001. Self-stabilizing routing in wireless embedded . In Proceedings of the SRDS Workshop on Reliability in Embedded Systems, 16--22 . Nesterenko, M. and Arora, A. 2001. Self-stabilizing routing in wireless embedded. In Proceedings of the SRDS Workshop on Reliability in Embedded Systems, 16--22."},{"volume-title":"Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS). IEEE, 191--198","author":"Nesterenko M.","key":"e_1_2_1_34_1","unstructured":"Nesterenko , M. and Arora , A . 2002a. Dining philosophers that tolerate malicious crashes . In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS). IEEE, 191--198 . Nesterenko, M. and Arora, A. 2002a. Dining philosophers that tolerate malicious crashes. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS). IEEE, 191--198."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1828"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/379539.379566"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IEEE INFOCOM.","volume":"3","author":"Shi S.","unstructured":"Shi , S. and Turner , J. S . 2002. Routing in overlay multicast networks . In Proceedings of the IEEE INFOCOM. Vol. 3 . IEEE Computer Society, 1200--1208. Shi, S. and Turner, J. S. 2002. Routing in overlay multicast networks. In Proceedings of the IEEE INFOCOM. Vol. 3. IEEE Computer Society, 1200--1208."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems.","volume":"2","author":"Sivilotti P.","unstructured":"Sivilotti , P. , Pike , S. , and Sridhar , N . 2000. A new distributed resource-allocation algorithm with optimal failure locality . In Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems. Vol. 2 . IASTED\/ACTA Press, 524--529. Sivilotti, P., Pike, S., and Sridhar, N. 2000. A new distributed resource-allocation algorithm with optimal failure locality. In Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems. Vol. 2. IASTED\/ACTA Press, 524--529."}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462194","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462187.1462194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462187.1462194"],"URL":"https:\/\/doi.org\/10.1145\/1462187.1462194","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}