ParAlg, Kapitel 6.4

6.4 MPC: Relationen und Funktionen auswerten

Eine Relation - genauer gesagt, eine binäre Relation - zwischen zwei Mengen $X$ und $Y$ ist eine Teilmenge $R \subseteq (X, Y)$ . Hier sehen Sie als Beispiel die Relation Amtssprachen, dargestellt als bipartiter Graph:

Die Abbildung ist nicht vollständig; weder sind alle Sprachen aufgeführt noch alle Länder. Beachten Sie, dass die USA keine offizielle Amtssprache haben. Als mathematisches Objekt betrachtet ist obige Abbildung eine Relation $R \subseteq X \times Y$ mit $X = {U, D, S, B, N, I}$ und $Y = {e, f, d, n, i}$ und

\begin{array}{r} R = {(D, d), (S, f), (S, d), (S, i), (B, f), (B, d), (B, n), (N, n), (I, d), (I, i)} . \end{array}

Im MPC-Modell ist eine Relation dadurch gegeben, dass die Elemente aus $R$ (also geordnete Paare aus $X \times Y$ ) beliebig verteilt auf den Maschinen liegen. In diesem Teilkapitel wollen wir einen effizienten MPC-Algorithmus für folgendes Problem entwickeln:

Problem 6.4.1 (Relation auswerten). Die Eingabe zu diesem Problem besteht aus einer Relation $R \subseteq X \times Y$ (als Menge von Daten-Items $(x, y)$ beliebig über die Maschine verteilt), sowie einer Menge von Query-Items der Form $(x, ?)$ . Hierbei darf das gleiche Query-Item $(x, ?)$ auf mehreren Maschinen vorkommen. Ziel ist es,

eine Funktion $f : X \to Y \cup {⊥}$ zu berechnen, sich also für jedes $x \in X$ auf ein $y \in Y$ zu einigen, für das $(x, y) \in Y$ gilt, bzw. auf $⊥$ , falls es kein solches gibt;
dass jede Maschine, die anfangs ein Query-Item $(x, ?)$ hält, am Schluss der Berechnung das Item $(x \mapsto f (x))$ hat.

In Worten: jede Maschine, die anfangs $(x, ?)$ hat, kennt am Ende ein $y$ mit $(x, y) \in R$ (oder weiß nun, dass es kein solches gibt), und dieses $y$ ist das gleiche für alle Maschinen, die anfangs $(x, ?)$ haben.

Theorem 6.4.2 Gegeben sei eine Relation $R \subseteq X \times Y$ und eine Menge von Query-Items $Q \subseteq X \times {?}$ . Sei $N$ die Gesamtzahl aller Items: $N = | R | + | Q |$ . Dann können $P = O (N^{1 - ϵ})$ Prozessoren mit jeweils $S = O (N^{ϵ})$ Speicher in $O (1 / ϵ)$ Runden die Relation auswerten.

Algorithmus. Anfangs liegen Daten-Items und Query-Items beliebig über die Maschinen verteilt. Hier ein Beispiel mit sechs Maschinen und fünf Items pro Maschine.

Beachten Sie, dass Maschine $3$ zum Beispiel das Daten-Item $(I, i)$ hat, dieses jedoch nicht unmittelbar verwenden kann, um die Query $(I, ?)$ zu beantworten: sie muss ja sicherstellen, dass alle Machinen mit Query $(I, ?)$ sich auf die gleiche Antwort einigen!

Maschine $M_{i}$ fügt jedem Item $(x, *)$ ihren Index hinzu, erzeugt also $(x, *, i)$ ; das $i$ dient als Rücksendeadresse. Nun sortieren wir alle Items, und zwar vorrangig nach der ersten Koordinate, also dem $x \in X$ und nachrangig nach der zweiten, also dem Element in $Y \cup {?}$ , wobei $?$ als letztes in dieser Ordnung kommt. Hier ist das Ergebnis als Liste (die Aufteilung der Maschinen zeigen wir hier nicht an; wir gehen aber davon aus, dass die ersten $S$ Items der Liste auf Maschine $1$ liegen; die zweiten $S$ Items der Liste auf Maschine 2 und so weiter).

(B, d, 5)
(B, f, 4)
(B, n, 6)
(B, ?, 1)
(B, ?, 2)
(B, ?, 3)
(B, ?, 4)
(B, ?, 6)
(D, d, 4)
(D, ?, 1)
(D, ?, 2)
(D, ?, 3)
(D, ?, 4)
(D, ?, 5)
(I, d, 4)
(I, i, 3)
(I, ?, 2)
(I, ?, 3)
(I, ?, 5)
(I, ?, 6)
(N, n, 1)
(N, ?, 5)
(S, d, 6)
(S, f, 3)
(S, i, 1)
(S, ?, 1)
(S, ?, 2)
(U, ?, 2)
(U, ?, 5)
(U, ?, 6)

Wir bilden auf diesem Array nun eine Präfixsumme, wobei wir immer die neueste Antwort "mitschleppen", solange diese die aktuelle Frage beantwortet. Formal definieren wir uns eine Verknüpfungsoperation $\circ$ auf der Menge der Items wie folgt:

\begin{array}{r} d_{1} \circ d_{2} := {\begin{cases} (x, y, i) & wenn d_{2} = (x, ?, i) und d_{1} = (x, y, *) \\ d_{2} & sonst. \end{cases} \end{array}

In Worten: $d_{1} \circ d_{2}$ ist $d_{2}$ , außer wenn $d_{2}$ eine Query ist und $d_{1}$ die Antwort darauf enthält, in welchem Falle wir diese Antwort übernehmen. Überzeugen Sie sich davon, dass $\circ$ assoziativ ist. Wir können nun in $O (1 / ϵ)$ Runden alle Präfixsummen berechnen. Aus technischen Gründen gehen wir davon aus, dass jeder Item in der Präfixsumme "weiß", ob er ursprünglich ein Query-Item oder ein Daten-Item gewesen ist; wir markieren Daten-Items hier mit einem Stern. Hier noch einmal die sortierte Liste und daneben die Präfixsummen:

(B, d, 5)*      (B, d, 5)*      
(B, f, 4)*      (B, f, 4)*
(B, n, 6)*      (B, n, 6)*
(B, ?, 1)       (B, n, 1)
(B, ?, 2)       (B, n, 2)
(B, ?, 3)       (B, n, 3)
(B, ?, 4)       (B, n, 4)
(B, ?, 6)       (B, n, 6)
(D, d, 4)*      (D, d, 4)*
(D, ?, 1)       (D, d, 1)
(D, ?, 2)       (D, d, 2)
(D, ?, 3)       (D, d, 3)
(D, ?, 4)       (D, d, 4)
(D, ?, 5)       (D, d, 5)
(I, d, 4)*      (I, d, 4)*
(I, i, 3)*      (I, i, 3)*
(I, ?, 2)       (I, i, 2)
(I, ?, 3)       (I, i, 3)
(I, ?, 5)       (I, i, 5)
(I, ?, 6)       (I, i, 6)
(N, n, 1)*      (N, n, 1)*
(N, ?, 5)       (N, n, 5)
(S, d, 6)*      (S, d, 6)*
(S, f, 3)*      (S, f, 3)*
(S, i, 1)*      (S, i, 1)*
(S, ?, 1)       (S, i, 1)
(S, ?, 2)       (S, i, 2)
(U, ?, 2)       (U, i, 2)
(U, ?, 5)       (U, i, 5)
(U, ?, 6)       (U, i, 6)

Jetzt schicken wir alle Ergebnisse der Präfixsumme an die jeweilige Rücksendeadresse zurück und erhalten folgendes Bild:

Die Rücksendeadresse haben wir hier weggelassen, weil sie jetzt nicht mehr interessant ist. Die Sternchen sind wichtig, weil nun zum Beispiel Maschine die Items $(B, n)$ und $(B, f) *$ qualitativ auseinanderhalten kann: sie weiß, dass $(B, f) *$ ein Daten-Item ist (welches besagt, dass französisch eine Amtssprache in Belgien ist), während $(B, n)$ besagt, dass sich die Maschinen darauf geeinigt haben, für Belgien Niederländisch als Sprache auszuwählen.

Laufzeit. Wie wir in Kapitel 6.3 gesehen haben, können wir in $O (1 / ϵ)$ Runden sortieren. Die Präfixsummen können wir wiederum in $O (1 / ϵ)$ Runden berechnen. Somit braucht der gesamte Algorithmus $O (1 / ϵ)$ Runden. Da es vielleicht etwas zu abstrakt ist, was ich mit Präfixsummen mit Verknüpfung $\circ$ berechnen meine, zeichne ich hier nochmal den Baum, den der Präfixsummen-Algorithmus verwendet. In meinem Beispiel ist das ein Baum mit Verzweigung $3$ ; im Ernstfall hat er Verzweigung $S$ und somit Höhe $\log_{S} P \leq 1 / ϵ$ :

Falls es zu $x \in X$ kein $y \in Y$ mit $(x, y) \in R$ gibt, so wird $(x, ?)$ am Schluss $(x, ?)$ bleiben und die betreffende Maschine weiß somit, dass es kein passendes $y$ gibt. Das ist im obigen Beispiel für $(U, ?)$ der Fall: die USA haben keine offizielle Amtssprache.