TY - GEN
T1 - Brief announcement
T2 - 2013 ACM Symposium on Principles of Distributed Computing, PODC 2013
AU - Davtyan, Seda
AU - Konwar, Kishori M.
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2013
Y1 - 2013
N2 - Distributed cooperative computing in networks involves marshaling collections of network nodes possessing the necessary computational resources. Before the willing nodes can act in a concerted way they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP). This paper presents a self-stabilizing algorithm that solves RDP in a deterministic synchronous setting. The solution approach is formulated in terms of evolving knowledge graphs, where vertices represent the participating network nodes, and edges represent one node's knowledge about another. Ideally, the diameter of such a graph is one, i.e., each node knows all others. The algorithm works in rounds as it evolves the knowledge graph with the goal of reducing its diameter. This is accomplished by nodes sharing their knowledge through gossip messages. We prove that the algorithm is self-stabilizing, i.e., it tolerates arbitrary perturbations in the nodes' local states and is guaranteed to solve the problem once such failures subside. The algorithm has stabilization time of O(D), and it takes at most 4D + 4 complete round to stabilize, where D is the diameter of the initial knowledge graph, and the corresponding message complexity is O(|V| · D), where V is the set of participating nodes.
AB - Distributed cooperative computing in networks involves marshaling collections of network nodes possessing the necessary computational resources. Before the willing nodes can act in a concerted way they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP). This paper presents a self-stabilizing algorithm that solves RDP in a deterministic synchronous setting. The solution approach is formulated in terms of evolving knowledge graphs, where vertices represent the participating network nodes, and edges represent one node's knowledge about another. Ideally, the diameter of such a graph is one, i.e., each node knows all others. The algorithm works in rounds as it evolves the knowledge graph with the goal of reducing its diameter. This is accomplished by nodes sharing their knowledge through gossip messages. We prove that the algorithm is self-stabilizing, i.e., it tolerates arbitrary perturbations in the nodes' local states and is guaranteed to solve the problem once such failures subside. The algorithm has stabilization time of O(D), and it takes at most 4D + 4 complete round to stabilize, where D is the diameter of the initial knowledge graph, and the corresponding message complexity is O(|V| · D), where V is the set of participating nodes.
KW - Distributed Cooperation
KW - Fault-Tolerance
KW - Resource Discovery
KW - Self-Stabilization
UR - http://www.scopus.com/inward/record.url?scp=84883497259&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883497259&partnerID=8YFLogxK
U2 - 10.1145/2484239.2484277
DO - 10.1145/2484239.2484277
M3 - Conference contribution
AN - SCOPUS:84883497259
SN - 9781450320658
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 116
EP - 118
BT - PODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing
Y2 - 22 July 2013 through 24 July 2013
ER -