We study the design of energy-efficient algorithms for the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of...
详细信息
ISBN:
(纸本)9783031327322;9783031327339
We study the design of energy-efficient algorithms for the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is active in the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages for only O(1) rounds during the whole execution of the algorithm. In other words, every Turing-computable problem can be solved by an algorithm consuming the least possible energy. In the LOCAL model, the same holds obviously, but with the additional feature that the algorithm runs in O(poly(n)) rounds in n-node networks. However, we show that insisting on algorithms running in O(poly(n)) rounds in the CONGEST model comes with a severe cost in terms of energy. Namely, there are problems requiring O(poly( n)) edge-activations (and thus O(poly( n)) node-activations as well) in the CONGEST model whenever solved by algorithms bounded to run in O(poly(n)) rounds. Finally, we demonstrate the existence of a sharp separation between the edge-activation complexity and the node-activation complexity in the CONGEST model, for algorithms bounded to run in O(poly(n)) rounds. Specifically, under this constraint, there is a problem with O(1) edge-activation complexity but (Omega) over tilde (n(1/4)) node-activation complexity.
Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions...
详细信息
Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case. and iterative algorithms for systems of linear equations. in the pulse-driven case. We provide some experimental evidence in these two cases. (c) 2008 Elsevier B.V. All rights reserved.
A distributed algorithm to find a maximal independent set of an undirected graph is proposed. It is borrowed by a centralized one and it is based on a sequence of Hopfield neural networks. We refer to the synchronous ...
详细信息
ISBN:
(纸本)3540442650
A distributed algorithm to find a maximal independent set of an undirected graph is proposed. It is borrowed by a centralized one and it is based on a sequence of Hopfield neural networks. We refer to the synchronous model of distributed computation in which the topology is described by the graph. We give an upper bound on the number of messages sent during the entire process of computation. To test the algorithm we experimentally compare it with a probabilistic heuristic derived by Ant Colony Optimization technique and with the standard greedy algorithm.
暂无评论