Der Parallel Search Algorithmus zeichnet sich im wesentlichen durch folgende Eigenschaften aus:

• Jeder Prozessor hat einen eigenen (unique) Teil des Suchraums.
• Die Kommunikation zwischen den Prozessoren wird minimal gehalten.
• Jeder Prozessor benutzt seinen eigenen sequentiellen Algorithmus
• Der Suchraum wird bis zur Lösung oder "dead-end" durchsucht.
• Suchräume werden auf Anfrage geteilt.

Initial werden der Suchraum zwischen den Prozessoren aufgeteilt. Jeder Prozessor durchsucht seinen Untersuchraum mit Hilfe seines sequentiellen Algorithmus. Hat ein Prozessor seinen Suchraum durchsucht und keine Lösung gefunden, so bekommt er die Hälfte des Suchraums eines anderen Prozessors. Die Prozessoren tauschen evtl. dead-ends (Belegungen für bestimmte Variablen bei denen keine Lösung möglich ist) untereinander aus. Wenn eine Lösung existiert, wird sie gefunden, wonach der Algorithmus terminiert.

Wie schon in 2.2 erläutert, garantiert dieser Algorithmus fast immer einen Zeitgewinn gegenüber den sequentiellen Algorithmen. Im worst case liegt der Zeitaufwand knapp über dem eines sequentiellen Algorithmus, was auf den Aufwand zur Aufteilung der Suchräume und zum Starten der Prozessoren zurückzuführen ist.

Der Algorithmus Parallel Check Forwards basiert auf dem Algorithmus check_forwards (siehe (1)) und nutzt die freien Prozessoren (Hardware) im System um das domain filtering parallel zu betreiben. Dabei wird die maximale Ausnutzung der vorhandenen Hardware angestrebt. Für diesen Algorithmus ist shared-memory erforderlich. Der Algorithmus sieht folgendermaßen aus (in pseudocode):

 FUNCTION parallel_check_forwards(i, j, k) : INTEGER
     // i,j,k - Indizes auf die Menge der Variablen


BEGIN
	consistent ß true;
	m ß j-1;
	WHILE consistent and m <= k DO
	BEGIN
		m ß m+1;
		fork(check_forwards(i, m, consistent));
		    // einen neuen Prozeß kreieren.
	END;
	return (consistent);
END;

Wie auch andere funktionsbasierten Algorithmen ist Parallel Check Forwards wegen des zusätzlichen Aufwands für das Kreieren neuer Prozesse nur bei großen Problemen anwendbar.