episciences.org_622_1653755448
1653755448
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
11
12
2013
Vol. 15 no. 3
Distributed Computing and...
On the complexity of distributed BFS in ad hoc networks with nonspontaneous wakeups
Dariusz
Kowalski
Krzysztof
KrzywdziĆski
Distributed Computing and Networking
We study time and message complexity of the problem of building a BFS tree by a spontaneously awaken node in ad hoc network. Computation is in synchronous rounds, and messages are sent via pointtopoint bidirectional links. Network topology is modeled by a graph. Each node knows only its own id and the id's of its neighbors in the network and no preprocessing is allowed; therefore the solutions to the problem of spanning a BFS tree in this setting must be distributed. We deliver a deterministic distributed solution that trades time for messages, mainly, with time complexity O(D . min(D; n=f(n)) . logD . log n) and with the number of pointtopoint messages sent O(n. (min(D; n=f(n))+f(n)) . logD. log n), for any nnode network with diameter D and for any monotonically nondecreasing sublinear integer function f. Function f in the above formulas come from the threshold value on node degrees used by our algorithms, in the sense that nodes with degree at most f(n) are treated differently that the other nodes. This yields the first BFSfinding deterministic distributed algorithm in ad hoc networks working in time o(n) and with o(n2) message complexity, for some suitable functions f(n) = o(n= log2 n), provided D = o(n= log4 n).
11
12
2013
622
https://hal.archivesouvertes.fr/hal00965724v1
10.46298/dmtcs.622
https://dmtcs.episciences.org/622

https://dmtcs.episciences.org/622/pdf