|
Published Articles >> Table of Contents >> Abstract
21st IEEE Symposium on Reliable Distributed Systems (SRDS'02)
p. 390
A Self-Stabilizing Algorithm for Finding Cliques in Distributed Systems
Hiroko Ishii, Fujitsu Nishi-Nihon Communication Systems, Ltd.
Hirotsugu Kakugawa, Hiroshima University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/RELDIS.2002.1180216
Send link to a friend
| Abstract |
|
Self-stabilization is a theoretical framework of nonmasking fault-tolerant algorithms in distributed systems. In this paper, we consider a problem to find fully connected subgraphs (cliques) in a network. In our problem setting, each process P in a network G is given a set of its neighbor processes as input, and must find a set of neighbors that are fully connected together with P. As constraints on solutions which make the problem non-trivial, each process must compute larger cliques as possible, and a process Pj in a clique that a process Pi computes must agree on the result, i.e., the same clique must be obtained by Pj. We present a self-stabilizing algorithm to find cliques, and show its correctness and performance.
|
 Additional Information
|
Citation:
Hiroko Ishii, Hirotsugu Kakugawa,
"A Self-Stabilizing Algorithm for Finding Cliques in Distributed Systems,"
srds,
p. 390,
21st IEEE Symposium on Reliable Distributed Systems (SRDS'02),
2002
|
|
