[CS] ปัญหาสองนายพล

Two generals’ problem หรือ Two generals’ paradox หรือ Two armies problem เป็นปัญหาคลาสสิกในด้านวิทยาการคอมพิวเตอร์ ซึ่งจะกล่าวถึงการสื่อสารระหว่าง 2 principals ที่อยู่คนละที่กันโดยผ่านช่องทางที่ไม่เสถียรหรือไม่ปลอดภัย ซึ่งสามารถยกตัวอย่างให้เห็นภาพแบบง่าย ๆ ได้ดังนี้

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

ดังนั้นนายพลทั้ง 2 คนจะต้องนัดหมายวันและเวลาเพื่อโจมตีพร้อมกัน โดยต้องมีนายพลจากฝั่งใดฝั่งหนึ่งส่งสารไปหานายพลอีกฝั่งหนึ่ง

ในที่นี้จะสมมติว่านายพล A ส่งข้อความว่า “โจมตี ณ ตอนรุ่งสางของวันพรุ่งนี้” ผ่านทางม้าเร็ว (Messenger) ไปหานายพล B ซึ่งม้าเร็วนี้จำเป็นต้องวิ่งผ่านเมือง C ซึ่งไม่ปลอดภัย

หากม้าเร็วถูกสังหารโดยเมือง C ก่อนที่จะนำสารไปถึงนายพล B จะส่งผลให้นายพล A บุกโจมตีเพียงลำพังซึ่งจะพ่ายแพ้ในที่สุด

นายพล A จึงแก้ปัญหาโดยการให้นายพล B ส่ง ข้อความยืนยัน (Ack) กลับมาเพื่อบอกว่าได้รับสารจากนายพล A แล้วนะ ซึ่งดูเหมือนจะแก้ปัญหานี้ได้ (ข้ามประเด็นเรื่องข้อมูลอาจถูกบิดเบือนโดยเมือง C ทั้งขาไปและขากลับไปก่อน)

แต่ไม่ใช่ เพราะจะเจอปัญหาเดิมอีก กล่าวคือนายพล B กังวลว่านายพล A ได้รับ Ack แล้วหรือยัง ซึ่งหากนายพล A ไม่ได้รับ นายพล B ก็จะนำกองทัพไปบุกเมือง C เพียงลำพัง และจะพ่ายแพ้ในที่สุด

นายพล B จึงแก้ปัญหาโดยการให้นายพล A ส่ง ack กลับมาอีกว่า “ยืนยันว่าได้รับข้อความที่ยืนยันการโจมตีตอนรุ่งสางพรุ่งนี้แล้วนะ”

จะเห็นว่าปัญหานี้จะเกิดขึ้นไม่จบไม่สิ้น และยังคงเป็นปัญหาที่ไม่สามารถแก้ได้ (การันตีอะไรไม่ได้)

ลองจินตนาการว่าเครื่องคอมพิวเตอร์ 2 เครื่องที่มีสถานะเป็น inconsistant state ต้องสื่อสารกันผ่านเครือข่ายที่ไม่เถียรซึ่งก็คือ Transmission control protocol (TCP) โดย TCP จะใช้กลไก 4-way handshake ในการตกลงกันก่อนที่จะสื่อสาร

หากคอมพิวเตอร์ทั้ง 2 เครื่องได้รับ Ack จากอีกเครื่องแล้ว การสื่อสารข้อมูลกันจะเริ่มต้นขึ้นหลังจากนี้ แต่หากสมมติว่าคอมพิวเตอร์ A ไม่ได้รับ Fin จากคอมพิวเตอร์ B หลังจากที่ได้รับ Ack แล้วจะเกิดสิ่งที่เรียกว่า half-open connection ซึ่งจะไม่สามารถสื่อสารกันต่อได้

จะเห็นได้ว่าแม้แต่ TCP ซึ่งเป็น protocol ที่มีความน่าเชื่อถือสูงก็ยังไม่สามารถแก้ไขปัญหา two generals’ problem ได้ แต่ก็ยังโชคดีที่เราพอจะมีวิธีที่จะสู้กับปัญหานี้อยู่บ้าง

วิธีที่ 1 : เราจะยอมรับการสื่อสารผ่านทางช่องทางที่ไม่เสถียรและอนุญาตให้ข้อมูลบางอันหล่นหายได้ แต่ต้องมีการกำหนด mitigation degree ไว้

ย้อนกลับมาที่นายพล A จะเกิดอะไรขึ้นถ้าจากเดิมที่นายพล A จะส่งข้อความไปหานายพล B แค่เพียงครั้งเดียว เปลี่ยนเป็นส่งไปหลาย ๆ ฉบับ เช่น 100 ฉบับ โดยตั้งสมมติฐานว่านายพล B คงจะได้รับข้อความอย่างน้อย 1 ฉบับ

ข้อความแต่ละฉบับของนายพล A ที่ส่งไปจะมีตัวเลขกำกับเช่น ฉบับที่ 1 ถึงฉบับที่ 100 เมื่อนายพล B ได้รับข้อความจากนายพล A สิ่งที่นายพล B ได้เรียนรู้นอกจากข้อความหลักที่นายพล A ส่งมาแล้ว นายพล B สามารถวิเคราะห์ได้ว่าช่องทางในการส่งม้าเร็วมานั้นมีความน่าเชื่อถือมากน้อยแค่ไหนโดยดูจากจำนวนข้อความที่ได้รับ

วิธีการแบบนี้จะทำให้นายพลทั้ง 2 มีความมั่นใจเพิ่มขึ้น แต่ต้องแลกด้วยค่าใช้จ่ายในการส่งข้อความที่สูงขึ้น (ม้าเร็วอาจต้องสละชีวิตเยอะ)

วิธีที่ 2 : สมมติว่าการส่งม้าเร็วจากนายพล A ไปยังนายพล B ใช้เวลา 10 นาทีในการเดินทางไป และใช้เวลาเดินทางกลับเพื่อส่ง Ack จากนายพล B อีก 10 นาที รวมเป็น 20 นาที นายพล A จะส่งข้อมูลไปหานายพล B ทุก ๆ 20 นาที เมื่อไหร่ก็ตามที่นายพล A ได้รับข้อความ Ack จากนายพล B นายพล A จะหยุดส่งข้อความไปหานายพล B และในขณะเดียวกันหากนายพล B ไม่ได้รับข้อความจากนายพล A แสดงว่านายพล A ได้รับข้อความ Ack จากนายพล B แล้ว ซึ่งทำให้ทั้งนายพล A และนายพล B มีความมั่นใจเพิ่มขึ้น

จากวิธีการทั้ง 2 แบบนี้ จะเห็นว่าเราต้องเลือกระหว่าง “ค่าใช้จ่าย” กับ “ความเร็ว” ซึ่งเป็น trade-off ที่หลีกเลี่ยงไม่ได้

สรุป

ปัญหาสองนายพลเป็นปัญหาคลาสสิกใน computer science ซึ่งยังคงไม่สามารถแก้ไขได้ (unsolvable) โดยเราจะเจอปัญหานี้ก็ต่อเมื่อมีการพยายามสื่อสารกันบนเครือข่ายที่ไม่เสถียร ซึ่งปัญหาหลักก็คือ inconsistent state ส่งผลทำให้ knowledge ที่มีไม่ตรงกัน ซึ่งมีวิธีแก้ปัญหาที่สามารถนำไปใช้ในทางปฏิบัติได้อยู่ 2 แนวทาง (ตามที่ยกตัวอย่างมาด้านบน)

เพิ่มเติม

ปัญหาสองนายพลถูกตีพิมพ์เมื่อปี ค.ศ. 1975 ในหัวข้อ “Some constraints and trade-offs in the design of network communications” โดย Akkoyunlu และคณะ โดยในเปเปอร์ได้ยกตัวอย่างการสื่อสารระหว่างเหล่าอันธพาล (gangsters) 2 กลุ่ม ซึ่งสามารถอ่านเปเปอร์ได้ที่ https://dl.acm.org/doi/abs/10.1145/800213.806523

อ้างอิง

Akkoyunlu, E. A., Ekanadham, K., & Huber, R. V. (1975, November). Some constraints and tradeoffs in the design of network communications. In Proceedings of the fifth ACM symposium on Operating systems principles (pp. 67–74).

หมายเหตุ: Two generals’ problem ไม่เท่ากับ Byzentines generals problem (BGP)ซึ่ง BGP เป็น general version ของ two generals’ problem และ BGP จะพูดถึงเรื่อง distributed systems, fault tolerance , และ blockchain ซึ่งเราจะกล่าวถึง BGP ในบทความถัดไป

Finematics, “Two Generals’ Problem Explained”, location: https://www.youtube.com/watch?v=s8Wbt0b8bwY

Tom Scott, “The Two Generals’ Problem”, localtion: https://www.youtube.com/watch?v=IP-rGJKSZ3s