6.2 Sortieren

Die Eingabe besteht aus einer Menge $X$ von Items $x$ aus einem geordneten Universum. Das Ziel ist es, diese Menge zu sortieren. Was heißt das im MPC-Kontext? Wir betrachten die Menge $X$ als sortiert, wenn jeder Item $x$ durch einen Item $(i,x)$ ersetzt worden ist, wobei $i=\text{rank}(x,X)$ ist. Dann hätten wir $X$ in ein Array im Sinne von Übungsaufgabe 6.1.2 umgewandelt und somit in jedem vernünftigen Sinne sortiert. In Worten: am Ende des Algorithmus soll jedes Element seinen Rang kennen.

Unser Algorithmus ist eine MPC-Version von Quicksort. Die Idee ist es, nicht ein Pivot, sondern eine ganze Menge $Y$ von Pivots zu wählen. Die Pivots $Y$ zerteilen die Menge $X$ in mehrere Teilintervalle oder Unterprobleme. Über einen Baum ähnlich wie in Theorem 6.1.2 senden wir dann alle Pivots zu einer zentralen Maschine, welche sie lokal sortiert (was als ein Schritt zählt) und als sortierte Menge wieder an alle Maschinen aussendet. Jede Maschine bestimmt dann (lokal, also in einem Schritt) für jedes ihrer Items, zu welchem Unterproblem es gehört. Nun lösen wir rekursiv jedes Unterproblem.

Eine Schwierigkeit besteht darin, dass wir die Maschinen irgendwie den Unterproblemen zuordnen müssen; also (1) bestimmen, an welchem Unterproblem $j$ die Maschine $i$ arbeiten soll und (2) erreichen müssen, dass alle Items, die zu Unterproblem $j$ gehören, auf den zuständigen Maschinen landen. Problem (1) wird einen weiteren "Baum-Broadcast" erfordern; Problem (2) lösen wir mit Randomisierung.

MPC-Quicksort

Als erstes wollen wir eine Menge $Y$ von $\sqrt{S}=N^{ϵ/2}$ zufällig Pivots wählen, und zwar in einem Schritt, also ohne Kommunikation. Dies geht näherungsweise und mit Randomisierung: wenn wir jeden Item $x$ mit Wahrscheinlich $p$ markieren, dann gilt für die Menge $Y$ von markierten Items:

$$\begin{array}{rl}\mathbb{E}[|Y|]& =\sum _{x\in X}Pr[x\text{ ist markiert}]=p\cdot N.\end{array}$$

Wir wollen $\mathbb{E}[|Y|]=\frac{\sqrt{S}}{2}$ erreichen: die Menge $Y$ der Pivots soll auf keinen Fall mehr als $\sqrt{S}$ Elemente enthalten, und der Faktor $1/2$ dient als Sicherheitsabstand. Wir wählen also $p=\frac{\sqrt{S}}{2N}$.

Warum die Behauptung gilt und was überhaupt "mit großer Wahrscheinlichkeit" heißt, das schauen wir uns weiter unten genauer an. Im Moment gehen wir einfach davon aus, dass $|Y|\le \sqrt{S}$ gilt. Die Pivots $Y$ liegen über alle Maschinen verteilt. Wir wollen sie auf einer bestimmte Maschine, zum Beispiel Maschine 1, sammeln.

Maschine $1$ hält nun (neben ihren "normalen" Eingabe-Items) die Menge $Y$. Sie sortiert sie lokal, bestimmt somit für jedes $y\in Y$ seinen Rang $j=\text{rank}(y,Y)$ und bildet den "indizierten" Item $(j,y)$. Wir bezeichnen diese indizierte Menge $\{(\text{rank}(y,Y),y)|y\in Y\}$ als $\hat{Y}$. Dann sendet Maschine $1$ die Menge $\hat{Y}$ an alle Maschinen; dies geht wiederum in $2\lambda$ Runden, analog zu Übungsaufgabe 6.2.1. Alle Maschinen kennen nun also die Pivots $y_1<y_2<\cdots <y_k$ in aufsteigender Reihenfolge (mit $k:=|Y|)$. Dies unterteilt $X$ in Teilintervalle / Unterprobleme. Formal: das Teilproblem $X_j$ ( für $0\le j\le k$) ist die Menge $$\begin{array}{r}{X}_j:=\{x\in X|\text{rank}(x,Y)=j\}.\end{array}$$ Jede Maschine bestimmt nun $\text{rank}(x,Y)$ für jeden ihrer Items $x$ und weiß nun, zu welchem Teilproblem $x$ gehört; ganz konkret ersetzt sie $x$ durch $⟨x,\text{rank}(x,Y)⟩$. Dies geht lokal, also in einer Runde. Jede Maschine $i$ kennt nun die Anzahl $N_{i,j}$ ihrer Items, die zu Teilproblem $j$ gehören. Wir wollen nun

$$\begin{array}{r}{N}_j:=\sum _{i=1}^P{N}_{i,j}=|X_j|.\end{array}$$

bestimmen, also die Größe des Teilproblems $j$.

Wir wollen nun die $P$ Maschinen den $k$ Unterproblemen zuteilen und dann $X_j$ auf die zuständigen Maschinen aufteilen. Hierfür brauchen wir mindestens $\lceil |X_j|/S\rceil$ Maschinen. Um etwas "Sicherheitsabstand" zu haben, setzen wir $P_j:=\frac{2|X_j|}{S}$. Jede Maschine kennt die Zahlen $P_j$ und weiß somit, welche Maschinen für Teilproblem $j$ zuständig sind: mit $t_j:=P_1+\cdots +P_{j-1}$ sind das die Maschinen mit Index in

$$\begin{array}{r}{I}_j:=\{t_j+1,t_j+2,\dots ,t_j+P_j\}\end{array}$$

Beachten Sie, dass die Berechnung der Präfixsummen $P_1+\cdots +P_{j-1}$ kein Präfixsummenproblem im MPC-Sinne darstellt, weil es lokal ausgeführt werden kann: jede Maschine kennt alle Zahlen $P_1,\dots ,P_k$. Wir müssen nun alle Items, die zum Teilproblem $j$ gehöhren, auf die Maschinen mit Index in $I_j$ aufteilen. Damit dies in einer Runde gelingt, verwenden wir wiederum Randomisierung: Maschine $i$ schickt jeden ihrer Items $⟨x,j⟩$ an eine Maschine $i^{\prime }$, wobei sie $i^{\prime }$ zufällig aus $I_j$ wählt.

Wieviele Items empfängt eine Maschine $i^{\prime }$ in dieser Runde? Die Maschinen in Menge $I_j$ empfangen insgesamt $|X_j|$ Items; da die Items zufällig veretilt werden, erhält Maschine $i^{\prime }$ im Erwartungswert $\frac{|X_j|}{P_j}=\frac{S}{2}$ viele Items.

Wenn bisher kein "Unfall" geschehen ist (also keines der schlimmen Ereignisse von kleiner Wahrscheinlichkeit eingetreten ist), dann hält nun jede Maschine eine Menge von Items, die alle zu einem Teilproblem gehören, und jede Maschine weiß auch, an welchem Teilproblem sie arbeiten soll und welche anderen mit ihr. Wir können nun also rekursiv auf jedem Teilproblem weiterarbeiten.

Laufzeitanalyse

Die gerade beschriebene Phase von MPC-Quicksort benötigt $O(\lambda )$ Runden. Es bleibt zu untersuchen, wie viele Phasen der rekursive Aufruf erzeugt. Hierzu untersuchen wir, wie groß die Teilprobleme werden. Da wir $X$ in $k+1$ Teilprobleme $X_0,\dots ,X_k$ unterteilen (mit $k=|Y|$ die Anzahl der Pivots), sollte jedes Teilproblem "im Durchschnitt" $\frac{N}{k+1}$ Elemente enthalten. Die Anzahl $k$ der Pivots ist wiederum im Erwartungswert $\tilde{k}:=\frac{\sqrt{S}}{2}$, so dass wir $\frac{N}{k+1}$ wohl bei ungefährt $\frac{2N}{\sqrt{S}}=2N^{1-ϵ/2}$ erwarten.

Wir "erwarten" also, dass die Größe eines Teilproblems bei ungefähr $2N^{1-ϵ/2}$ liegt. Nach dieser Rechnung würde in jedem rekursiven Level die Anzahl $N$ der Elemente ungefähr durch $\tilde{k}=\frac{\sqrt{S}}{2}$ geteilt. Nach $\frac{\log N}{\log \tilde{k}}=O(1/ϵ)$ Rekursionsleveln wären wir fertig; sogar noch etwas früher: sobald ein Teilproblem kleiner als $N^{ϵ}$ ist, können wir es auf einer Maschine sortieren.

Wahrscheinlichkeitsrechnung: Beweise der Behauptungen

Schneller sortieren in $O(\lambda )$ Runden

Ich beschreibe nun einen schnelleren Sortieralgorithmus, der auch auf Quicksort beruht. Er stammt aus dem Paper Sorting, Searching, and Simulation in the MapReduce Framework von Michael T. Goodrich, Nodari Sitchinava und Qin Zhang.