Complexité de communication randomisée de l'indexation

Question

La fonction dollars est défini comme

$$ mathrm {index} (x, i) = x_i, $$où $ x = x_1 points x_n $. Je recherche la complexité de communication randomisée de $ mathrm {index} $ pour un nombre arbitraire de tours.

D'une manière ou d'une autre, je ne parviens pas à le trouver dans la littérature.

La complexité de communication déterministe est connue pour être $ Theta ( log n) $, alors que sa complexité de communication randomisée unidirectionnelle est $ Theta (n) $.

Je suppose que la complexité de communication randomisée est toujours $ Theta ( log n) $, Je n'ai pas pu trouver une limite inférieure.

Depuis cette fonction, elle est bien étudiée, elle doit être indiquée quelque part.

Merci de votre aide.