การทนความผิดพร่องแบบไบแซนไทน์ สำนักงานใหญ่ของจักรวรรดิโรมันตะวันออกโบราณเคยเป็นหนึ่งในเมืองที่มีอิทธิพลและมั่งคั่งที่สุดในโลก อย่างไรก็ตามเนื่องจากดินแดนที่กว้างขวาง บีซันเทียม พบกับการบุกโจมตีจากภายนอกและการกบฏภายในอยู่เสมอ ในการป้องกันพรมแดน บีซันเทียมส่งทหารหลายกอง ที่มีนายพลคนละคนควบคุม การเอื้ออำนวยความเห็นร่วมกันในหมู่นายพลเหล่านี้กลายเป็นท้าทายที่สำคัญ
ปัญหานายพลบีซันไทน์มีความสัมพันธ์ใกล้ชิดกับบล็อกเชน ระบบเครือข่ายบล็อกเชนเป็นระบบเครือข่ายแบบกระจายที่ทุกโหนดเหมือนนายพลบีซันไทน์ต้องบรรลุความเห็นร่วมในการธุรกรรมและข้อมูลในสภาพแวดล้อมของเครือข่ายที่ไม่น่าเชื่อถือ

ปัญหาทหารสองท่าน

ปัญหาสองนายพลเป็นกรณีพิเศษของปัญหานายพลไบแซนไทน์ ปัญหาและข้อพิสูจน์ของการแก้ปัญหาถูกเสนอครั้งแรกโดย E.A. Akkoyunlu, K.Ekanadham และ R.V. Huber ในบทความปี 1975 เรื่อง "ข้อ จํากัด บางประการและการแลกเปลี่ยนในการออกแบบการสื่อสารเครือข่าย" ในปี 1978 จิมเกรย์ตั้งชื่อปัญหานี้อย่างเป็นทางการว่า "ปัญหาสองนายพล" ในหนังสือของเขา "หมายเหตุเกี่ยวกับระบบปฏิบัติการฐานข้อมูล" เดิมทีมันถูกใช้เพื่อวิเคราะห์ปัญหาของการบรรลุฉันทามติผ่านการสื่อสารผ่านลิงค์การสื่อสารที่ไม่น่าเชื่อถือ ปัจจุบันมักใช้เพื่อแสดงให้เห็นถึงความสอดคล้องและปัญหาฉันทามติในระบบกระจาย

คำจำกัดกายของปัญหา:
ทัพของประเทศ A สองกอง ที่มีแม่นางพร้อมที่จะโจมตีทัพของประเทศ B ที่ถูกล้อมล้อมในหุบเขา กองทัพของประเทศ B มีกำแพงล้อมรอบที่หุบเขา กับ ทัพ A สองกอง ที่ตั้งอยู่บนเนินเขาด้านทางทั้งสองข้างของหุบเขา อย่างไรก็ตาม เส้นทางเดียวที่ระหว่างทัพ A สองกองผ่านทางหุบเขา ทัพของประเทศ B มีพลังที่แข็งแกร่งกว่าทัพ A ในแต่ล่ะกอง แต่หากทัพ A โจมตีร่วมกัน ทัพของประเทศ B จะถูกชนะได้
ปัญหา: สามารถสร้างอัลกอริทึมที่อนุญาตให้นายพล 2 ท่านของกองทัพ A เห็นด้วยกันเพื่อโจมตีพร้อมกันหรือไม่ อัลกอริทึมอาจรวมถึงการส่งและรับข้อความ
วิธีแก้ไข: ปัญหาสองนายพลแบบคลาสสิกไม่สามารถแก้ไขได้ ไม่มีโปรโตคอลใดที่สามารถรับประกันได้ว่ากองทัพทั้งสองของ A จะประสานงานการโจมตีได้สําเร็จ อย่างไรก็ตามในระบบการปฏิบัติปัญหาสามารถแก้ไขได้ค่อนข้างน่าเชื่อถือเช่นด้วยกลไก "การจับมือสามทาง" ในโปรโตคอล TCP

การทนความผิดพร่องแบบไบแซนไทน์

ปัญหาจอห์นบุยซันทีนผิดพลาดถูกเสนอครั้งแรกโดยเลสลีแลมพอร์ท ผู้ได้รับรางวัล Turing ปี 2013 ในบทความของเขา “ปัญหาจอห์นบุยซันทีนผิดพลาด” ปัญหาบอกว่าจะทำอย่างไรเพื่อให้ได้ความสอดคล้องในระบบกระจายในกรณีที่มีพฤติกรรมที่ไม่ดี เช่นการแก้ไขข้อความ
กองทัพหลายกองของจักรวรรดิบิซันทีนแวดล้อมเมืองศัตรู ที่นำโดยนายทหารแต่ละคน กองทัพบิซันทีนสามารถสื่อสารกันได้แค่ผ่านข่าวสาร หลังจากสังเกตกำลังกองทัพของศัตรู นายทหารบิซันทีนต้องเดินทางสู่ข้อสรุปเดียวกัน: แต่ถ้ามีกองทัพบิซันทีนมากกว่าครึ่งทัพทั้งหมดๆ โจมตีร่วมกันที่เมืองนั้น พวกเขาจะสามารถจับเมืองและประสบความสำเร็จ

โซลูชัน: หากจำนวนนายพล (โหนด) ในระบบไบแซนไทน์ คือ Z และจำนวนนายพลที่ไม่เชื่อถือได้ (ทรยศ) คือ X จะสามารถรับประกันความสอดคล้องของระบบด้วยโปรโตคอล Byzantine Fault Tolerance (BFT) เท่านั้นเมื่อ Z ≥ 3X + 1
ในระบบทางปฏิบัติ ความล้มเหลวที่ทำให้โหนดไม่สามารถตอบสนองถือเป็น "ข้อผิดพลาดของการล้มเหลว" ในขณะที่โหนดที่ปลอมและแก้ไขข้อความถือเป็น "ข้อผิดพลาดของการไบแซนไทน์"

การจำแนกอัลกอริทึมเห็นด้วย

ระบบบล็อกเชนเป็นชนิดของระบบกระจายที่เป็นพิเศษ โดยเฉพาะเชนสาธารณะ เช่น Bitcoin และ Ethereum ซึ่งประกอบด้วยโหนดเครือข่ายที่กระจายและไม่ไว้วางใจใครบางคนในจำนวนมาก กลไกตรวจสอบที่ใช้ในบล็อกเชน รักษาให้ระบบบล็อกเชนบรรลุความสอดคล้องข้อมูลอย่างต่อเนื่องโดยไม่มีการแยกย่อย
โดยอิงจากประเภทการทนความผิดพร่อง อัลกอริทึมเชื่อมั่นสามารถจำแนกเป็นอัลกอริทึมที่ไม่สามารถทนความผิดพร่องแบบไบแซนไทน์ (CFT) และอัลกอริทึมทนความผิดพร่องแบบไบแซนไทน์ (BFT)

อัลกอริทึมที่ไม่ทนความผิดพร่องแบบไบแซนไทน์

ในระบบแบบกระจายอัลกอริธึม Non-Byzantine Fault Tolerance ช่วยให้มั่นใจได้ถึงความน่าเชื่อถือของระบบแบบกระจายทั้งหมดเมื่อโหนดประสบกับความล้มเหลวของระบบหรือการหยุดทํางานที่ไม่ได้วางแผนไว้ (ความผิดพลาดที่ไม่ใช่ไบแซนไทน์) อย่างไรก็ตาม, เมื่อโหนดที่เป็นอันตรายปลอมแปลงหรือยุ่งเกี่ยวกับข้อมูล, อัลกอริธึม Non-Byzantine Fault Tolerance ไม่สามารถรับประกันความน่าเชื่อถือของระบบได้. อัลกอริทึมเหล่านี้ใช้เป็นหลักในระบบกระจายขององค์กรแบบปิดที่มีการควบคุม อัลกอริธึม Non-Byzantine Fault Tolerance ที่เป็นตัวแทนมากที่สุด ได้แก่ อัลกอริทึม Paxos และอัลกอริทึม Raft

อัลกอริธึมความทนทานต่อความผิดพลาดของไบแซนไทน์

อัลกอริธึม Byzantine Fault Tolerance ช่วยให้ระบบแบบกระจายมั่นใจได้ถึงความน่าเชื่อถือแม้ว่าโหนดจะพบข้อผิดพลาดประเภทใด ๆ ตราบใดที่จํานวนโหนดที่ผิดพลาดไม่เกินสัดส่วนที่กําหนด พูดง่ายๆก็คือตราบใดที่จํานวนโหนดที่ผิดพลาด (เนื่องจากความผิดพลาดที่ไม่ใช่ไบแซนไทน์หรือไบแซนไทน์) น้อยกว่าสัดส่วนที่แน่นอนของโหนดทั้งหมดอัลกอริธึม Byzantine Fault Tolerance สามารถรับประกันความน่าเชื่อถือของระบบได้ เนื่องจากมีโหนดเครือข่ายที่ไม่ไว้วางใจจํานวนมากในระบบบล็อกเชนเช่น Bitcoin และ Ethereum อัลกอริธึม Byzantine Fault Tolerance จึงถูกใช้เป็นหลักในกลไกฉันทามติของบล็อกเชน อัลกอริธึม Byzantine Fault Tolerance ที่เป็นตัวแทนมากที่สุด ได้แก่ PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work) และ PoS (Proof of Stake)