### On the Cost of Waking Up

#### Abstract

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.

#### Keywords

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.