ปัญหา ต้นไม้แผ่คลุมขั้นต่ำแบบกระจาย (MST)เกี่ยวข้องกับการสร้างต้นไม้แผ่คลุมขั้นต่ำโดยใช้อัลกอริทึมแบบกระจายในเครือข่ายที่โหนดต่างๆ สื่อสารกันโดยการส่งข้อความ ปัญหานี้แตกต่างอย่างสิ้นเชิงจากปัญหาแบบลำดับคลาสสิก แม้ว่าวิธีการพื้นฐานที่สุดจะคล้ายกับอัลกอริทึมของ Borůvkaก็ตาม การประยุกต์ใช้ที่สำคัญอย่างหนึ่งของปัญหานี้คือการค้นหาต้นไม้ที่สามารถใช้สำหรับการกระจายสัญญาณโดยเฉพาะอย่างยิ่ง หากต้นทุนในการส่งข้อความผ่านขอบในกราฟมีนัยสำคัญ MST สามารถลดต้นทุนรวมสำหรับกระบวนการต้นทางในการสื่อสารกับกระบวนการอื่นๆ ทั้งหมดในเครือข่ายได้

ปัญหาดังกล่าวได้รับการเสนอและแก้ไขเป็นครั้งแรก^ในปี พ.ศ. 2526 โดย Gallager และคณะ [ ^{1 ]}โดยที่คือจำนวนจุดยอดในกราฟต่อมา วิธีแก้ปัญหาได้รับการปรับปรุงเป็น^{[ 2 ]}และในที่สุด^{[ 3 ] [ 4 ]}โดยที่Dคือเครือข่ายหรือเส้นผ่านศูนย์กลางของกราฟ ขอบเขตล่างของความซับซ้อนของเวลาในการแก้ปัญหาได้รับการแสดงให้เห็นในที่สุดว่าคือ^{[ 5 ]}${\displaystyle O(V\log V)}$${\displaystyle V}$${\displaystyle O(V)}$${\displaystyle O({\sqrt {V}}\log ^{*}V+D)}$${\displaystyle \Omega \left({{\frac {\sqrt {V}}{\log V}}+D}\right).}$

กราฟอินพุตถือเป็นเครือข่าย โดยที่จุดยอดเป็นโหนดการคำนวณอิสระ และขอบเป็นลิงก์การสื่อสาร ลิงก์มีน้ำหนักเช่นเดียวกับในปัญหาแบบคลาสสิก ${\displaystyle G(V,E)}$${\displaystyle V}$${\displaystyle E}$

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

ผลลัพธ์จากอัลกอริทึมนี้คือ โหนดทุกโหนดจะทราบว่าลิงก์ใดบ้างที่อยู่ในต้นไม้แผ่คลุมขั้นต่ำ และลิงก์ใดบ้างที่ไม่อยู่ในนั้น

แบบจำลองการส่งข้อความ ( Message -passing model) เป็นหนึ่งในแบบจำลองที่ใช้กันอย่างแพร่หลายที่สุดในระบบประมวลผลแบบกระจายในแบบจำลองนี้ แต่ละกระบวนการจะถูกจำลองเป็นโหนดของกราฟ และแต่ละช่องทางการสื่อสารระหว่างสองกระบวนการจะเป็นขอบของกราฟ

อัลกอริทึมที่ใช้กันทั่วไปสองแบบสำหรับปัญหาต้นไม้แผ่คลุมขั้นต่ำแบบคลาสสิก ได้แก่อัลกอริทึมของ Primและอัลกอริทึมของ Kruskalอย่างไรก็ตาม การนำอัลกอริทึมทั้งสองนี้ไปใช้ในแบบจำลองการส่งข้อความแบบกระจายนั้นทำได้ยาก ความท้าทายหลักๆ คือ:

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

เนื่องจากความยากลำบากเหล่านี้ จึงจำเป็นต้องมีเทคนิคใหม่สำหรับอัลกอริธึม MST แบบกระจายในแบบจำลองการส่งข้อความ บางเทคนิคมีความคล้ายคลึงกับอัลกอริธึมของ Borůvkaสำหรับปัญหา MST แบบคลาสสิก

อัลกอริทึม GHS ^{[ 1 ]}ของGallager , Humblet และ Spira เป็นหนึ่งในอัลกอริทึมที่รู้จักกันดีที่สุดในทฤษฎีการคำนวณแบบกระจาย อัลกอริทึมนี้สร้าง MST ในรูปแบบการส่งข้อความแบบอะซิงโครนัส

อัลกอริทึม GHS จำเป็นต้องมีข้อสมมติหลายประการ

• กราฟที่ป้อนเข้ามาเป็นกราฟเชื่อมต่อและไม่มีทิศทาง
• แต่ละขอบในกราฟอินพุตมีน้ำหนักที่แน่นอนและแตกต่างกัน ข้อสมมตินี้ไม่จำเป็นหากมีวิธีการที่สอดคล้องกันในการแก้ปัญหาความเท่ากันของน้ำหนักขอบ
• แต่ละโหนดจะทราบน้ำหนักของแต่ละเส้นเชื่อมที่เข้ามายังโหนดนั้นตั้งแต่เริ่มต้น
• ในขั้นต้น โหนดแต่ละโหนดจะอยู่ในสถานะไม่ทำงาน โหนดแต่ละโหนดจะตื่นขึ้นมาเองโดยธรรมชาติ หรือถูกปลุกให้ตื่นโดยการรับข้อความจากโหนดอื่น
• ข้อความสามารถส่งได้อย่างอิสระในทั้งสองทิศทางบนขอบเครือข่าย และจะมาถึงหลังจากความล่าช้าที่ไม่สามารถคาดเดาได้แต่มีค่าแน่นอน โดยปราศจากข้อผิดพลาด
• แต่ละสายจะส่งข้อความตามลำดับFIFO (First In, First Out)

กำหนดให้ส่วนย่อยของ MST เป็นต้นไม้ย่อยของนั่นคือ ส่วนย่อยคือเซตของโหนดและขอบที่เชื่อมต่อกันของMST มีคุณสมบัติสำคัญสองประการที่เกี่ยวข้องกับส่วนย่อย: ^{[ 1 ]}${\displaystyle T}$${\displaystyle T}$${\displaystyle T}$

1. กำหนดให้ส่วนหนึ่งของต้นไม้ครอบคลุมน้อยที่สุด (MST) มาเป็นส่วนหนึ่ง และให้เป็นขอบขาออกที่มีน้ำหนักน้อยที่สุดของส่วนหนึ่งนั้น การเชื่อมและโหนดที่อยู่ติดกันที่ไม่ใช่ส่วนหนึ่งของส่วนหนึ่งเข้ากับส่วนหนึ่งนั้น จะได้ส่วนหนึ่งอีกส่วนหนึ่งของต้นไม้ครอบคลุมน้อยที่สุด (MST)${\displaystyle T}$${\displaystyle e}$${\displaystyle e}$
2. ถ้าขอบทั้งหมดของกราฟที่เชื่อมต่อกันมีน้ำหนักต่างกัน ต้นไม้ครอบคลุมน้อยที่สุด (MST) ของกราฟนั้นจะมีเพียงหนึ่งเดียว

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

อัลกอริทึม GHS กำหนดระดับ ให้กับแต่ละส่วนย่อย ซึ่งเป็น จำนวนเต็มที่ไม่ลดลงโดยมีค่าเริ่มต้นเป็น 0 ยิ่งไปกว่านั้น แต่ละส่วนย่อยที่มีระดับไม่เป็นศูนย์จะมีIDซึ่งเป็น ID ของขอบหลักในส่วนย่อย ซึ่งจะถูกเลือกเมื่อสร้างส่วนย่อย ในระหว่างการดำเนินการของอัลกอริทึม แต่ละโหนดสามารถจำแนกขอบที่เข้ามาแต่ละขอบออกเป็นสามประเภท: ^{[ 1 ] [ 6 ]}

• ขอบ สาขาคือขอบที่ถูกกำหนดว่าเป็นส่วนหนึ่งของ MST (Minimum Strategies)
• เส้นเชื่อม ที่ถูกปฏิเสธคือเส้นเชื่อมที่ถูกพิจารณาแล้วว่าไม่ได้เป็นส่วนหนึ่งของ MST (Minimum Stable Tree)
• เส้นเชื่อม พื้นฐานคือเส้นเชื่อมทั้งหมดที่ไม่ใช่เส้นเชื่อมสาขาหรือเส้นเชื่อมที่ถูกปฏิเสธ

ในส่วนประกอบระดับ 0 โหนดที่ตื่นขึ้นแต่ละโหนดจะทำสิ่งต่อไปนี้:

1. เลือกขอบด้านที่มีน้ำหนักน้อยที่สุดและทำเครื่องหมายขอบนั้นเป็นขอบสาขา
2. ส่งข้อความผ่านขอบสาขาเพื่อแจ้งเตือนโหนดอีกด้านหนึ่ง
3. รอรับข้อความจากอีกฝั่งหนึ่งของขอบฟ้า

เส้นเชื่อมที่ถูกเลือกโดยโหนดทั้งสองที่เชื่อมต่อกัน จะกลายเป็นเส้นเชื่อมหลัก และถูกกำหนดให้มีระดับ 1

ในส่วนย่อยที่ไม่ใช่ระดับศูนย์ จะมีการเรียกใช้อัลกอริทึมแยกต่างหากในแต่ละระดับ อัลกอริทึมนี้สามารถแบ่งออกเป็นสามขั้นตอน ได้แก่ การกระจายสัญญาณ การรวมสัญญาณ และการเปลี่ยนแปลงแกนหลัก

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

ในขั้นตอนนี้ โหนดทั้งหมดในส่วนย่อยจะร่วมมือกันเพื่อค้นหาขอบขาออกที่มีน้ำหนักน้อยที่สุดของส่วนย่อยนั้น ขอบขาออกคือขอบที่เชื่อมต่อกับส่วนย่อยอื่นๆ ข้อความที่ส่งในขั้นตอนนี้จะมีทิศทางตรงกันข้ามกับขั้นตอนการกระจายเสียง โดยเริ่มต้นจากโหนดใบทั้งหมด (โหนดที่มีขอบสาขาเพียงเส้นเดียว) ข้อความจะถูกส่งผ่านขอบสาขา ข้อความนั้นจะประกอบด้วยน้ำหนักน้อยที่สุดของขอบขาออกที่พบ (หรือค่าอนันต์หากไม่พบขอบดังกล่าว) วิธีการค้นหาขอบขาออกที่มีน้ำหนักน้อยที่สุดจะกล่าวถึงในภายหลัง สำหรับแต่ละโหนดที่ไม่ใช่โหนดใบ เมื่อกำหนดจำนวนขอบสาขาเป็น n แล้วหลังจากได้รับข้อความ convergecast แล้ว โหนดนั้นจะเลือกน้ำหนักน้อยที่สุดจากข้อความและเปรียบเทียบกับน้ำหนักของขอบขาออกที่เชื่อมต่อกับโหนดนั้น น้ำหนักที่น้อยที่สุดจะถูกส่งไปยังสาขาที่ได้รับข้อความกระจายเสียงมา ${\displaystyle n}$${\displaystyle n-1}$

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

ดังที่กล่าวไว้ข้างต้น โหนดทุกโหนดจำเป็นต้องค้นหาขอบขาออกที่มีน้ำหนักน้อยที่สุดหลังจากได้รับข้อความกระจายเสียงจากแกนหลัก หากโหนดได้รับข้อความกระจายเสียง โหนดนั้นจะเลือกขอบพื้นฐานที่มีน้ำหนักน้อยที่สุดและส่งข้อความไปยังโหนดอีกด้านหนึ่งพร้อมกับ ID และระดับของส่วนย่อย จากนั้น โหนดจะตัดสินใจว่าขอบนั้นเป็นขอบขาออกหรือไม่ และส่งข้อความกลับไปแจ้งผลลัพธ์ให้โหนดอื่นทราบ การตัดสินใจจะดำเนินการตามขั้นตอนดังต่อไปนี้: ${\displaystyle n}$${\displaystyle n'}$${\displaystyle n'}$${\displaystyle n}$

1. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)={\mathit {Fragment}}_{\mathit {ID}}(n')}$กล่าวคือ โหนดและอยู่ในแฟรกเมนต์เดียวกัน ดังนั้นเส้นเชื่อมจึงไม่ใช่เส้นเชื่อมออก${\displaystyle n}$${\displaystyle n'}$
2. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')}$และนั่นคือ โหนดและเป็นของส่วนย่อยที่แตกต่างกัน ดังนั้นเส้นเชื่อมจึงเป็นเส้นเชื่อมออก${\displaystyle {\mathit {Level}}(n)\leq {\mathit {Level}}(n')}$${\displaystyle n}$${\displaystyle n'}$
3. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')}$และ. เราไม่สามารถสรุปใดๆ ได้ เหตุผลก็คือ โหนดทั้งสองอาจอยู่ในกลุ่มเดียวกันอยู่แล้ว แต่โหนดยังไม่ทราบข้อเท็จจริงนี้เนื่องจากความล่าช้าของข้อความที่ส่งแบบกระจาย ในกรณีนี้ อัลกอริทึมจะอนุญาตให้โหนดเลื่อนการตอบกลับออกไปจนกว่าระดับของมันจะสูงกว่าหรือเท่ากับระดับที่ได้รับจากโหนด.${\displaystyle {\mathit {Level}}(n)>{\mathit {Level}}(n')}$${\displaystyle n'}$${\displaystyle n'}$${\displaystyle n}$

ให้และเป็นสองส่วนย่อยที่ต้องนำมารวมกัน มีสองวิธีในการทำเช่นนี้: ^{[ 1 ] [ 6 ]}${\displaystyle F}$${\displaystyle F'}$

• ผสาน : การดำเนินการนี้จะเกิดขึ้นหากทั้งสองส่วนมีขอบขาออกที่มีน้ำหนักต่ำสุดร่วมกัน และระดับของส่วนที่ผสานแล้วจะเป็น${\displaystyle F}$${\displaystyle F'}$${\displaystyle {\mathit {Level}}(F)={\mathit {Level}}(F')}$${\displaystyle {\mathit {Level}}(F)+1}$
• ดูดซับ : การดำเนินการนี้จะเกิดขึ้นหากชิ้นส่วนที่รวมกันจะมีระดับเดียวกับ${\displaystyle {\mathit {Level}}(F)<{\mathit {Level}}(F')}$${\displaystyle F'}$

นอกจากนี้ เมื่อเกิดการดำเนินการ "ดูดซับ" (Absorb) จะต้องอยู่ในขั้นตอนของการเปลี่ยนแปลงแกนหลัก ในขณะที่สามารถอยู่ในขั้นตอนใดก็ได้ ดังนั้น การดำเนินการ "ดูดซับ" อาจทำได้แตกต่างกันไปขึ้นอยู่กับสถานะของให้เป็นขอบที่และต้องการรวมเข้าด้วยกัน และให้และเป็นโหนดสองโหนดที่เชื่อมต่อกันด้วยในและตามลำดับ มีสองกรณีที่ต้องพิจารณา: ${\displaystyle F}$${\displaystyle F'}$${\displaystyle F'}$${\displaystyle e}$${\displaystyle F}$${\displaystyle F'}$${\displaystyle n}$${\displaystyle n'}$${\displaystyle e}$${\displaystyle F}$${\displaystyle F'}$

ดังที่กล่าวไว้ข้างต้น ชิ้นส่วนต่างๆ จะถูกรวมเข้าด้วยกันโดยใช้การดำเนินการ "ผสาน" (Merge) หรือ "ดูดซับ" (Absorb) การดำเนินการ "ดูดซับ" จะไม่เปลี่ยนแปลงระดับสูงสุดในบรรดาชิ้นส่วนทั้งหมด การดำเนินการ "ผสาน" อาจเพิ่มระดับสูงสุดขึ้น 1 ระดับ ในกรณีที่เลวร้ายที่สุด ชิ้นส่วนทั้งหมดจะถูกรวมเข้าด้วยกันโดยใช้การดำเนินการ "ผสาน" ดังนั้นจำนวนชิ้นส่วนจะลดลงครึ่งหนึ่งในแต่ละระดับ ดังนั้นจำนวนระดับสูงสุดคือโดยที่คือจำนวนโหนด ${\displaystyle O(\log V)}$${\displaystyle V}$

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

Maleq Khan และ Gopal Pandurangan ได้พัฒนาอัลกอริทึมการประมาณค่า[ ^{7 ] อั}ลกอริทึมนี้ทำงานในเวลา โดยที่คือเส้นผ่านศูนย์กลางเส้นทางที่สั้นที่สุดในท้องถิ่น^{[ 7 ]}ของกราฟ ${\displaystyle O(\log n)}$${\displaystyle O(D+L\log n)}$${\displaystyle L}$