Um gültige Werte durch Abhängigkeiten zu erzeugen bzw. um die Konsistenz bzgl. der Constraint-Relationen zu überprüfen, werden Wertebereichsänderungen der Constraint-Variablen durch das Constraint-Netz propagiert. Constraint-Propagation bedeutet, dass sich Änderungen bzgl. des Wertebereichs einer Constraint-Variable an einer bestimmten Stelle im Constraint-Netz durch die Verknüpfungen der Constraints, und den in ihnen definierten Abhängigkeiten, auf andere involvierte Variablen bzw. ihrer Wertebereiche, auswirken:5.13
Die Beschränkung des Wertebereichs einer Variable hat Auswirkungen auf die Wertebereiche der übrigen Variablen, die mit dieser Variable im Constraint-Netz über ein Constraint in Verbindung stehen, d.h. wenn sie in demselben Constraint vorkommen. Deren eingeschränkten Wertebereiche schränken wiederum die Wertebereiche anderer Variablen ein usw. Die Änderungen breiten sich durch das Constraint-Netz aus: sie werden propagiert. Es verringert sich dadurch insgesamt die Anzahl der möglichen Belegungen.
Das Verfahren wurde erstmals von David L. Waltz zur automatischen Erkennung von Linienzeichnungen eingesetzt. Waltz (1975) verwendete die Propagationsmethode zur Interpretation von Linienzeichnungen dreidimensionaler Objekte (vgl. Abschnitt 5.2.1). Von Alan K. Mackworth wurde die Idee des Propagierens aufgegriffen und zum allgemeinen Konzept der Konsistenztechniken weiterentwickelt (vgl. Mackworth, 1977a).5.14 Im Wesentlichen werden eine Reihe von Konsistenzgraden unterschieden, die in Anlehnung an die Terminologie der Graphentheorie Knotenkonsistenz, Kantenkonsistenz, Pfadkonsistenz und k-Konsistenz genannt werden. In den folgenden Abschnitten werden diese Konsistenzgrade jeweils erläutert. Zu beachten ist, dass zur Herstellung einer bestimmten Konsistenz grundsätzlich unterschiedliche Algorithmen verwendet werden können.