\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \)

Unser Rechnermodell besteht aus $P$ Maschinen, von denen jede einen lokalen Speicher hat, der $S$ Items halten kann. Ein Item besteht üblicherweise aus einem oder einer konstanten Zahl von Maschinenwörtern. Der Input besteht aus $N$ Items, die auf beliebige Weise auf die Maschinen verteilt sind, aber so, dass jede Maschine nicht mehr als $S$ Items hält. Es gilt also $N \leq P \cdot S$. Wir gehen meistens davon aus, dass $P \cdot S \geq c N$ sind für eine konstante $c$, zum Beispiel $c=2$, einfach, um etwas Spielraum zu haben und Items auch mal doppelt speichern zu können.

Definition(Runde in einem MPC-Algorithmus). In jeder Runde führt jede Maschine eine lokale Berechnung ihrer Menge von Items durch; deren Ergebnis ist wiederum eine Menge von Items, die sie dann an eine oder mehrere Maschinen schicken wird. Dabei muss jedoch gelten, dass keine Maschine mehr als $S$ Items verschickt oder mehr als $S$ Items empfängt. Formal:

  1. In Runde $r$ hält Maschine $i$ eine Menge $X_{i,r}$ an Items. Es gilt $|X_{i,r}| \leq S$.
  2. Sie führt nun eine lokale Berechnung durch und erhält dadurch eine neue Menge: $Y_{i,r} := f(X_{i,r})$; ein Element in $Y_{i,r}$ ist von der Form $(j,y)$, wobei $j$ der Index der Maschine ist, an den dies geschickt werden soll. Sei also $Y_{i,r,j} := \{y \ | \ (j,y) \in Y_{i,r}\}$ die Menge der Items, die Maschine $i$ am Ende von Runde $r$ an Maschine $j$ schicken will.
  3. Maschine $i$ schickt $Y_{i,r,j}$ an Maschine $j$.
  4. Maschine $j$ empfängt die Items von mehreren Maschinen und setzt \begin{align*} X_{j, r+1} := \bigcup_{i} Y_{i,r,j} \ . \end{align*} Wobei wir sicherstellen müssen, dass $\sum_{i} |Y_{i,r,j}| \leq S$ gilt.

Die Funktion $f$ darf vom Index $i$ der Maschine und der Runde $r$ abhängen; ganz pedantisch würden wir also $f(i,r, X_{i,r})$ schreiben.

Dies ist eine Runde eines MPC-Protokolls. Insbesondere tun wir so, als könnte die lokale Berechnung $f$ in $O(1)$ Zeit ausgeführt werden. Das ist natürlich nicht immer realistisch, trägt aber der empirischen Tatsache Rechnung, dass die Gesamtkomplexität von den I/O-Operationen, also der Kommunikation über das Netzwerk, und nicht von den eigentlichen Rechenoperationen dominiert wird. In den MPC-Algorithmen, die wir vorstellen werden, sind die lokalen Rechenoperationen $f$ in der Tat immer sehr einfache Operationen (die immer in polynomieller und meist auch linearer Zeit oder $O(n \log n)$ ausgeführt werden können).

Typische Parameter für $S$ und $P$

Interessant wird das MPC-Modell, wenn $S$ so groß ist, dass jede Maschine einen signifikanten Teil der Berechnung lokal erledigen kann, aber noch nicht so groß, dass sie alles erledigen könnte. Zum Beispiel wenn $S = N^{\epsilon}$ gilt für $0 \lt \epsilon \lt 1$, wobei $\epsilon$ aber eher nahe bei $0$ ist als bei $1$. Ein wichtiger Parameter in diesem Setting ist

\begin{align*} \lambda := \frac{\log N}{\log S} = \frac{1}{\epsilon} \ . \end{align*}

Laufzeit

Im Zusammenhang von MPC-Algorithmen interessieren wir uns vorerst hauptsächlich für die Anzahl der Runden. Unser Ziel ist es, Algorithmen von konstanter Rundenkomplexität zu entwerfen - die Anzahl der Runden soll also nicht von der Inputgröße $N$ abhängen. Sie kann und wird jedoch von dem Parameter $\epsilon$ abhängen. Eine typische gute Laufzeit wird $O(\lambda) = O(\frac{1}{\epsilon})$ sein.

Literatur