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