In order to realize the cooperation of a group of multiple nodes, messages have to be reliably and efficiently delivered to all of them, according to a traditional broadcasting paradigm, by also reducing the electric ...
详细信息
In order to realize the cooperation of a group of multiple nodes, messages have to be reliably and efficiently delivered to all of them, according to a traditional broadcasting paradigm, by also reducing the electric energy consumed by each involved node. In this paper, we propose three types of energy-efficient broadcast algorithms, namely EEB (energy-efficient broadcast), EEB2 (modified EEB), and AEEB (augmented EEB) whose objective is reducing the total electric energy consumed by nodes. In the EEB algorithm, a wireless link to a farthest child node is truncated until there is no other child node which can forward messages to it in a more energy-efficient way. In the EEB2 algorithm, a link to a farthest child node is truncated if there is another child node which can forward the message to it. In the EEB and EEB2 algorithms, a child node is selected for each parent node. On the other hand, one parent node is selected among possible parent nodes of each child node, which is nearest to the child node in the AEEB algorithm. We evaluate the EEB, EEB2, and AEEB algorithms and show that the total electric energy consumed by nodes can be reduced in the AEEB algorithm.
Distributed systems are inherently complex as they need to address the interplay between features like communication, concurrency, and failure. Due to the inherent complexity of these interacting features, it is typic...
详细信息
ISBN:
(纸本)9781450380492
Distributed systems are inherently complex as they need to address the interplay between features like communication, concurrency, and failure. Due to the inherent complexity of these interacting features, it is typically not possible to systematically test these kind of systems;yet, unexpected and unlikely combinations of events might cause corner cases that are hard to find. But since these systems are running typically for long durations, these events are likely to materialize eventually and must be handled correctly. Caught in such a dilemma, students are able to experience the benefits of applying verification tools to check their own algorithms and implementations. Having executable models with automatically generated executions allows them to experiment with different solutions by iteratively adapting and refining their algorithms. In this experience report, we report on our experience of teaching verification in a ( hands-on) distributed systems course. We argue that broadcast algorithms provide a sweet spot in design and verification complexity. To this end, we give an implementation of these algorithms in Erlang and derive a TLA+ specification. TLA+ is a formal language for describing and reasoning about distributed and concurrent systems and provides a model checker, TLC, among other things. Our study reveals interesting parallels between the Erlang and TLA+ code, while exposing the challenges of formally modeling communication and parallelism in distributed systems. Presenting selected aspects of our course design, we aim to motivate the feasibility and need for introducing verification in close correspondence to programming tasks.
In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the br...
详细信息
ISBN:
(纸本)9781581134865
In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.
暂无评论