Loading...
Please wait, while we are loading the content...
Similar Documents
Energy-efficient distributed minimum spanning tree construction: tight bounds and algorithms.
| Content Provider | CiteSeerX |
|---|---|
| Author | Choi, Yongwook |
| Abstract | Traditionally, the performance of distributed algorithms has been measured in terms of running time and message complexity. However, in many settings, a more accurate and relevant measure of performance is required. In ad hoc wireless networks, energy is a very critical factor for measuring the efficiency of a distributed algorithm. Thus in addition to the traditional time and message complexity, it is also relevant to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper focuses on the energy complexity of distributed algorithms for the Euclidean minimum spanning tree (MST) problem, one of the most important problems in distributed computing. We show tight upper and lower bounds on the energy complexity of distributed (Euclidean) MST algorithms. We also study distributed approximation algorithms for MST that have almost optimal energy complexity, but give a constant factor approximation to the MST. We present two sets of results, one where nodes are distributed randomly in a plane, and the other where nodes can be arbitrarily distributed. For random distribution of nodes, we show that Ω(log n) is a lower bound on the energy complexity of any distributed MST algorithm. We then give a distributed algorithm that constructs an optimal MST with O(log n) energy complexity on |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Energy Complexity Distributed Algorithm Tight Bound Message Complexity Traditional Time Tight Upper Distributed Computing Many Setting Distributed Mst Algorithm Mst Algorithm Critical Factor Constant Factor Approximation Ad Hoc Wireless Network Optimal Mst Important Problem Relevant Measure Optimal Energy Complexity Approximation Algorithm Random Distribution Euclidean Minimum Total Energy |
| Content Type | Text |
| Resource Type | Article |
