A self-stabilizing algorithm for maximal 2-packing

Abstract

In the self-stabilizing algorithmic paradigm for distributed computing each node has only a local view of the system, yet in a finite amount of time the system converges to a global state, satisfying some desired property. In a graph G = (V, E), a subset S ⊆ V is a 2-packing if ∀u ∈ V: |N [u] ∩ S | ≤ 1. In this paper we present an ID-based, self-stabilizing algorithm for finding a maximal 2-packing, a non-local prop-erty, in an arbitrary graph. We also show how to use Markov analysis to analyse the behaviour of a non-ID-based version of the algorithm.