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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 أكتوبر 2021
الحدث35th International Symposium on Distributed Computing, DISC 2021 - Virtual, Freiburg, ألمانيا
المدة: ٤ أكتوبر ٢٠٢١٨ أكتوبر ٢٠٢١

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت209
رقم المعيار الدولي للدوريات (المطبوع)1868-8969


!!Conference35th 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'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا