Awarie procesora w przetwarzaniu rozproszonym, które nie są awariami ani bizantyjskie

13

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?

Również bardziej szczegółowe pytanie:

Czy zbadano model, w którym z pewnym prawdopodobieństwem proces jest włączony w kroku czasu , a poza tym wyłączony? Tak więc każdy proces mruga, jakby był. $t$

Najbardziej interesuje mnie to, jak te niepowodzenia odnoszą się do konsensusu i innych problemów związanych z porozumieniem rozproszonym.

Dziękuję Ci.

reference-request dc.distributed-comp Aaron Sterling
źródło

@Aaron: Kilka lat temu miałem kurs na temat „systemów rozproszonych” i drugi na temat „systemów odpornych na uszkodzenia”, ale tak naprawdę nie interesuję się tymi tematami. Myślę jednak, że słowo kluczowe dynamiczny model błędu może ci pomóc.

MS Dousti,

1

Wydaje mi się, że model awarii stosowany w obszarze samostabilizacji nie ogranicza się do awarii awaryjnych lub awarii bizantyjskich. Jednym ze sposobów powiązania tego z awariami bizantyjskimi: możesz mieć tymczasowe zachowanie bizantyjskie, ale jeśli i kiedy takie zachowanie ustanie, system samostabilizujący musi osiągnąć prawidłowy stan.

Jukka Suomela,

1

Odnośnie twojego bardziej szczegółowego pytania: jeśli procesor jest włączony z prawdopodobieństwem

, brzmi dla mnie bardzo podobnie do modelu asynchronicznego, w którym procesory są zawsze włączone, ale wiadomości przyjmują, powiedzmy,

rundy w oczekiwaniu na dotarcie do miejsca docelowego. Czy mógłbyś wyjaśnić, czym różni się to od modelu, który miałeś na myśli?

p

$p$

1 / p

$1/p$

Jukka Suomela,

1

@Aaron: Naprawdę nie wiem, jak bardzo zbadano tego rodzaju modele. Ale myślę, że jeśli masz jakiś deterministyczny algorytm synchroniczny

z czasem działania

, możesz po prostu użyć synchronizatora

do symulacji

w modelu asynchronicznym, i przypuszczam, że oczekiwany czas działania byłby podobny do

. ( Synchronizator

po prostu gwarantuje, że twoi sąsiedzi nigdy nie są więcej niż 1 krok do przodu lub za tobą w symulacji

)

A

$A$

T

$T$

α

$\alpha$

A

$A$

T / p

$T/p$

α

$\alpha$

A

$A$

Jukka Suomela

2

@Aaron: Wziąłem teorię obliczeń rozproszonych z Michelem Raynalem i opisał trzeci model, w którym wiadomości mogą być upuszczane losowo. W tym modelu komunikat może nie zostać dostarczony w trybie cichym, ale nie musi to oznaczać awarii węzła. Chodzi o awarie łącza, a nie o awarie węzła „uczciwy model stratnego kanału”, możesz przeczytać więcej o tym tutaj: Quiescent Uniform Reliable Broadcast jako ankieta wprowadzająca do wykrywaczy awarii - Michel Raynal ( ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz )

M. Alaggan

12

Skopiowano z komentarzy do pytania jako na żądanie.

Teorię obliczeń rozproszonych przyjąłem z Michelem Raynalem i opisał trzeci model, w którym wiadomości mogą być upuszczane losowo. W tym modelu komunikat może nie zostać dostarczony w trybie cichym, ale nie musi to oznaczać awarii węzła. Chodzi raczej o awarie łącza niż o awarie węzła „model dość stratnego kanału”, możesz przeczytać więcej o tym tutaj: Quiescent Uniform Reliable Broadcast jako ankieta wprowadzająca do wykrywaczy awarii - Michel Raynal (ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz)

M. Alaggan
źródło

10

Ze względu na wysokie koszty zasobów związane z bizantyjską odpornością na uszkodzenia, oczywiście przeanalizowano modele awarii z coraz silniejszymi założeniami, szczególnie w odniesieniu do wymagań dotyczących zasobów, aby tolerować uszkodzenia typu ograniczonego. ( Azadmanesh i Kieckhafer, 2002 ) zapewniają bardzo ładną taksonomię (patrz ryc. 1)

$3f+1$ $f+1$ $2f+1$ $f$

Innym sposobem na modelowanie założeń trybu awarii jest odejście od punktu widzenia zorientowanego na węzeł, w którym utrata wiadomości jest modelowana jako wina nadawcy, w kierunku modelu uszkodzenia łącza, który jest tylko podwójnym widokiem, po niespójnościach, które mogą powodować system jest brany pod uwagę. Model ten został zbadany przez ( Schmid, Weiss i Rushby, 2002 ), omijając wynik niemożliwości ( Grey, 1978 ), pokazując deterministyczne rozwiązanie problemu skoordynowanego ataku w przypadku błędów łącza.

Martin Schwarz
źródło

8

Nie wiem czy @M. Alaggan mówił o tego rodzaju błędach, ale z pewnością wyglądają podobnie: usterki przejściowe.

W modelu DVFS , w którym można zmodyfikować częstotliwość i napięcie w celu zmniejszenia zużycia energii, Zhu i Aydin w tym artykule (pdf) zastosowali model błędu dla DVFS. Rozważają przejściowe awarie, które są na przykład błędami spowodowanymi błędami oprogramowania. Unieważniają one tylko wykonanie bieżącego zadania, a procesor będący przedmiotem tej awarii będzie mógł odzyskać i wykonać kolejne przypisane mu zadanie (jeśli takie istnieje).

$\lambda$

λ (f) = λ_{p} e^{d \frac{f_{m a x} - f}{f_{m a x} - f_{m i n}}},

$\begin{equation} \label{fault} \lambda(f)=\lambda_p \; e^{d\frac{f_{max}-f}{f_{max}-f_{min}}}, \end{equation}$

f_{m i n} \leq f \leq f_{m a x}

$f_{min}\leq f \leq f_{max}$

d \geq 0

$d\geq0$

λ_{p}

$\lambda_p$

f_{m a x}

$f_{max}$

p

$p$

T_{i}

$T_i$

p

$p$

f_{i}

$f_i$

R_{i} (f_{i}) = e^{- λ (f_{i}) \times E x e c u t i o n T i m e (T_{i}, f_{i})} .

$R_i(f_i)=e^{-\lambda(f_i)\times Execution~Time(T_i,f_i)}.$

Przepraszam, że opublikowałem to tak długo po oryginalnym poście, ale znalazłem to pytanie, ponieważ pracowałem nad tym tematem :). Gdy nie badamy DVFS, błędy te nadal istnieją, formuły prawdopodobnie nadal są poprawne (lub można je dostosować). Więcej informacji na temat awarii przejściowych bez DVFS można znaleźć tutaj .

Gopi
źródło

4

Jeśli chodzi o wspomniane już modele niepowodzenia zaniechania, przyjrzeliśmy się NeigerToueg , który rozważa różne ich rodzaje.

Czy zbadano model, w którym z pewnym prawdopodobieństwem proces jest włączony w kroku czasu t, a poza tym wyłączony? Tak więc każdy proces mruga, jakby był.

To brzmi jak model odzyskiwania po awarii. Nie znam żadnego modelu, w którym procesy są probabilistycznie włączane / wyłączane. Istnieją również warianty, w których procesy są bizantyjskie przez pewien czas, a następnie odzyskują, w miarę upływu czasu wszystkie procesy mogą być bizantyjskie (choć w większości brane pod uwagę w przypadku synchronizacji zegara).

Zauważ, że jeśli będąc wyłączonym masz na myśli, że proces nie tylko robi postępy (nie traci swojego stanu, a wiadomości nie są tracone z powodu wyłączenia odbiornika), to to, na co patrzysz, jest określane jako asynchroniczne system. W kontekście pamięci współużytkowanej twoje pytanie może być zatem ściśle powiązane z tym dokumentem Aspnesa .

Martin B.
źródło

1

Mogą istnieć inne rodzaje awarii. Na przykład niektóre procesory (np. W ramach protokołów rozgłoszeniowych lub multiemisji) mogą zostać przeciążone i nie będą mogły przetworzyć wszystkich przychodzących wiadomości. Powoduje to, że procesor pojawia się offline dla niektórych procesorów w systemie rozproszonym.

Mohammad Al-Turkistany
źródło

Awarie procesora w przetwarzaniu rozproszonym, które nie są awariami ani bizantyjskie

Odpowiedzi: