Pytania otagowane jako dc.distributed-comp

Pytania teoretyczne w obliczeniach rozproszonych

4
Dlaczego nie udało nam się opracować jednolitej teorii złożoności obliczeń rozproszonych?
Dziedzina przetwarzania rozproszonego okazała się bardzo krótka w opracowaniu jednej teorii matematycznej opisującej algorytmy rozproszone. Istnieje kilka „modeli” i struktur obliczeń rozproszonych, które po prostu nie są ze sobą kompatybilne. Sama eksplozja różnych właściwości czasowych (asynchronia, synchronizacja, synchronizacja częściowa), różne prymitywy komunikacyjne (przekazywanie wiadomości w stosunku do pamięci współużytkowanej, transmisja …
10
Aktualne modele równoległe do obliczeń
Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90. Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń równoległych? Czy ogólne modele są …
4
Dlaczego problem konsensusu jest tak ważny w obliczeniach rozproszonych?
W obliczeniach rozproszonych problem konsensusu wydaje się być jednym z głównych tematów, który przyciągnął intensywne badania. W szczególności artykuł „Niemożność rozproszonego konsensusu z jednym wadliwym procesem” otrzymał nagrodę PODC Influential Paper Award 2001 . Dlaczego więc problem konsensusu jest tak ważny? Co możemy osiągnąć dzięki konsensusowi zarówno w teorii, jak …
4
Nieskończenie duże, ale lokalnie skończone problemy obliczeniowe
To pytanie jest inspirowane komentarzem Jukki Suomeli do innego pytania . Jakie są przykłady nieskończenie dużych, ale lokalnie skończonych problemów obliczeniowych (i algorytmów)? Innymi słowy, jakie są przykłady obliczeń, które zatrzymują się w skończonym czasie, w których każda Maszyna Turinga odczytuje i przetwarza tylko dane skończone, ale w sumie obliczenia …
1
Dowody poprawności klasycznych Paxos i Fast Paxos
Czytam artykuł „Fast Paxos” autorstwa Leslie Lamport i utknąłem z dowodami poprawności zarówno klasycznych Paxos, jak i Fast Paxos. Aby zachować spójność, wartość wybrana przez koordynatora w fazie 2 a w rundzie i powinna spełniaćvvv2 a2a2ajaii Dla dowolnej rundy j < i żadna wartość inna niż v nie była lub …
1
Czy istnieje lista problemów kanonicznych w systemach rozproszonych?
W ubiegłym tygodniu ponownie przeczytałem transkrypt Leslie Lamport z 1982 r. Z konferencji, którą wygłosił na temat Rozwiązanych problemów, Nierozwiązanych problemów i nieproblemów w współbieżności . Artykuł jest czytelny, ale jedną z rzeczy, które skłoniły mnie do myślenia, jest następujące stwierdzenie: Czy każdy problem można uznać za problem wzajemnego wykluczenia …
2
Zdecentralizowany algorytm do określania wpływowych węzłów w sieciach społecznościowych
W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm empty~set} wybierz węzeł o najwyższym indywidualnym wpływie, nazwij go ; S = S ∪ v 1v1v1v_1S=S∪v1S=S∪v1S …
5
Awarie procesora w przetwarzaniu rozproszonym, które nie są awariami ani bizantyjskie
Istnieją dwa główne typy awarii procesorów w modelach przetwarzania rozproszonego: (1) Awarie awarii: procesor zatrzymuje się i nigdy nie uruchamia się ponownie. (2) Awarie bizantyjskie: procesory zachowują się przeciwnie, złośliwie. Moje pytanie brzmi: Jakie inne rodzaje awarii procesorów, które zostały zbadane, które nie ograniczają się do awarii lub awarii bizantyjskich? …
2
złożoność losowych plotek
Problem plotkowania w systemach rozproszonych jest następujący. Mamy wykres GGG z nnn wierzchołkami. Każdy wierzchołek ma komunikat który należy wysłać do wszystkich węzłów.vvvmvmvm_v Moje pytanie dotyczy teraz modelu sieci ad-hoc (zakładamy, że węzeł nie ma żadnej wcześniejszej wiedzy na temat topologii sieci, jej stopni wejściowych i wyjściowych oraz zestawu sąsiadów. …
3
Wydajne porównanie DAG przez sieć
W rozproszonych systemach kontroli wersji (takich jak Mercurial i Git ) istnieje potrzeba skutecznego porównywania ukierunkowanych wykresów acyklicznych (DAG). Jestem programistą Mercurial i bardzo chcielibyśmy usłyszeć o pracy teoretycznej, która omawia złożoność czasową i sieciową porównywania dwóch DAG. Wspomniane DAG są tworzone na podstawie zarejestrowanych zmian. Wersje są jednoznacznie identyfikowane …
1
Jakie są główne problemy badawcze w transakcjach rozproszonych?
Tło: Przetwarzanie transakcji jest tradycyjnym tematem badań w teorii baz danych. Obecnie transakcje rozproszone są popularyzowane przez wielkoskalowe rozproszone systemy pamięci masowej, które zazwyczaj obejmują partycjonowanie danych (zwane także shardingiem) i replikację danych . Jakie są główne problemy badawcze w transakcjach rozproszonych? Czy istnieją dobrze znane teorie i rozwiązania, które …
1
Jaka jest zaleta projektowania deterministycznych algorytmów rozproszonych?
Algorytmy rozproszone odporne na awarie mogą być deterministyczne lub probabilistyczne. Weźmy na przykład problem konsensusu. Paxos jest deterministyczny w tym sensie, że biorąc pod uwagę przyjęte założenie, zawsze działa. Natomiast randomizowany konsensus działa z określonym prawdopodobieństwem. Jaka jest zaleta projektowania i stosowania algorytmu deterministycznego? Założenia, na których opierają się algorytmy …
2
Dlaczego linearyzowalność jest właściwością bezpieczeństwa i dlaczego zestawy właściwości bezpieczeństwa są zamknięte?
W rozdziale 13 „Obiekty atomowe” książki „Algorytmy rozproszone” Nancy Lynch udowodniono, że linearyzowalność (znana również jako atomowość) jest właściwością bezpieczeństwa. To znaczy, że jego odpowiednia właściwość śledzenia jest niepusta, zamknięta z prefiksem i zamknięta z ograniczeniem , jak zdefiniowano w sekcji 8.5.3. Nieformalnie właściwość bezpieczeństwa jest często interpretowana jako powiedzenie, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.