Model Waktu dan Kegagalan

Model waktu dan kegagalan menentukan asumsi algoritma terdistribusi mengenai penundaan pesan dan kecepatan prosesor, serta bagaimana komponen diizinkan untuk mengalami kegagalan.

Definition

Model waktu menetapkan asumsi tentang batas atas waktu pengiriman pesan dan kecepatan proses relatif, sementara model kegagalan menetapkan serangkaian cara di mana proses dan saluran dapat menyimpang dari perilaku yang ditentukan.

Scope

Topik ini mencakup model waktu sinkron, asinkron, dan sinkron parsial; taksonomi kegagalan mulai dari crash (fail-stop) hingga omission dan timing, sampai ke kesalahan arbitrer (Byzantine); serta abstraksi detektor kegagalan yang menjembatani sistem asinkron dan penalaran berbasis batas waktu. Model-model ini adalah aksioma dari mana hasil kemungkinan dan ketidakmungkinan diturunkan.

Core questions

• Batas penundaan dan kecepatan apa yang dapat diasumsikan oleh suatu algoritma, dan bagaimana batas waktu bergantung padanya?
• Kelas kegagalan mana—crash, omission, timing, Byzantine—yang harus ditutupi oleh protokol?
• Bagaimana sistem asinkron dapat dilengkapi dengan detektor kegagalan untuk mengatasi hasil ketidakmungkinan?

Key theories

Sinkronisasi parsial

Sistem nyata tidak sepenuhnya sinkron maupun sepenuhnya asinkron; model sinkron parsial mengasumsikan batas penundaan dan kecepatan yang berlaku pada akhirnya atau tidak diketahui, yang cukup untuk menyelesaikan konsensus sambil tetap realistis.

Hierarki model kegagalan

Kegagalan berkisar dari crash fail-stop yang jinak, melalui omission pengiriman/penerimaan dan pelanggaran waktu, hingga perilaku Byzantine yang arbitrer; tingkat keparahan kegagalan yang harus ditoleransi oleh protokol menentukan faktor replikasi dan kompleksitas pesan yang diperlukan.

Detektor kegagalan yang tidak dapat diandalkan

Detektor kegagalan abstrak memberikan petunjuk yang mungkin salah tentang proses mana yang telah crash; mengkarakterisasi detektor terlemah yang cukup untuk menyelesaikan konsensus menyelaraskan ketelitian asinkron dengan implementasi berbasis batas waktu yang praktis.

Clinical relevance

Sistem produksi secara implisit memilih model waktu dan kegagalan setiap kali mereka menetapkan batas waktu, memilih faktor replikasi, atau memutuskan apakah akan bertahan dari partisipan yang berbahaya; kesalahan dalam asumsi ini adalah akar penyebab umum insiden split-brain dan kehilangan data.

History

Setelah model asinkron terbukti terlalu lemah untuk konsensus yang toleran terhadap kesalahan, Dwork, Lynch, dan Stockmeyer memperkenalkan sinkronisasi parsial pada tahun 1988, dan Chandra serta Toueg memformalkan detektor kegagalan yang tidak dapat diandalkan pada tahun 1996, yang bersama-sama menyediakan alat pemodelan yang memungkinkan kesepakatan toleran terhadap kesalahan yang praktis.

Debates

Apakah batas waktu merupakan asumsi waktu atau detektor kegagalan?

Satu pandangan memperlakukan batas waktu sebagai pengkodean batas sinkronisasi (akhir); pandangan lain memperlakukannya sebagai implementasi detektor kegagalan abstrak. Kedua kerangka ini sebagian besar setara tetapi menekankan batas desain yang berbeda antara model jaringan dan algoritma.

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

Mengapa deteksi kegagalan yang andal tidak dapat diimplementasikan dalam sistem yang murni asinkron?

Tanpa batas penundaan pesan, proses yang lambat tetapi hidup tidak dapat dibedakan dari proses yang crash, sehingga detektor apa pun harus kadang-kadang salah. Inilah sebabnya mengapa sistem asinkron dilengkapi dengan asumsi waktu atau detektor yang tidak dapat diandalkan.