Deterministic logarithmic completeness in the distributed sleeping model

Leonid Barenboim, Tzalik Maimon

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


In this paper we provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model [22, 9] 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.

שפה מקוריתאנגלית
כותר פרסום המארח35th International Symposium on Distributed Computing, DISC 2021
עורכיםSeth Gilbert
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
מסת"ב (אלקטרוני)9783959772105
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוק׳ 2021
אירוע35th International Symposium on Distributed Computing, DISC 2021 - Virtual, Freiburg, גרמניה
משך הזמן: 4 אוק׳ 20218 אוק׳ 2021

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
ISSN (מודפס)1868-8969


כנס35th International Symposium on Distributed Computing, DISC 2021
עירVirtual, Freiburg

הערה ביבליוגרפית

Publisher Copyright:
© Leonid Barenboim and Tzalik Maimon; licensed under Creative Commons License CC-BY 4.0

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Deterministic logarithmic completeness in the distributed sleeping model'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי