TY - GEN
T1 - Self-stabilizing resource discovery algorithm
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 - Massive distributed cooperative computing in networks involves marshaling large collections of network nodes possessing the necessary computational resources. In order for the willing nodes to act in a concerted way they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP). There are solutions for this problem that achieve impressive efficiency in the absence of failures, however, their correctness and performance cannot be guaranteed in the presence of failures. In practical environments it is important to have solutions that can cope with intermittent failures, and, in particular to design self-stabilizing algorithms for the problem. This paper presents a self-stabilizing algorithm that solves RDP in a deterministic synchronous setting. The 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 by nodes sharing knowledge through gossip messages with the goal of reducing its diameter. We prove that the algorithm is self-stabilizing, that is, the algorithm is able to tolerate arbitrary perturbations in the nodes' local states and is guaranteed to solve the problem once such failures subside. We show that the algorithm has stabilization time of O(logD), and it takes at most 2logD + 10 complete round to stabilize, where D is the diameter of the initial knowledge graph. The corresponding message complexity is O(|V|2·logD), where V is the set of participating nodes.
AB - Massive distributed cooperative computing in networks involves marshaling large collections of network nodes possessing the necessary computational resources. In order for the willing nodes to act in a concerted way they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP). There are solutions for this problem that achieve impressive efficiency in the absence of failures, however, their correctness and performance cannot be guaranteed in the presence of failures. In practical environments it is important to have solutions that can cope with intermittent failures, and, in particular to design self-stabilizing algorithms for the problem. This paper presents a self-stabilizing algorithm that solves RDP in a deterministic synchronous setting. The 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 by nodes sharing knowledge through gossip messages with the goal of reducing its diameter. We prove that the algorithm is self-stabilizing, that is, the algorithm is able to tolerate arbitrary perturbations in the nodes' local states and is guaranteed to solve the problem once such failures subside. We show that the algorithm has stabilization time of O(logD), and it takes at most 2logD + 10 complete round to stabilize, where D is the diameter of the initial knowledge graph. The corresponding message complexity is O(|V|2·logD), where V is the set of participating nodes.
KW - Distributed Algorithm
KW - Resource Discovery
KW - Self-Stabilization
UR - http://www.scopus.com/inward/record.url?scp=84893105933&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893105933&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03850-6_10
DO - 10.1007/978-3-319-03850-6_10
M3 - Conference contribution
AN - SCOPUS:84893105933
SN - 9783319038490
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 129
EP - 144
BT - Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Proceedings
T2 - 17th International Conference on Principles of Distributed Systems, OPODIS 2013
Y2 - 16 December 2013 through 18 December 2013
ER -