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.