Document Open Access Logo

Deterministic Logarithmic Completeness in the Distributed Sleeping Model

Authors Leonid Barenboim, Tzalik Maimon

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.10.pdf
  • Filesize: 0.67 MB
  • 19 pages

Document Identifiers

Author Details

Leonid Barenboim
  • The Open University of Israel, Raanana, Israel
Tzalik Maimon
  • Ben-Gurion University of The Negev, Beer Sheva, Israel

Funding

This work was supported by the Open University of Israel Research Fund.

Acknowledgements

The authors are grateful to the anonymous reviewers for helpful comments.

Cite As Get BibTex

Leonid Barenboim and Tzalik Maimon. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.10

Abstract

In this paper we provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model [Valerie King et al., 2011; Soumyottam Chatterjee et al., 2020] is a generalization of the standard message-passing model, with an additional capability of network nodes to enter a sleeping state occasionally. As long as a vertex is in the awake state, it is similar to the standard message-passing setting. However, when a vertex is asleep it cannot receive or send messages in the network nor can it perform internal computations. On the other hand, sleeping rounds do not count towards awake complexity. Awake complexity is the main complexity measurement in this setting, which is the number of awake rounds a vertex spends during an execution. In this paper we devise algorithms with worst-case guarantees on the awake complexity. 
We devise a deterministic scheme with awake complexity of O(log n) for solving any decidable problem in this model by constructing a structure we call Distributed Layered Tree. This structure turns out to be very powerful in the sleeping model, since it allows one to collect the entire graph information within a constant number of awake rounds. Moreover, we prove that our general technique cannot be improved in this model, by showing that the construction of distributed layered trees itself requires Ω(log n) awake rounds. This is obtained by a reduction from message-complexity lower bounds, which is of independent interest. Furthermore, our scheme also works in the CONGEST setting where we are limited to messages of size at most O(log n) bits. This result is shown for a certain class of problems, which contains problems of great interest in the research of the distributed setting. Examples for problems we can solve under this limitation are leader election, computing exact number of edges and average degree. 
Another result we obtain in this work is a deterministic scheme for solving any problem from a class of problems, denoted O-LOCAL, in O(log Δ + log^*n) awake rounds. This class contains various well-studied problems, such as MIS and (Δ+1)-vertex-coloring. Our main structure in this case is a tree as well, but is sharply different from a distributed layered tree. In particular, it is constructed in the local memory of each processor, rather than distributively. Nevertheless, it provides an efficient synchronization scheme for problems of the O-LOCAL class.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Computing
  • Sleeping Model
  • Complexity Class

Metrics

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

Related Versions

References

  1. Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time quasi-polylogarithmic in delta. In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 289-298. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405710.
  2. Leonid Barenboim, Shlomi Dolev, and Rafail Ostrovsky. Deterministic and energy-optimal wireless synchronization. ACM Trans. Sens. Networks, 11(1):13:1-13:25, 2014. URL: https://doi.org/10.1145/2629493.
  3. Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1-23:25, 2011. URL: https://doi.org/10.1145/2027216.2027221.
  4. Leonid Barenboim, Michael Elkin, and Tzalik Maimon. Deterministic distributed (delta + o(delta))-edge-coloring, and vertex-coloring of graphs with bounded diversity. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 175-184. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087812.
  5. Leonid Barenboim and Tzalik Maimon. Deterministic logarithmic completeness in the distributed sleeping model. CoRR, abs/2108.01963, 2021. URL: http://arxiv.org/abs/2108.01963.
  6. Leonid Barenboim and Yaniv Tzur. Distributed symmetry-breaking with improved vertex-averaged complexity. In Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, January 04-07, 2019, pages 31-40. ACM, 2019. URL: https://doi.org/10.1145/3288599.3288601.
  7. Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky. Near-optimal radio use for wireless network synchronization. Theor. Comput. Sci., 453:14-28, 2012. URL: https://doi.org/10.1016/j.tcs.2011.09.026.
  8. Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. The energy complexity of broadcast. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 95-104. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212774.
  9. Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. Sleeping is efficient: MIS in O(1)-rounds node-averaged awake complexity. In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 99-108. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405718.
  10. Jing Deng, Yunghsiang S. Han, Wendi Rabiner Heinzelman, and Pramod K. Varshney. Scheduling sleeping nodes in high density cluster-based sensor networks. Mob. Networks Appl., 10(6):825-835, 2005. URL: https://doi.org/10.1007/s11036-005-4441-9.
  11. Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts. Performing work efficiently in the presence of faults. SIAM J. Comput., 27(5):1457-1491, 1998. URL: https://doi.org/10.1137/S0097539793255527.
  12. Laura Marie Feeney and Martin Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In Proceedings IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Twenty years into the communications odyssey, Anchorage, Alaska, USA, April 22-26, 2001, pages 1548-1557. IEEE Comptuer Society, 2001. URL: https://doi.org/10.1109/INFCOM.2001.916651.
  13. Laurent Feuilloley. How long it takes for an ordinary node with an ordinary ID to output? In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, volume 10641 of Lecture Notes in Computer Science, pages 263-282. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-72050-0_16.
  14. Laurent Feuilloley. How long it takes for an ordinary node with an ordinary id to output? Theor. Comput. Sci., 811:42-55, 2020. URL: https://doi.org/10.1016/j.tcs.2019.01.023.
  15. Manuela Fischer. Improved deterministic distributed matching via rounding. Distributed Comput., 33(3-4):279-291, 2020. URL: https://doi.org/10.1007/s00446-018-0344-4.
  16. Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 180-191. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.25.
  17. Greg N. Frederickson and Nancy A. Lynch. Electing a leader in a synchronous ring. J. ACM, 34(1):98-115, 1987. URL: https://doi.org/10.1145/7531.7919.
  18. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(1):66-77, 1983. URL: https://doi.org/10.1145/357195.357200.
  19. Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, and Chang Su. Time efficient k-shot broadcasting in known topology radio networks. Distributed Comput., 21(2):117-127, 2008. URL: https://doi.org/10.1007/s00446-008-0058-0.
  20. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 784-797. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055471.
  21. Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA, pages 219-225. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314705.
  22. Valerie King, Cynthia A. Phillips, Jared Saia, and Maxwell Young. Sleeping on the job: Energy-efficient and robust broadcast for radio networks. Algorithmica, 61(3):518-554, 2011. URL: https://doi.org/10.1007/s00453-010-9422-0.
  23. Fabian Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1244-1259. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.76.
  24. Nathan Linial. Distributive graph algorithms-global solutions from local data. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 331-335. IEEE Computer Society, 1987. URL: https://doi.org/10.1109/SFCS.1987.20.
  25. Miao Peng, Yang Xiao, and Pu Patrick Wang. Error analysis and kernel density approach of scheduling sleeping nodes in cluster-based wireless sensor networks. IEEE Trans. Veh. Technol., 58(9):5105-5114, 2009. URL: https://doi.org/10.1109/TVT.2009.2027908.
  26. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 350-363. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384298.
  27. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1-24:40, 2013. URL: https://doi.org/10.1145/2431211.2431223.
  28. Chafiq Titouna, Abdelhak Mourad Guéroui, Makhlouf Aliouat, Ado Adamou Abba Ari, and Amine Adouane. Distributed fault-tolerant algorithm for wireless sensor networks. Int. J. Commun. Networks Inf. Secur., 9(2), 2017. URL: http://www.ijcnis.org/index.php/ijcnis/article/view/1848.
  29. Lijun Wang, Jia Yan, Tao Han, and Dexiang Deng. On connectivity and energy efficiency for sleeping-schedule-based wireless sensor networks. Sensors, 19(9):2126, 2019. URL: https://doi.org/10.3390/s19092126.
  30. Rong Zheng and Robin Kravets. On-demand power management for ad hoc networks. Ad Hoc Networks, 3(1):51-68, 2005. URL: https://doi.org/10.1016/j.adhoc.2003.09.008.
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