Document Open Access Logo

Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach

Authors Yuval Emek, Yuval Gil, Noga Harlev

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.27.pdf
  • Filesize: 0.71 MB
  • 19 pages

Document Identifiers

Author Details

Yuval Emek
  • Technion - Israel Institute of Technology, Haifa, Israel
Yuval Gil
  • Technion - Israel Institute of Technology, Haifa, Israel
Noga Harlev
  • Technion - Israel Institute of Technology, Haifa, Israel

Funding

This research was supported by VATAT Fund to the Technion Artificial Intelligence Hub (Tech.AI).

Acknowledgements

We thank Laurent Feuilloley for a helpful and insightful discussion.

Cite As Get BibTex

Yuval Emek, Yuval Gil, and Noga Harlev. Design of Self-Stabilizing Approximation Algorithms via a Primal-Dual Approach. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.OPODIS.2022.27

Abstract

Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results:  
- A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds. 
- A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds. 
- A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds.  In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Distributed algorithms
Keywords
  • self-stabilization
  • approximation algorithms
  • primal-dual

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ozkan Arapoglu and Orhan Dagdeviren. An asynchronous self-stabilizing maximal independent set algorithm in wireless sensor networks using two-hop information. In 2019 International Symposium on Networks, Computers and Communications (ISNCC), pages 1-5. IEEE, 2019. Google Scholar
  2. Baruch Awerbuch and George Varghese. Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In FOCS, volume 91, pages 258-267, 1991. Google Scholar
  3. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 165-174. ACM, 2017. Google Scholar
  4. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2 + ε)-approximation for vertex cover in o(log Δ / ε log log Δ) rounds. J. ACM, 64(3):23:1-23:11, 2017. Google Scholar
  5. Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (Δ + 1)-coloring and applications. J. ACM, 69(1):5:1-5:26, 2022. Google Scholar
  6. Jean RS Blair and Fredrik Manne. Efficient self-stabilizing algorithms for tree networks. In 23rd International Conference on Distributed Computing Systems, 2003. Proceedings., pages 20-26. IEEE, 2003. Google Scholar
  7. Subhendu Chattopadhyay, Lisa Higham, and Karen Seyffarth. Dynamic and self-stabilizing distributed matching. In Proceedings of the twenty-first annual symposium on Principles of distributed computing, pages 290-297, 2002. Google Scholar
  8. Well Y Chiu, Chiuyuan Chen, and Shih-Yu Tsai. A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon. Information Processing Letters, 114(10):515-518, 2014. Google Scholar
  9. Johanne Cohen, Jonas Lefevre, Khaled Maâmra, Laurence Pilard, and Devan Sohier. A self-stabilizing algorithm for maximal matching in anonymous networks. Parallel Processing Letters, 26(04):1650016, 2016. Google Scholar
  10. Edsger W Dijkstra. Self-stabilization in spite of distributed control. In Selected writings on computing: a personal perspective, pages 41-46. Springer, 1982. Google Scholar
  11. Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25-29, 2022, pages 292-300. ACM, 2022. Google Scholar
  12. Swan Dubois and Sébastien Tixeuil. A taxonomy of daemons in self-stabilization. arXiv preprint, 2011. URL: http://arxiv.org/abs/1110.0334.
  13. Manuela Fischer. Improved deterministic distributed matching via rounding. Distributed Computing, 33, June 2020. Google Scholar
  14. Mohsen Ghaffari and Goran Zuzic. Universally-optimal distributed exact min-cut. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25-29, 2022, pages 281-291. ACM, 2022. Google Scholar
  15. Wayne Goddard, Stephen T Hedetniemi, David P Jacobs, Pradip K Srimani, and Zhenyu Xu. Self-stabilizing graph protocols. Parallel Processing Letters, 18(01):189-199, 2008. Google Scholar
  16. Wayne Goddard, Stephen T Hedetniemi, David Pokrass Jacobs, and Pradip K Srimani. Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. In Proceedings International Parallel and Distributed Processing Symposium, pages 14-pp. IEEE, 2003. Google Scholar
  17. Maria Gradinariu and Sébastien Tixeuil. Conflict managers for self-stabilization without fairness assumption. In 27th International Conference on Distributed Computing Systems (ICDCS'07), pages 46-46. IEEE, 2007. Google Scholar
  18. Nabil Guellati and Hamamache Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. Journal of Parallel and Distributed Computing, 70(4):406-415, 2010. Google Scholar
  19. Sandra M Hedetniemi, Stephen T Hedetniemi, David P Jacobs, and Pradip K Srimani. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Computers & Mathematics with Applications, 46(5-6):805-811, 2003. Google Scholar
  20. Stephen T Hedetniemi, David P Jacobs, and Pradip K Srimani. Maximal matching stabilizes in time o (m). Information Processing Letters, 80(5):221-223, 2001. Google Scholar
  21. Su-Chu Hsu and Shing-Tsaan Huang. A self-stabilizing algorithm for maximal matching. Information processing letters, 43(2):77-81, 1992. Google Scholar
  22. Michiyo Ikeda, Sayaka Kamei, and Hirotsugu Kakugawa. A space-optimal self-stabilizing algorithm for the maximal independent set problem. In the Third International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), pages 70-74, 2002. Google Scholar
  23. Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved distributed approximations for maximum independent set. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 35:1-35:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Jun Kiniwa. Approximation of self-stabilizing vertex cover less than 2. In Symposium on Self-Stabilizing Systems, pages 171-182. Springer, 2005. Google Scholar
  25. Fabian Kuhn and Rogert Wattenhofer. Constant-time distributed dominating set approximation. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, PODC '03, pages 25-32. Association for Computing Machinery, 2003. Google Scholar
  26. Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local algorithms: Self-stabilization on speed. In Symposium on Self-Stabilizing Systems, pages 17-34. Springer, 2009. Google Scholar
  27. Fredrik Manne, Morten Mjelde, Laurence Pilard, and Sébastien Tixeuil. A new self-stabilizing maximal matching algorithm. Theoretical Computer Science, 410(14):1336-1345, 2009. Google Scholar
  28. Sandeep K Shukla, Daniel J Rosenkrantz, S Sekharipuram Ravi, et al. Observations on self-stabilizing graph algorithms for anonymous networks. In Proceedings of the second workshop on self-stabilizing systems, volume 7, page 15. University of Nevada LasVegas, 1995. Google Scholar
  29. Gerard Tel. Maximal matching stabilizes in quadratic time. Information Processing Letters, 49(6):271-272, 1994. Google Scholar
  30. Volker Turau. Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler. Information Processing Letters, 103(3):88-93, 2007. Google Scholar
  31. Volker Turau and Bernd Hauck. A fault-containing self-stabilizing (3- 2δ+ 1)-approximation algorithm for vertex cover in anonymous networks. Theoretical computer science, 412(33):4361-4371, 2011. Google Scholar
  32. Vijay V. Vazirani. Approximation algorithms. Springer, 2001. Google Scholar
  33. Guangyuan Wang, Hua Wang, Xiaohui Tao, and Ji Zhang. A self-stabilizing protocol for minimal weighted dominating sets in arbitrary networks. In Proceedings of the 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pages 496-501. IEEE, 2013. Google Scholar
  34. Zhenyu Xu, Stephen T Hedetniemi, Wayne Goddard, and Pradip K Srimani. A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph. In International Workshop on Distributed Computing, pages 26-32. Springer, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact