Toleransi Kesalahan Bizantium

Toleransi kesalahan Bizantium adalah studi tentang mencapai kesepakatan ketika beberapa proses mungkin gagal secara arbitrer, termasuk dengan mengirimkan pesan yang bertentangan atau berbahaya.

Definition

Kesalahan Bizantium adalah penyimpangan arbitrer dari spesifikasi komponen, termasuk perilaku berbahaya; toleransi kesalahan Bizantium adalah kemampuan protokol terdistribusi untuk memenuhi kondisi kebenarannya meskipun ada sejumlah peserta yang salah (faulty participants) yang terbatas.

Scope

Topik ini mencakup masalah jenderal Bizantium dan batas ketahanan ketat yang ditetapkannya (setidaknya 3f+1 proses, atau pesan yang ditandatangani, untuk menoleransi f kesalahan arbitrer), algoritma kesepakatan pesan lisan dan pesan yang ditandatangani secara sinkron, serta protokol toleransi kesalahan Bizantium asinkron praktis seperti PBFT dan turunannya. Ini mendasari model kepercayaan pada blockchain berizin dan layanan tereplikasi berintegritas tinggi.

Core questions

• Berapa banyak proses yang benar yang dibutuhkan untuk menoleransi sejumlah kesalahan arbitrer tertentu?
• Bagaimana tanda tangan digital mengubah batas ketahanan untuk kesepakatan Bizantium?
• Bagaimana kesepakatan Bizantium dapat dibuat cukup efisien untuk sistem asinkron praktis?

Key theories

Batas jenderal Bizantium

Dengan pesan yang tidak terautentikasi (lisan), kesepakatan Bizantium dapat diselesaikan jika dan hanya jika lebih dari dua pertiga proses benar (n > 3f); pesan terautentikasi dengan tanda tangan yang tidak dapat dipalsukan melonggarkan persyaratan ini.

Replikasi BFT praktis

PBFT menunjukkan bahwa kesepakatan Bizantium dapat berjalan dalam sistem parsial sinkron dengan replikasi mesin-status menggunakan primer dan protokol tiga fase, mencapai kinerja praktis sambil menoleransi hingga sepertiga replika yang salah.

Algoritma kesepakatan sinkron

Dalam model sinkron, algoritma pesan lisan dan pesan bertanda tangan rekursif mencapai kesepakatan dalam f+1 putaran, menggambarkan biaya kompleksitas putaran untuk menoleransi kesalahan arbitrer.

Clinical relevance

Toleransi kesalahan Bizantium adalah fondasi sistem yang harus tahan tidak hanya terhadap kerusakan tetapi juga kompromi atau perilaku berbahaya, termasuk blockchain berizin, layanan tereplikasi dengan jaminan tinggi, serta kontrol avionik dan kedirgantaraan di mana kegagalan komponen arbitrer tidak dapat dikesampingkan.

History

Pease, Shostak, dan Lamport menetapkan batas kesepakatan pada tahun 1980 dan mendramatisasinya sebagai masalah jenderal Bizantium pada tahun 1982; selama hampir dua dekade, kesepakatan Bizantium dianggap terlalu mahal untuk praktik hingga PBFT Castro dan Liskov pada tahun 1999 menunjukkan replikasi Bizantium asinkron yang efisien, menghidupkan kembali bidang ini dan kemudian menginformasikan konsensus blockchain.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Mengapa menoleransi f kesalahan Bizantium membutuhkan 3f+1 proses?

Proses yang benar harus mencapai keputusan mayoritas bahkan ketika f proses yang salah berbohong dan f lainnya mungkin lambat atau tidak dapat dijangkau; hanya dengan lebih dari tiga kali jumlah proses yang salah, mayoritas yang benar selalu dapat mengalahkan kombinasi peserta yang salah dan tertinggal.