Kegagalan prosesor dalam komputasi terdistribusi yang tidak crash atau Bizantium

13

Ada dua jenis utama kegagalan prosesor dalam model komputasi terdistribusi:

(1) Kegagalan kerusakan: prosesor berhenti, dan tidak pernah memulai lagi. (2) Kegagalan Bizantium: prosesor berperilaku berlawanan, jahat.

Pertanyaanku adalah:

Apa saja jenis kegagalan prosesor yang telah dipelajari, yang tidak berkurang menjadi rusak atau kegagalan Bizantium?

Juga, pertanyaan yang lebih spesifik:

Apakah model telah dipelajari di mana, dengan beberapa kemungkinan, suatu proses aktif pada langkah waktu , dan jika tidak aktif? Jadi setiap proses berkedip-kedip, seolah-olah. $t$

Saya paling tertarik dengan bagaimana kegagalan ini terkait dengan konsensus dan masalah perjanjian terdistribusi lainnya.

Terima kasih.

reference-request dc.distributed-comp Aaron Sterling
sumber

@ Harun: Saya punya kursus tentang "sistem terdistribusi" dan satu lagi tentang "sistem toleransi kesalahan" beberapa tahun yang lalu, tapi saya tidak benar-benar ke dalam topik-topik itu. Namun saya pikir model kesalahan dinamis kata kunci dapat membantu Anda.

MS Dousti

1

Saya kira model kegagalan yang digunakan di bidang stabilisasi diri tidak mengurangi kegagalan crash atau kegagalan Bizantium. Satu cara untuk mengaitkannya dengan kegagalan Bizantium: Anda dapat memiliki perilaku Bizantium sementara , tetapi jika dan ketika perilaku tersebut berhenti, sistem yang dapat menstabilkan diri harus mencapai kondisi yang benar.

Jukka Suomela

1

Mengenai pertanyaan Anda yang lebih spesifik: Jika sebuah prosesor jika "on" dengan probabilitas

, menurut saya sangat mirip dengan model asinkron di mana prosesor selalu aktif tetapi pesan mengambil, katakanlah, putaran

dengan harapan untuk mencapai tujuan mereka. Bisakah Anda menjelaskan bagaimana ini berbeda dari model yang ada dalam pikiran Anda?

p

$p$

1 / p

$1/p$

Jukka Suomela

1

@ Harun: Saya tidak benar-benar tahu berapa banyak model semacam ini telah dipelajari. Tapi saya kira jika Anda memiliki algoritma sinkron deterministik

dengan waktu berjalan

, Anda bisa menggunakan

-synchroniser untuk mensimulasikan

dalam model asinkron, dan saya kira waktu berjalan yang diharapkan akan menjadi sesuatu seperti

. (

-synchroniser hanya menjamin bahwa tetangga Anda tidak pernah lebih dari 1 kali melangkah maju atau di belakang Anda dalam simulasi

)

A

$A$

T

$T$

α

$\alpha$

A

$A$

T / p

$T/p$

α

$\alpha$

A

$A$

Jukka Suomela

2

@ Harun: Saya telah mengambil teori komputasi terdistribusi dengan Michel Raynal dan dia menggambarkan model ketiga, di mana pesan dapat dihapus secara acak. Dalam model itu sebuah pesan dapat gagal dikirim secara diam-diam, tetapi itu tidak selalu berarti bahwa simpul tersebut gagal. Ini adalah tentang kegagalan tautan dan bukan kegagalan simpul "model saluran lossy yang adil", Anda dapat membaca lebih lanjut tentang hal ini di sini: Siaran Seragam yang Dapat Dipercaya sebagai Survei Pengantar untuk Kegagalan Detektor Oracles - Michel Raynal ( ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz )

M. Alaggan

12

Disalin dari komentar pada pertanyaan sesuai permintaan.

Saya telah mengambil teori komputasi terdistribusi dengan Michel Raynal dan dia menggambarkan model ketiga, di mana pesan dapat dijatuhkan secara acak. Dalam model itu sebuah pesan dapat gagal dikirim secara diam-diam, tetapi itu tidak selalu berarti bahwa simpul tersebut gagal. Ini adalah tentang kegagalan tautan dan bukan kegagalan simpul "model saluran lossy yang adil", Anda dapat membaca lebih lanjut tentang hal ini di sini: Siaran Seragam yang Dapat Dipercaya sebagai Survei Pengantar untuk Kegagalan Detektor Oracle - Michel Raynal (ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz)

M. Alaggan
sumber

10

Karena tingginya biaya sumber daya yang terlibat dengan toleransi kesalahan Bizantium, model kegagalan dengan asumsi yang semakin kuat tentu saja telah dianalisis, terutama tergantung pada persyaratan sumber daya untuk mentoleransi kesalahan jenis terbatas. ( Azadmanesh dan Kieckhafer, 2002 ) memberikan taksonomi yang sangat bagus (lihat Gambar 1.)

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

Cara lain untuk memodelkan asumsi mode kegagalan adalah menjauh dari sudut pandang node-centric, di mana kehilangan pesan dimodelkan sebagai kesalahan pengirim, menuju model kesalahan-tautan, yang hanya merupakan tampilan ganda, setelah inkonsistensi yang dapat mereka sebabkan dalam sistem dipertimbangkan. Model ini telah diselidiki oleh ( Schmid, Weiss, dan Rushby, 2002 ), menghindari hasil ketidakmungkinan ( Gray, 1978 ) yang menunjukkan solusi deterministik dari masalah Serangan Terkoordinasi di bawah kesalahan tautan.

Martin Schwarz
sumber

8

Saya tidak tahu apakah @M. Alaggan berbicara tentang kesalahan semacam ini, tetapi mereka jelas terlihat sama: kesalahan sementara.

Dalam model DVFS , di mana seseorang dapat memodifikasi frekuensi dan tegangan untuk mengurangi konsumsi energi, Zhu dan Aydin dalam makalah ini (pdf) menggunakan model kesalahan untuk DVFS. Mereka menganggap kegagalan sementara, yang merupakan kesalahan yang disebabkan oleh kesalahan perangkat lunak misalnya. Mereka hanya membatalkan eksekusi tugas saat ini dan prosesor yang mengalami kegagalan akan dapat memulihkan dan menjalankan tugas selanjutnya yang diberikan kepadanya (jika ada).

$\lambda$

λ (f) = λ_{p} e^{d \frac{f_{m Sebuah x} - f}{f_{m Sebuah x} - f_{m saya 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)}.$

Maaf memposting ini begitu lama setelah posting asli, tetapi saya menemukan pertanyaan ini karena saya sedang mengerjakan subjek ini :). Ketika tidak mempelajari DVFS, kesalahan-kesalahan ini masih ada, formula mungkin masih valid (atau dapat diadaptasi). Anda dapat menemukan informasi lebih lanjut tentang kegagalan sementara tanpa DVFS di sini .

Gopi
sumber

4

Mengenai model kegagalan kelalaian yang disebutkan telah melihat NeigerToueg , yang mempertimbangkan berbagai jenis itu.

Apakah model telah dipelajari di mana, dengan beberapa kemungkinan, suatu proses aktif pada t langkah waktu, dan jika tidak aktif? Jadi setiap proses berkedip-kedip, seolah-olah.

Ini terdengar seperti model crash-recovery. Saya tidak mengetahui model mana pun yang prosesnya hidup / mati secara probabilistik. Ada juga varian di mana proses adalah Bizantium untuk beberapa waktu dan kemudian pulih, di mana seiring waktu semua proses dapat menjadi Bizantium (meskipun sebagian besar dipertimbangkan untuk sinkronisasi jam).

Perhatikan bahwa jika dengan tidak aktif Anda hanya berarti bahwa suatu proses hanya tidak membuat kemajuan (tidak kehilangan keadaannya, dan tidak ada pesan yang hilang karena penerima "tidak aktif") maka apa yang Anda lihat disebut sebagai tidak sinkron. sistem. Dalam konteks memori bersama, pertanyaan Anda kemudian bisa terkait erat dengan makalah Aspnes ini .

Martin B.
sumber

1

Mungkin ada jenis kegagalan lainnya. Misalnya, beberapa prosesor (mis. Siaran atau protokol multicast) mungkin menjadi kelebihan beban dan tidak dapat memproses semua pesan yang masuk. Ini menghasilkan prosesor tampak offline ke beberapa prosesor dalam sistem terdistribusi.

Mohammad Al-Turkistany
sumber

Kegagalan prosesor dalam komputasi terdistribusi yang tidak crash atau Bizantium

Jawaban: