Die Wahl des Spenders erfolgt nach denselben
Kriterien wie beim Parallelen Backtracking, d.h.,
entweder existiert eine zentrale Datenstruktur (z.B. Heap),
oder Teilaufgaben werden von anderen Prozessoren angefordert.
Bei Verwendung einer zentralen Datenstruktur
erhält der anfordernde Prozessor das günstigste
Problem.
Nachdem er es expandiert hat, werden
die Nachfolger wieder eingefügt.
Bei verteilter Datenhaltung verwaltet jeder
Prozessor einen lokalen Heap, aus dem er das
jeweils günstigste Problem entfernt und nach
der Expansion die Nachfolger wiederum einfügt.
Um zu vermeiden, daß Prozessoren an ungünstigen
Problemen arbeiten, obwohl im Netzwerk günstigere
existieren, verteilt ein Prozessor von Zeit zu Zeit
einige seiner günstigsten Teilprobleme an andere
Prozessoren.
Je nach Topologie werden beliebige
Empfänger gewählt oder auch nur Nachfolger und
Vorgänger bzgl. eines fest gewählten Hamiltonkreises
im Netzwerk.
Die Wahl des Zeitpunkts zum Informationsaustausch mit
den Nachbarn kann z.B. ausgelöst werden durch das
Ansteigen der lokalen unteren Schranke.
Eine andere Methode basiert auf einem andauernden
Versenden eigener günstiger Probleme.
Erhält Prozessor A vom Nachbarn B günstigere
Probleme, als er selbst hat, so wird die Sendefrequenz
für Kanal AB auf ``niedrig'' gesetzt;
erhält Prozessor A
vom Nachbarn B ungünstigere Probleme, als er selbst hat,
so wird die Sendefrequenz für Kanal AB auf ``hoch'' gesetzt.
Als Ergebnis der Lastverteilung gleichen sich die
lokalen unteren Schranken an, wodurch ein
globaler Heap, auf den mehrere Prozessoren
zugreifen, simuliert wird.
Bei Suchverfahren in Zustandsgraphen, die
mehrfache Exploration durch Abgleich mit der OPEN-List und
der CLOSED-List vermeiden wollen, entsteht im
parallelen Fall zusätzlicher Overhead:
Durch eine Hashfunktion f wird jeder Knoten des
Suchraums auf eine Prozessorkennung
0,...,p - 1
abgebildet.
Ein Prozessor, der einen Knoten x erzeugt,
schickt ihn zur weiteren Bearbeitung an
Prozessor f (x) , der ihn mit dem Bestand seiner
lokalen Listen abgleicht.