loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st IEEE Symposium on Reliable Distributed Systems (SRDS'02)
A Self-Stabilizing Algorithm for Finding Cliques in Distributed Systems
Osaka University, Suita, Japan
October 13-October 16
ISBN: 0-7695-1659-9
Hiroko Ishii, Fujitsu Nishi-Nihon Communication Systems, Ltd.
Hirotsugu Kakugawa, Hiroshima University
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.
Citation:
Hiroko Ishii, Hirotsugu Kakugawa, "A Self-Stabilizing Algorithm for Finding Cliques in Distributed Systems," srds, pp.390, 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.