Biorąc pod uwagę zestaw niezsynchronizowanych replik M, jak znaleźć podzbiór o danym rozmiarze N, który minimalizuje liczbę retransmisji komunikatów niezbędnych do synchronizacji ich stanów komunikatów w niezawodnym środowisku multiemisji (tj. - wszystkie repliki niezawodnie odbierają wszystkie pozostałe wiadomości repliki)?Jak zminimalizować liczbę retransmisji do synchronizacji N replik?
Stany komunikatów replik składają się z komunikatów, które każdy z nich posiada z tych samych źródeł D (D> = M). Dla każdego źródła replika ma wszystkie wiadomości od tego źródła aż do kilku najwyższych porządkowych (tj. - FIFO, bez dziur, począwszy od zera). Tak więc stan wiadomości repliki może być reprezentowany jako wektor liczb porządkowych, z każdym elementem odpowiadającym źródłu. Alternatywnie możesz myśleć o stanie wiadomości repliki jako o punkcie w przestrzeni D-wymiarowej, jeśli chcesz.
Załóżmy, że wszystkie repliki M już wymieniły swoje wektory stanu komunikatów, więc wszystkie z nich mają macierz M rzędów x D kolumn wszystkich ich stanów komunikatów. Tak więc jest to obecnie scentralizowany problem obliczeniowy, biorąc pod uwagę tę macierz.
Metoda brute force dająca optymalną odpowiedź to zbadanie wszystkich (M select N) podzbiorów i wybranie takiego, który wymaga minimalnej liczby retransmisji niezbędnych do synchronizacji tego podzbioru. Problem polega na tym, że to podejście ma co najmniej czynnikową asymptotyczną złożoność w M.
Chciałem sprawdzić, czy ktoś wie, czy może wymyślić optymalny algorytm o znacznie lepszych asymptotycznych granicach?
Początkowo zastanawiałem się nad tym, jak rozwiązać problem teorii grafów, gdy stany komunikatów replik są wierzchołkami na całkowicie połączonym wykresie, gdzie waga krawędziowa była odległością Manhattanu między dwoma wektorami stanu komunikatów punktów końcowych. Następnie coś podobnego MIN łącza aglomeratów materiałem grupowanie hierarchiczne algorytmem Prim następnie Algorytm Kruskala gdzie po zatrzymać rozmiar każdego klastra jest równa lub przekracza N.
które mogą działać w O (M^2) czasu, ale można skonstruować licznik przykłady, w których nie daje natychmiastowej optymalnej odpowiedzi. Na przykład dla D = 1 dla uproszczenia, niech liczby porządkowe replik M = 7 wynoszą {0, 2, 4, 14, 15, 16, 19} i N = 5. Algorytm Kruskala będzie skupiał się {14, 15, 16 , 19} i {0, 2, 4}, a następnie połączyć te dwa klastry w ostatnim kroku. Ale rzeczywistą odpowiedzią, jakiej chcieliśmy, jest synchronizacja replik ze stanami {2, 4, 14, 15, 16} łącznie. Może moglibyśmy zatrzymać się, gdy pierwszy połączony klaster przekroczy N, a następnie spróbować go przyciąć? Ale w tym przykładzie wracamy ponownie do zadawania oryginalnego pytania, ponieważ klaster, na którym zatrzymaliśmy, zawiera wszystkie repliki M! I oczywiście ten problem nie jest tak prosty, gdy D> 1, który zawsze będzie (D> = M).
Innym problemem z powyższym podejściem jest to, że jeśli algorytm zdecyduje się zsynchronizować dwa klastry replik w większym klastrze, to nie tylko wpływa na odległości między innymi klastrami i nowo połączonym klastrem (np. - jak w normalnej aglomeracji hierarchiczne grupowanie), ale także odległości między wszystkimi innymi klastrami, ponieważ wszystkie one słyszą i mogą korzystać z każdej wysłanej retransmisji. Tak więc, wszystkie odległości między wszystkimi klastrami mogą się zmieniać po każdym kroku scalania iw niezbyt prosty sposób, jeśli pozwolisz, aby replika korzystała z otrzymywanych tu wiadomości, nie w FIFO, bez wierceń. Na przykład replika A ma komunikaty od źródła D1 do liczby porządkowej X. Algorytm wybiera synchronizację dwóch klastrów, w tym A, które wymagają retransmisji wiadomości ze źródła D1 od X + 5 do X + 10. Optymalny algorytm zda sobie sprawę z tego, że A potencjalnie korzysta z tych retransmisji, mimo że są poza jego FIFO, brak porządków porządkowych dla źródła D1 z luką komunikatów od X + 1 do X + 4.
Innym sposobem, w jaki myślałem o rozwiązaniu tego problemu, było rozpatrzenie go jako problemu geometrycznego, w którym stany replik M reprezentują punkty w przestrzeni D-wymiarowej L1. Następnie chcemy znaleźć najmniejszy "objętościowy" wypukły kadłub, który zawiera co najmniej N punktów. To może nie być dobre podejście, ale myślenie o nim w sposób geometryczny w naturalny sposób oddaje ideę, że wszystkie repliki mogą korzystać z dowolnych dwóch zestawów synchronizacji replik. Większość ich odległości zostanie zredukowana do powierzchni nowego obiektu (nie wierzchołków!) Utworzonych przez scalenie stanów dwóch zestawów.
EDYCJA - Inny sposób, w jaki o tym pomyślałem, pochodzi z przykładu, który podałem. Dla każdego źródła DX znajdź podzbiór N replik, który wymaga minimalnej liczby retransmisji do zsynchronizowania na tym źródle. To dość łatwe. Problem polega na tym, że musisz następnie porównać i zmodyfikować te podzestawy D, aby uzyskać je wszystkie, aby pokryć te same N repliki. Nie jest to w pełni ukształtowany pomysł, ponieważ minimum N w każdym wymiarze DX jest lokalnym minimum w przestrzeni globalnej, które może znajdować się w niewłaściwym obszarze jako globalna optymalna odpowiedź dla tego wymiaru. W każdym razie, jest to inny pomysł do przemyślenia.
EDIT2 - Wracając do algorytmu Prim + Kruskala i ignorując fakt, że każde scalenie aktualizuje względne odległości między wszystkimi klastrami, czy prawdą jest, że gdy odkryjemy pierwszy klaster, którego rozmiar jest równy lub przekracza N, wówczas optymalna odpowiedź musi być jakimś podzbiorem tego klastra? Jeśli rozmiar klastra jest równy N, to jesteśmy skończeni. Jeśli rozmiar klastra przekracza N, to czy moglibyśmy zrobić coś takiego, jak obliczyć środek ciężkości klastra i wybrać N najbliższych replik do środka ciężkości? Czy to przyniesie optymalną odpowiedź? To nadal nie wydaje się właściwe, ponieważ nie uwzględnia "kierunkowości" różnych odległości od środka ciężkości. Oznacza to, że nie rozróżnia on dwóch replik, które są blisko siebie w przestrzeni D-wymiarowej (co powinno faworyzować) w przeciwieństwie do dwóch replik, które znajdują się w "przeciwnych" kierunkach względem siebie w stosunku do środka ciężkości. Może moglibyśmy zamiast tego spojrzeć na minimalne drzewo opinające repliki w klastrze i jakoś przyciąć je, aby znaleźć minimalny podzbiór wagi, który pozostaje połączony?
Wszelkie pomysły lub wskazówki do odpowiednich algorytmów byłyby bardzo mile widziane!
W jaki sposób definiujesz "retransmisję wiadomości" w tym problemie? Co zawiera "wiadomość"? Czy przesyłanie wiadomości do wszystkich replik ma taki sam koszt jak przesyłanie do pojedynczej repliki? Nie rozumiem też, dlaczego {2, 4, 14, 15, 16} jest "faktyczną odpowiedzią" w twoim przykładzie. – mhum
@mhum Retransmisja wiadomości następuje wtedy, gdy wiadomość, znana już jednej lub większej liczbie obecnych replik, jest rozsyłana grupowo przez jednego z nich do całej grupy. Odbywa się to, aby pomóc replikom, które nie znają jeszcze tego komunikatu, aby zbliżyć wszystkie stany komunikatów replik do zsynchronizowania (tj. - równego). Komunikat składa się z kilku bajtów danych. Dla uproszczenia rozważ każdą retransmisję wiadomości jako równie kosztowną jak każda inna. Tak, wszystkie transmisje są rozsyłane grupowo i niezawodnie docierają do wszystkich w grupie. – jschultz410
{2, 4, 14, 15, 16} jest odpowiedzią, ponieważ jest to podzbiór rozmiaru N = 5, który wymaga najmniejszej retransmisji, aby wszystkie ich stany były równe 16. Wiadomości od 3 do 16 musiałyby być retransmitowany, więc 14 wiadomości. Inne prawie optymalne zestawy to {4, 14, 15, 16, 19}, ale wymaga to od 5 do 19 = 15 retransmisji i {0, 2, 4, 14, 15}, które wymagają od 1 do 15 = 15 retransmisji. W jednym wymiarze ten problem jest dość łatwy, ale wyobraź sobie, że gdyby było 7 lub 10 wymiarów, każda replika byłaby w dowolnych pozycjach w obrębie każdego wymiaru. – jschultz410