A deterministic worst-case message complexity optimal solution for resource discovery
Kniesburges, Sebastian
Koutsopoulos, Andreas
Scheideler, Christian
ddc:040
We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the address of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (O(n)O(n)) or bits (O(nlogn)O(nlogn)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (O(n)O(n)) on the number of rounds.
Elsevier
2015
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://ris.uni-paderborn.de/record/327
Kniesburges S, Koutsopoulos A, Scheideler C. A deterministic worst-case message complexity optimal solution for resource discovery. <i>Theoretical Computer Science</i>. 2015:67-79. doi:<a href="https://doi.org/10.1016/j.tcs.2014.11.027">10.1016/j.tcs.2014.11.027</a>
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2014.11.027
info:eu-repo/semantics/closedAccess