Aktualne badania i problemy

Tutaj jest próbka moich aktualnych problemów badawczych:

Wybór lidera (Leader Election)

Wiekszość znanych algorytmów wyboru lidera zakłada, że węzły mają unikalne identyfikatory. Celem prowadzonych badań jest zastąpienie tego założenia odpowiednim losowym generowaniem identyfikatorów. Oto jeden z wyników związanych z tymi badaniami (prowadzę je wspólnie z mgr Dominikiem Bojko):

Twierdzenie. Niech $X_1,\ldots,X_n$ ($n\geq 2$) będą niezależnymi zmiennymi losowymi o rozkładzie jednostajnym ze zbioru $\{1,\ldots,L\}$. Niech $M = \max\{X_i:i=1,\ldots,L\}$ oraz niech $S = |\{X_i: X_i = M\}|$. Wtedy $$ \Pr[S=1] = \frac{n}{L^n} \sum_{k=1}^{L-1} k^{n-1} \approx 1 - \frac{n}{2L}~. $$

Własności miary Lebesgue'a (properties of Lebesgueq measure)

Czy teoria mnogości ZFC+ ($\mathrm{add}(\mathcal{L}) = \omega_2$) + ($\mathrm{cof}(\mathcal{L}) = \omega_3$) + ($2^{\omega} = \omega_4$) jest niesprzeczna?

Uwaga: Zdaje się, że problem został rozwiązany pozytywnie przez matematyków z Austrii - ale ciągle sprawdzam jego poprawność (dowód jest dosyć żmudny) [grudzień 2017].

Protokół Chord (Chord P2P Protocol)

W trakcie badanie pewnych wariantów P2P protokołu Chord pojawiła się następująca rekurencja:
$$ m_0 = 1; \quad m_{n+1} = \frac{1}{2^{n+1}} \sum_{k=0}^{n} \binom{n}{k} \min\{m_k,m_{n-k}\}~. $$
Do tej pory nie znam asymptotyki tego ciągu. Podejrzewam, że
$$ m_{n} = \frac{a}{n} + \frac{b}{n^{3/2}} + O(\frac{1}{n^{2}}) $$ dla pewnych stałych $a\approx 0.28$ oraz $b\approx 0.32$. Rafał Kapelko pokazał, że $m_n = \Theta(\frac{1}{n})$.

Średnie w sieciach rozproszonych (Agregates in distributed networks)

Mamy danych spójny graf $(V,E)$. Mamy daną funkcję $X:V\to \mathbb{R}$. Cel: opracowanie rozproszonego protokołu, który służy do wyznaczenia wartości $\sum\{X(v): v\in V\}/|V|$. Wartość ta powinna być znana każdemu wierzchołkowi $v\in V$. Znane protokoły polegają na lokalnym uśrednianiu obserwowanych wartości (coś w stylu: zastąp $X_v$ przez średnią wartość $\sum\{X_u: (v,u)\in E\}$). Niektóre ze nich mają udowodnioną poprawność i zbadane jest tempo zbieżności (niektóre dowody są bardzo ładne i polegają na badaniu wartości własnych macierzy związanych z nimi). Zachowują się one dobrze dla grafów zbliżonych do grafu pełnego. Niestety, ich tempo zbieżności dla grafów zbliżonych do liniowych jest bardzo duże, co uniemożliwia stosowanie ich w praktyce.

Ostatnio badam alternatywne rozwiązanie tego zagadnienia: polega ono na zbudowaniu przybliżonego histogramu funkcji $X$; przybliżenie zaś polega na zastosowaniu liczników probabilistycznych opartych na zmiennych o rozkładzie wykładniczym. Aktualnie otrzymane wyniki pokazują, że algorytm działać będzie w czesie O(D), gdzie $D$ jest średnicą grafu oraz, że osiągnąć można dowolnie dużą precyzję (kosztem złożoności komunikacyjnej). Badania te prowadzę wspólnie z mgr Karolem Gotrydem.