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 add ress 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)) or bits (O(nlogn)) a node receives or sendscoincides with the lower bound, while ensuring only a linearruntime (O(n)) on the number of rounds.
2013
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://ris.uni-paderborn.de/record/564
Kniesburges S, Koutsopoulos A, Scheideler C. A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery. In: <i>Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)</i>. Lecture Notes in Computer Science. ; 2013:165-176. doi:<a href="https://doi.org/10.1007/978-3-319-03578-9_14">10.1007/978-3-319-03578-9_14</a>
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-03578-9_14
info:eu-repo/semantics/closedAccess