ﻻ يوجد ملخص باللغة العربية
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need $Omega(log n)$ and $Omega(log^2 n)$ energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ($Omega(n)$) time. In the CD and No-CD models we can solve broadcast using $O(frac{log nloglog n}{logloglog n})$ energy and $O(log^3 n)$ energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant $epsilon>0$, broadcast can be solved in $O(D^{1+epsilon}log^{O(1/epsilon)} n)$ time with $O(log^{O(1/epsilon)} n)$ energy, where $D$ is the diameter of the network.
We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds. -- For an
In this paper, we consider the Byzantine reliable broadcast problem on authenticated and partially connected networks. The state-of-the-art method to solve this problem consists in combining two algorithms from the literature. Handling asynchrony and
In virtualized data centers, consolidation of Virtual Machines (VMs) on minimizing the number of total physical machines (PMs) has been recognized as a very efficient approach. This paper considers the energy-efficient consolidation of VMs in a Cloud
The problem of attaining energy efficiency in distributed systems is of importance, but a general, non-domain-specific theory of energy-minimal scheduling is far from developed. In this paper, we classify the problems of energy-minimal scheduling and
The Reliable Broadcast concept allows an honest party to send a message to all other parties and to make sure that all honest parties receive this message. In addition, it allows an honest party that received a message to know that all other honest p