Szacowanie percentylu między rozproszonymi węzłami bez ujawniania wartości

Mam dość unikalny problem do rozwiązania i mam nadzieję, że ktoś tutaj da mi wgląd w to, jak najlepiej go rozwiązać.

Problem: Załóżmy, że lista N liczb jest dzielona między zestawem uczestników w taki sposób, że żaden pojedynczy uczestnik nie zna żadnej z dzielonych przez siebie liczb. Wszyscy uczestnicy znają N (wielkość listy liczb) i sumę wszystkich liczb na liście, ale nic więcej a priori.

Współpracując, można porównać dwie wspólne liczby aib w taki sposób, aby uczestnicy dowiedzieli się, czy stwierdzenie „a <b” jest prawdziwe, ale nic więcej. Jest to jednak bardzo kosztowna rzecz (przeczytaj: wykonanie pojedynczego porównania może zająć wiele sekund, a może nawet minut). Zobacz koniec tego postu, aby uzyskać więcej informacji na temat tego, jak to możliwe.

Na koniec dnia strony chcą przedstawić dane wyjściowe, które indeksy na liście odpowiadają „najwyższym K procentom” (największy procent K) na wspólnej liczbie na liście. Można to oczywiście zrobić przez sortowanie lub użycie algorytmu wyboru „najwyższego K”. Jednak zwykle używają okropnych porównań, których należy unikać. (Są to O (n log n) lub O (n), z dość dużymi ukrytymi stałymi.)

Inną alternatywą jest „odgadnięcie” liczby X, dla której (1-K)% jest mniejsze niż X, a K% jest większe. Następnie możesz porównać każdy element z X i zobaczyć, ile jest większych, a ile mniejszych. Jeśli twoje domysły były błędne, popraw je, używając czegoś w rodzaju wyszukiwania binarnego, dopóki nie zbiegniesz na właściwym rozwiązaniu. To wymaga znacznie mniej porównań, jeśli twoje przypuszczenia są dobre.

Moje pytanie brzmi:

Biorąc pod uwagę tylko N i sumę, jaki jest najlepszy sposób na „przewidzenie” X?

Oczywiście będzie to zależeć od podstawowej dystrybucji. W przypadku różnych przypadków użycia podstawowa dystrybucja będzie prawdopodobnie inna, ale będzie znana, dlatego interesują mnie dobre rozwiązania dla wszystkich popularnych (normalne, jednolite, wykładnicze, może kilka innych). Bardzo chciałbym usłyszeć sugestie dotyczące najlepszego wyszukiwania typu „binarnego”, aby zminimalizować liczbę kroków przy założeniu, że rozkład leży u podstaw.

$f_i$$f_i$$f_i(j)$$1\leq i\leq N$. Biorąc pod uwagę ten udział, uczestnik nie ma informacji (w sensie teoretycznym) na temat liczby; w rzeczywistości żaden odpowiedni podzbiór uczestników nie może połączyć wiedzy, aby uzyskać informacje na temat wspólnych numerów. Jednak stosując wyrafinowaną bezpieczną technikę obliczeń wielostronnych, można ustalić, czy jedna wspólna wartość jest mniejsza niż inna, bez ujawniania jakichkolwiek informacji. Ta technika wymaga współpracy wszystkich uczestników, dlatego jest tak kosztowna i powinna być wykonywana jak najmniej razy.

Wydaje się, że zadajesz dwa powiązane pytania:

1. „Które indeksy na liście odpowiadają górze”
2. „Oszacowanie percentyla”, „liczba X, dla której… K% jest większe”

Mogą one wymagać bardzo różnej liczby porównań parami.

Innym aspektem, który może mieć znaczący wpływ, są informacje, które są udostępniane. Wszyscy znają liczbę, którą otrzymał, znają sumę i wyniki porównań, w których brali udział. Tak / nie. Mówisz jednak również, że „strony chcą podać, które wskaźniki na liście odpowiadają górnej”, dlatego sugerujesz że niektóre informacje o indeksach zostaną udostępnione. W zależności od tego, co dokładnie jest udostępniane, możesz ponownie uzyskać bardzo różne rozwiązania.