2013/06/07 by Sebastian Kniesburges, Kniesburges, Sebastian, Andreas Koutsopoulos +3
Computer Science · #Caching and Content Delivery #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1306.1692
Full Version of Sirocco 2013 paper
arxiv created 2013/06/07 · openalex publication_date 2013/06/07 · arxiv updated 2013/06/10 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
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)) or bits (O(n log n)) a node receives or sends coincides with the lower bound, while ensuring only a linear runtime (O(n)) on the number of rounds.