แบบจำลองเวลาและความล้มเหลว

แบบจำลองเวลาและความล้มเหลวระบุสิ่งที่อัลกอริทึมแบบกระจายอาจสันนิษฐานเกี่ยวกับความล่าช้าของข้อความและความเร็วของโปรเซสเซอร์ และวิธีการที่ส่วนประกอบต่าง ๆ ได้รับอนุญาตให้ล้มเหลวได้

Definition

แบบจำลองเวลากำหนดข้อสมมติฐานเกี่ยวกับขีดจำกัดบนของเวลาการส่งข้อความและความเร็วสัมพัทธ์ของกระบวนการ ในขณะที่แบบจำลองความล้มเหลวกำหนดชุดของวิธีการที่กระบวนการและช่องทางอาจเบี่ยงเบนไปจากพฤติกรรมที่ระบุไว้

Scope

หัวข้อนี้ครอบคลุมแบบจำลองเวลาแบบซิงโครนัส อะซิงโครนัส และกึ่งซิงโครนัส; การจำแนกประเภทของความล้มเหลวตั้งแต่การขัดข้อง (fail-stop) ไปจนถึงการละเว้นและเวลา ไปจนถึงความผิดพลาดแบบสุ่ม (Byzantine); และการสร้างนามธรรมของตัวตรวจจับความล้มเหลวที่เชื่อมโยงระบบอะซิงโครนัสกับการให้เหตุผลโดยอาศัยการหมดเวลา แบบจำลองเหล่านี้เป็นสัจพจน์ที่ใช้ในการอนุมานผลลัพธ์ทั้งที่เป็นไปได้และเป็นไปไม่ได้

Core questions

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

Key theories

ภาวะกึ่งซิงโครนัส

ระบบจริงไม่ได้เป็นทั้งซิงโครนัสเต็มรูปแบบหรืออะซิงโครนัสเต็มรูปแบบ; แบบจำลองกึ่งซิงโครนัสสันนิษฐานว่ามีขีดจำกัดของความล่าช้าและความเร็วที่คงอยู่ตลอดไปหรือยังไม่ทราบ ซึ่งเพียงพอที่จะแก้ไขปัญหาฉันทามติในขณะที่ยังคงความเป็นจริง

ลำดับชั้นของแบบจำลองความล้มเหลว

ความล้มเหลวมีตั้งแต่การขัดข้องแบบ fail-stop ที่ไม่รุนแรง ไปจนถึงการละเว้นการส่ง/รับและการละเมิดเวลา ไปจนถึงพฤติกรรม Byzantine แบบสุ่ม; ความรุนแรงของความล้มเหลวที่โปรโตคอลต้องทนทานกำหนดปัจจัยการจำลองแบบที่จำเป็นและความซับซ้อนของข้อความ

ตัวตรวจจับความล้มเหลวที่ไม่น่าเชื่อถือ

ตัวตรวจจับความล้มเหลวแบบนามธรรมให้คำแนะนำที่อาจไม่ถูกต้องเกี่ยวกับกระบวนการที่ขัดข้อง; การระบุลักษณะของตัวตรวจจับที่อ่อนแอที่สุดที่เพียงพอต่อการแก้ไขปัญหาฉันทามติจะช่วยประสานความแม่นยำของระบบอะซิงโครนัสกับการนำไปใช้งานจริงโดยอาศัยการหมดเวลา

Clinical relevance

ระบบการผลิตมักจะเลือกแบบจำลองเวลาและความล้มเหลวโดยปริยายเมื่อมีการตั้งค่าการหมดเวลา เลือกปัจจัยการจำลองแบบ หรือตัดสินใจว่าจะป้องกันผู้เข้าร่วมที่เป็นอันตรายหรือไม่ การตั้งสมมติฐานเหล่านี้ผิดพลาดเป็นสาเหตุหลักที่พบบ่อยของเหตุการณ์ split-brain และข้อมูลสูญหาย

History

หลังจากที่แบบจำลองอะซิงโครนัสแสดงให้เห็นว่าอ่อนแอเกินไปสำหรับการสร้างฉันทามติที่ทนทานต่อความผิดพลาด Dwork, Lynch, และ Stockmeyer ได้นำเสนอภาวะกึ่งซิงโครนัสในปี 1988 และ Chandra และ Toueg ได้กำหนดรูปแบบตัวตรวจจับความล้มเหลวที่ไม่น่าเชื่อถือในปี 1996 ซึ่งทั้งหมดนี้ได้มอบเครื่องมือในการสร้างแบบจำลองที่ทำให้ข้อตกลงที่ทนทานต่อความผิดพลาดในทางปฏิบัติเป็นไปได้

Debates

การหมดเวลาเป็นข้อสมมติฐานด้านเวลาหรือตัวตรวจจับความล้มเหลว?

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

Key figures

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

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

เหตุใดการตรวจจับความล้มเหลวที่เชื่อถือได้จึงไม่สามารถนำไปใช้ในระบบอะซิงโครนัสบริสุทธิ์ได้?

หากไม่มีขีดจำกัดของความล่าช้าของข้อความ กระบวนการที่ช้ามากแต่ยังทำงานอยู่จะไม่สามารถแยกแยะได้จากกระบวนการที่ขัดข้อง ดังนั้นตัวตรวจจับใด ๆ จะต้องผิดพลาดในบางครั้ง นี่คือเหตุผลที่ระบบอะซิงโครนัสได้รับการเสริมด้วยข้อสมมติฐานด้านเวลาหรือตัวตรวจจับที่ไม่น่าเชื่อถือ