Spezielle Kollisionsauflösung bei verteilter Verarbeitung
Verfasst: 29.01.2014, 13:46
Hallo ihr,
mich interessiert das zwecks Verteilung auf mehrere Rechner schon ziemlich lange. Folgendes Problem:
Ich verteile die Kollisionserkennung auf mehrere Rechner. Nicht jeder Rechner kennt alle Objekte, aber es ist sichergestellt, dass alle Kollisionen erkannt werden. Nun benötige ich einen Algorithmus, der bei der Kollisionsauflösung möglichst so arbeitet, dass theoretisch alle Kollisionen gleichzeitig aufgelöst werden können ohne jeden Rechner mit allen Objekten bekannt zu machen. Ich bin mir allerdings nicht sicher ob das überhaupt möglich ist bzw. zu einigermaßen stabilen Ergebnissen führt. Ein Beispiel:
Objekte: A, B, C, D
A überschneidet sich mit B und B mit C und C mit D -> [A,B], [B,C], [C,D]
Zwei Prozesse: P1, P2
P1 kennt nur die Objekte A und B
P2 kennt nur die Objekte B, C und D
Nun sollen A, B, C und D von P1 und P2 so angepasst werden, dass sie sich nicht mehr überschneiden. Normalerweise verlässt man sich dann ja, soweit ich weiß, auf die Reihenfolge der Auflösung. D.h. z.B. führt [C,D] zu einer Änderung, die dann bei der Auflösung von [B,C] berücksichtigt wird, die dann wieder bei der Auflösung von [A,B] berücksichtigt wird.
Was ich jetzt gerne hätte, wäre ein Algorithmus der damit klar kommt, dass P1 A und B versetzen kann ohne die Veränderungen von C und D zu kennen. Also dass bei der Auflösung der Kollisionen immer nur die direkt durch eine Kollision betroffenen Elemente beim Prozess bekannt sein müssen. D.h. P1 wird zwar über [B,C] informiert, nicht aber über [C,D].
Gibt es einen Algorithmus dieser Art?
Ist es ein gangbarer Weg mit einem getuntem Algorithmus in einem Schritt immer nur die direkt betroffenen Pärchen zu berücksichtigen?
Das letzte mal als ich das versucht habe, sind bestimmte Kombinationen aus Objekten je nach Lokalität wesentlich schlechter aufgelöst worden (eine natürliche Folge des gewählten Algorithmus)...
Gibt es einen sinnvollen Mechanismus die Ergebnisse der einzelnen Prozesse zu verschmelzen? Momentan mache ich es so, dass die Prozesse nacheinander die Auflösung machen und sich nach jedem Schritt über die gemeinsamen bekannten Elemente austauschen. Das ist war schneller als einen Prozess alleine arbeiten zu lassen, aber durch den gesuchten Algorithmus würde es natürlich noch viel schneller werden.
Vielen Dank und viele Grüße
Christian
mich interessiert das zwecks Verteilung auf mehrere Rechner schon ziemlich lange. Folgendes Problem:
Ich verteile die Kollisionserkennung auf mehrere Rechner. Nicht jeder Rechner kennt alle Objekte, aber es ist sichergestellt, dass alle Kollisionen erkannt werden. Nun benötige ich einen Algorithmus, der bei der Kollisionsauflösung möglichst so arbeitet, dass theoretisch alle Kollisionen gleichzeitig aufgelöst werden können ohne jeden Rechner mit allen Objekten bekannt zu machen. Ich bin mir allerdings nicht sicher ob das überhaupt möglich ist bzw. zu einigermaßen stabilen Ergebnissen führt. Ein Beispiel:
Objekte: A, B, C, D
A überschneidet sich mit B und B mit C und C mit D -> [A,B], [B,C], [C,D]
Zwei Prozesse: P1, P2
P1 kennt nur die Objekte A und B
P2 kennt nur die Objekte B, C und D
Nun sollen A, B, C und D von P1 und P2 so angepasst werden, dass sie sich nicht mehr überschneiden. Normalerweise verlässt man sich dann ja, soweit ich weiß, auf die Reihenfolge der Auflösung. D.h. z.B. führt [C,D] zu einer Änderung, die dann bei der Auflösung von [B,C] berücksichtigt wird, die dann wieder bei der Auflösung von [A,B] berücksichtigt wird.
Was ich jetzt gerne hätte, wäre ein Algorithmus der damit klar kommt, dass P1 A und B versetzen kann ohne die Veränderungen von C und D zu kennen. Also dass bei der Auflösung der Kollisionen immer nur die direkt durch eine Kollision betroffenen Elemente beim Prozess bekannt sein müssen. D.h. P1 wird zwar über [B,C] informiert, nicht aber über [C,D].
Gibt es einen Algorithmus dieser Art?
Ist es ein gangbarer Weg mit einem getuntem Algorithmus in einem Schritt immer nur die direkt betroffenen Pärchen zu berücksichtigen?
Das letzte mal als ich das versucht habe, sind bestimmte Kombinationen aus Objekten je nach Lokalität wesentlich schlechter aufgelöst worden (eine natürliche Folge des gewählten Algorithmus)...
Gibt es einen sinnvollen Mechanismus die Ergebnisse der einzelnen Prozesse zu verschmelzen? Momentan mache ich es so, dass die Prozesse nacheinander die Auflösung machen und sich nach jedem Schritt über die gemeinsamen bekannten Elemente austauschen. Das ist war schneller als einen Prozess alleine arbeiten zu lassen, aber durch den gesuchten Algorithmus würde es natürlich noch viel schneller werden.
Vielen Dank und viele Grüße
Christian