Deterministic Logarithmic Completeness in the Distributed Sleeping Model
share
We provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model 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 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. 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.
READ FULL TEXT