Quelques questions de complexité liées au calcul distribué (Rapport préliminaire)

Soit M = 0, 1, 2, . . . , m—1, N = 0, 1, 2, . . . , n—1, et f : M × N → 0, 1 une fonction à valeurs booléennes. Nous nous intéresserons au problème suivant et aux questions qui y sont liées. Soit i ε M, j ε N des entiers connus seulement de deux personnes, P1 et P2, respectivement. Pour que P1 et P2 déterminent coopérativement la valeur f(i, j), ils échangent des informations l'un à l'autre alternativement, un bit à la fois, selon un certain algorithme. La quantité d'intérêt, qui mesure l'échange d'informations nécessaire pour calculer f, est le nombre minimum de bits échangés dans n'importe quel algorithme. Par exemple, si f(i, j) = (i + j) mod 2, alors 1 bit d'information (indiquant si i est impair) envoyé de P1 à P2 permettra à P2 de déterminer f(i, j), et c'est clairement le meilleur résultat possible.