文章基本信息

标题：On the Cost of Waking Up
本地全文：下载
作者：Stefan Dobrev ; Rastislav Královic ; Nicola Santoro 等
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2017
卷号：7
期号：2
页码：336-348
语种：English
出版社：International Journal of Networking and Computing
摘要：Often, in a distributed system, a task must be performed in which all entities must be involved; however only some of them are active, while the others are inactive, unaware of the new computation that has to take place. In these situations, all entities must become active, a task known as Wake-Up. It is not difficult to see that Broadcast is just the special case of the Wake-Up problem, when there is only one initially active entity. Both problems can be solved with the same trivial but expensive solution: Flooding. More efficient broadcast protocols exist for some classes of dense interconnection networks. The research question we examine is whether also wake-up can be performed significantly better in three classes of regular interconnection networks: hypercubes, complete networks, and regular complete bipartite graphs.In a d-dimensional hypercube network of n nodes, the cost of broadcasting is Theta(n) even if the edge labeling is arbitrary and the network is asynchronous. We show that, instead, wake-up requires Omega(n log n) message transmissions in the worst case, even if the network is synchronous and has sense of direction. Similarly, in a regular complete bipartite network Kp,p of n=2p anonymous entities the cost of broadcasting is Theta(n) even if the edge labeling is arbitrary and the network is asynchronous; instead, we show that wake-up requires Theta(n2) message transmissions in the worst case, even if the network is synchronous and has sense of direction.In a complete network Kn of n entities, the cost of broadcasting is minimal: n-1 message transmissions suffice even if the entities are anonymous. In this paper we prove that the cost of wake-up is order of magnitude higher. In the case of anonymous entities, Omega(n2) message transmissions are needed in the worst case, even if the network is fully synchronous and has sense of direction. In the case of entities with distinct ids, Omega(n log n) transmissions need to be performed and the bound is tight. This shows that, when the entities have Ids, Wake-Up is computationally as costly as the apparently more complex Election problem.
其他摘要：Often, in a distributed system, a task must be performed in which all entities must be involved; however only some of them are active, while the others are inactive, unaware of the new computation that has to take place. In these situations, all entities must become active, a task known as Wake-Up. It is not difficult to see that Broadcast is just the special case of the Wake-Up problem, when there is only one initially active entity. Both problems can be solved with the same trivial but expensive solution: Flooding. More efficient broadcast protocols exist for some classes of dense interconnection networks. The research question we examine is whether also wake-up can be performed significantly better in three classes of regular interconnection networks: hypercubes, complete networks, and regular complete bipartite graphs. In a d -dimensional hypercube network of n nodes, the cost of broadcasting is Theta( n ) even if the edge labeling is arbitrary and the network is asynchronous. We show that, instead, wake-up requires Omega( n log n ) message transmissions in the worst case, even if the network is synchronous and has sense of direction. Similarly, in a regular complete bipartite network K p,p of n =2 p anonymous entities the cost of broadcasting is Theta( n ) even if the edge labeling is arbitrary and the network is asynchronous; instead, we show that wake-up requires Theta( n 2 ) message transmissions in the worst case, even if the network is synchronous and has sense of direction. In a complete network K n of n entities, the cost of broadcasting is minimal: n -1 message transmissions suffice even if the entities are anonymous. In this paper we prove that the cost of wake-up is order of magnitude higher. In the case of anonymous entities, Omega( n 2 ) message transmissions are needed in the worst case, even if the network is fully synchronous and has sense of direction. In the case of entities with distinct ids, Omega( n log n ) transmissions need to be performed and the bound is tight. This shows that, when the entities have Ids, Wake-Up is computationally as costly as the apparently more complex Election problem.
关键词：distributed algorithms; message complexity; sense of direction;complete networks;complete bipartite graphs;hypercubes;wake-up;reset;election