A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

S. Kniesburges, A. Koutsopoulos, C. Scheideler, in:, Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO), 2013, pp. 165–176.

Download
Restricted 564-SIROCCO13.pdf 168.88 KB
Conference Paper
Author
; ;
Abstract
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.
Publishing Year
Proceedings Title
Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)
Page
165-176
LibreCat-ID

Cite this

Kniesburges S, Koutsopoulos A, Scheideler C. A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery. In: Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science.; 2013:165-176. doi:10.1007/978-3-319-03578-9_14.
Kniesburges, S., Koutsopoulos, A., & Scheideler, C. (2013). A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery. In Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO) (pp. 165–176). http://doi.org/10.1007/978-3-319-03578-9_14
@inbook{Kniesburges_Koutsopoulos_Scheideler_2013, series={Lecture Notes in Computer Science}, title={A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery}, DOI={10.1007/978-3-319-03578-9_14}, booktitle={Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)}, author={Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}, year={2013}, pages={165–176}, collection={Lecture Notes in Computer Science}}
Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” In Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO), 165–76. Lecture Notes in Computer Science, 2013. doi:10.1007/978-3-319-03578-9_14.
S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery,” in Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO), 2013, pp. 165–176.
Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler. “A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.” Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO). N.p., 2013. 165–176. Web. Lecture Notes in Computer Science.
Main File(s)
File Name
564-SIROCCO13.pdf 168.88 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T10:24:40Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar