อัลกอริทึม Dijkstra–Scholten (ตั้งชื่อตามEdsger W. DijkstraและCarel S. Scholten ) เป็นอัลกอริทึมสำหรับการตรวจจับการสิ้นสุดในระบบกระจาย^{[ 1 ] [ 2 ]}อัลกอริทึมนี้ได้รับการเสนอโดย Dijkstra และ Scholten ในปี 1980 ^{[ 3 ]}

ก่อนอื่น ลองพิจารณากรณีของกราฟกระบวนการ อย่างง่าย ซึ่งเป็นโครงสร้างแบบต้นไม้การคำนวณแบบกระจายที่มีโครงสร้างแบบต้นไม้นั้นไม่ใช่เรื่องแปลก กราฟกระบวนการดังกล่าวอาจเกิดขึ้นเมื่อการคำนวณเป็นแบบแบ่งและพิชิต อย่างเคร่งครัด โหนดเริ่มต้นการคำนวณและแบ่งปัญหาออกเป็นสองส่วน (หรือโดยปกติแล้วจะเป็นจำนวนเท่าๆ กันของ 2) ที่เท่าๆ กันโดยประมาณ และกระจายส่วนเหล่านั้นไปยังโปรเซสเซอร์อื่นๆ กระบวนการนี้จะดำเนินต่อไปแบบเรียกซ้ำจนกว่าปัญหาจะมีขนาดเล็กพอที่จะแก้ไขได้ในโปรเซสเซอร์เดียว

อัลกอริทึม Dijkstra–Scholten เป็นอัลกอริทึมแบบต้นไม้ ซึ่งสามารถอธิบายได้ดังต่อไปนี้:

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

• สำหรับโครงสร้างแบบต้นไม้ การตรวจจับการสิ้นสุดการทำงานทำได้ง่าย เมื่อกระบวนการในโหนดใบตรวจพบว่าตนเองสิ้นสุดการทำงานแล้ว มันจะส่งสัญญาณไปยังโหนดแม่ โดยทั่วไปแล้ว กระบวนการจะรอให้กระบวนการลูกทั้งหมดส่งสัญญาณก่อน จากนั้นจึงส่งสัญญาณไปยังโหนดแม่
• โปรแกรมจะหยุดทำงานเมื่อรูทได้รับสัญญาณจากลูกทั้งหมดของมัน

• อัลกอริทึมสำหรับต้นไม้สามารถขยายไปใช้กับกราฟทิศทางที่ไม่มีวงจรได้ โดยเราจะเพิ่มคุณลักษณะจำนวนเต็มเพิ่มเติมที่เรียกว่า "ส่วนขาด" ให้กับแต่ละขอบ
• ในขอบขาเข้า ค่า Deficit จะแสดงถึงความแตกต่างระหว่างจำนวนข้อความที่ได้รับและจำนวนสัญญาณที่ส่งตอบกลับ
• เมื่อโหนดต้องการยุติการเชื่อมต่อ โหนดจะรอจนกว่าจะได้รับสัญญาณจากขอบขาออกที่ลดค่าความขาดดุลลงเหลือศูนย์
• จากนั้นระบบจะส่งสัญญาณมากพอเพื่อให้แน่ใจว่าค่าความขาดดุลเป็นศูนย์ในแต่ละขอบขาเข้า
• เนื่องจากกราฟไม่มีวงจร ดังนั้นบางโหนดจะไม่มีเส้นเชื่อมขาออก และโหนดเหล่านี้จะเป็นโหนดแรกที่สิ้นสุดการทำงานหลังจากส่งสัญญาณไปยังเส้นเชื่อมขาเข้ามากพอแล้ว หลังจากนั้น โหนดในระดับที่สูงขึ้นจะสิ้นสุดการทำงานทีละระดับ

• หากอนุญาตให้มีวงจรได้ อัลกอริทึมก่อนหน้านี้จะไม่ทำงาน เนื่องจากอาจไม่มีโหนดใดที่มีเส้นเชื่อมขาออกเป็นศูนย์ ดังนั้นจึงอาจไม่มีโหนดใดที่สามารถยุติการทำงานได้โดยไม่ต้องปรึกษาโหนดอื่น
• อัลกอริทึม Dijkstra–Scholten แก้ปัญหานี้โดยการสร้างต้นไม้แผ่คลุม (spanning tree)ของกราฟโดยปริยาย ต้นไม้แผ่คลุมคือต้นไม้ที่รวมโหนดแต่ละโหนดของกราฟพื้นฐานเพียงครั้งเดียว และเซตของขอบเป็นเซตย่อยของเซตของขอบเดิม
• โครงสร้างต้นไม้จะเป็นแบบมีทิศทาง (กล่าวคือ ช่องทางต่างๆ จะมีทิศทาง) โดยมีโหนดต้นทาง (ซึ่งเริ่มต้นการคำนวณ) เป็นโหนดราก
• ต้นไม้แผ่ขยาย (spanning tree) ถูกสร้างขึ้นด้วยวิธีดังต่อไปนี้ มีการเพิ่มตัวแปรFirst_Edgeให้กับแต่ละโหนด เมื่อโหนดได้รับข้อความเป็นครั้งแรก โหนดจะกำหนดค่าเริ่มต้นให้กับFirst_Edgeด้วยขอบที่รับข้อความนั้นมาFirst_Edgeจะไม่เปลี่ยนแปลงหลังจากนั้น โปรดทราบว่า ต้นไม้แผ่ขยายนี้ไม่มีเพียงต้นเดียว และขึ้นอยู่กับลำดับของข้อความในระบบ
• แต่ละโหนดจะดำเนินการยุติการทำงานในสามขั้นตอนดังนี้:
  1. ส่งสัญญาณบนขอบขาเข้าทั้งหมด ยกเว้นขอบแรก (แต่ละโหนดจะส่งสัญญาณเพื่อลดค่าขาดดุลบนขอบขาเข้าแต่ละเส้นให้เป็นศูนย์)
  2. รอรับสัญญาณจากทุกขอบขาออก (จำนวนสัญญาณที่ได้รับในแต่ละขอบขาออกควรลดค่าความขาดดุลของแต่ละขอบให้เป็นศูนย์)
  3. ส่งสัญญาณบนFirst_Edge (เมื่อขั้นตอนที่ 1 และ 2 เสร็จสมบูรณ์ โหนดจะแจ้งให้โหนดแม่ในต้นไม้แผ่ขยายทราบถึงความตั้งใจที่จะยุติการทำงาน)

• อัลกอริทึมของหวง