A self-stabilizing algorithm for finding cliques in distributed systems

Self-stabilization is a theoretical framework of non-masking 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 P_j in a clique that a process P_i computes must agree on the result, i.e., the same clique must be obtained by P_j. We present a self-stabilizing algorithm to find cliques, and show its correctness and performance.