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

DOI10.1007/978-3-319-03578-9_14MaRDI QIDQ2868642zbMATH OpenOpenAlexFDO

Authors Sebastian Kniesburges, Andreas Koutsopoulos, Christian Scheideler

Publication date 17 December 2013

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.1692

zbMATH Keywords

distributed algorithmsself-stabilizationresource discoveryclique network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Distributed systems (68M14)

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 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.

Recommendations

• A deterministic worst-case message complexity optimal solution for resource discovery
• Deterministic resource discovery in distributed networks
• Distributed resource discovery in sub-logarithmic time
• On the message complexity of distributed problems
• Complexity and approximations for multimessage multicasting
• Resource Bounds for Self-Stabilizing Message-Driven Protocols
• A note on the message complexity of Cidon's distributed depth-first search algorithm

Cites work

• scientific article; zbMATH DE number 2079362 (Why is no real title available?)
• scientific article; zbMATH DE number 2080510 (Why is no real title available?)
• scientific article; zbMATH DE number 2080852 (Why is no real title available?)
• A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
• A self-stabilizing and local Delaunay graph construction
• Discovery through gossip
• Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
• Fast self-stabilizing minimum spanning tree construction. Using compact nearest common ancestor labeling scheme
• Group-based cryptography
• Novel architectures for P2P applications: the continuous-discrete approach
• Reaching Agreement in the Presence of Faults
• Resource discovery in distributed networks
• Self-stabilizing minimum degree spanning tree within one from the optimal degree
• Self-stabilizing systems in spite of distributed control
• The hyperring: a low-congestion deterministic data structure for distributed environments
• Viceroy, a scalable and dynamic emulation of the butterfly

Cited in

(4)

• Deterministic resource discovery in distributed networks
• A deterministic worst-case message complexity optimal solution for resource discovery
• Distributed resource discovery in sub-logarithmic time
• Asynchronous resource discovery

Describes a project that uses

Uses Software

• Pastry
• Chord

This page was built for publication: A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868642)