3.1 A Resilient, Asynchronous Broad

3.1 A Resilient, Asynchronous Broadcast
The revocation notification needs to be propagated to all alive processes in the specified communicator, even when new failures happen during the Revoke propagation. Therefore, it is in essence a reliable broadcast. Among the four defining qualities of a reliable broadcast usually considered in the literature (Termination, Validity, Integrity, Agreement) [19], the non-uniform variants of the properties are sufficient, and the integrity criteria can be relaxed in the
context of the Revoke algorithm. First, the agreement and validity properties ensure that
if a process broadcasts a value v, all processes deliver v. In the uniform-agreement case, that property extends to failed processes: if a failed process had delivered the value, then
it must be delivered at all correct processes. In the Revoke operation, if failures kill the initiator as well as all the already notified processes, the Revoke notification is indeed
lost, and surviving processes may never receive the notification. However, either correct processes are not expecting messages from the set of dead processes, therefore no operation can deadlock, or at least a correct process is directly trying to exchange messages with a dead process and will detect its failure, which means that its blocking operations will complete in error, and leave the opportunity for the application to reissue the Revoke operation. In all cases, a nonuniform reliable broadcast is sufficient to ensure deadlock free operation. This is of practical significance, because the reliable broadcast respecting the uniform-agreement property requires that the system is free of send-omission failures (that is, a send has completed, but the receiver does not receive the message) [19]. In MPI, when a send operation
completes, it does not mean that the receiver has delivered the message; the message may still be buffered on the sender process, and when that process is the victim of a crash failure, it may thereby simultaneously commit a send-omission failure. Ensuring that the network is free of send-omission failures requires the acknowledgement of sent messages, or additional rounds of message exchanges before delivering the reliable broadcast. As Revoke can be implemented with a
non-uniformly agreeing reliable broadcast, that extra cost is spared.Second, the integrity property states that a message is delivered once at most, and variants with additional ordering
properties exist, like FIFO or causal ordering between the delivery of different broadcasts. In the case of a Revoke notification, the first Revoke message to reach the process has
the effect of immutably altering the state of the communicator. Supplementary deliveries of Revoke messages for the same communicator have no effect. Similarly, if multiple initiators concurrently broadcast a Revoke notification on the same communicator, the order in which these notifications are delivered has no importance, as the final outcome is always a switch to an immutable revoked state. Therefore, we can retain a non-ordered, relaxed integrity reliable broadcast, in which we allow multiple out-of-order deliveries, but retain the reasonable assumption that Revoke messages do not appear out of “thin air”. Then, as long as the algorithm
still ensures the non-uniform agreement property, there are no opportunities for inconsistent views. These simplified requirements are crucial for decreasing the cost of the Revoke operation, as the size of the messages and the number of message exchanges rounds can be drastically increased when one needs to implement an ordered, uniform reliable broadcast. Given the non-uniform agreement, the no-ordering, and loose integrity properties, in the Revoke reliable broadcast, a process that receives its first Revoke message can perform a single round of emissions to all its neighbors, with a constant message size, and then deliver the Revoke notification immediately, without further verifications. The last important aspect is the topology of the overlaynetwork employed to perform the broadcast operation. In
the reliable broadcast algorithm, when a process receives a
broadcast message for the first time, it immediately broadcasts that same message to all its neighbors in the overlay graph. The agreement property can be guaranteed only
when failures do not disconnect the overlay graph. In early
prototype versions of the ulfm implementation, the reliable
broadcast procedure employed a fully connected network
(which guarantees that disconnected cliques never form).
Obviously, this method scales poorly as, with the number
or processes, the graph degree is linear, and the number of
exchanged messages is quadratic. In practice, at scale, the
large graph degree resulted in the application aborting due
to resource exhaustion (too many open channels simultaneously, not enough memory for unexpected messages, etc.).Therefore, one needs to consider a more scalable overlay
topolog

ผลลัพธ์ (ไทย) 1:

3.1 การออกอากาศที่ยืดหยุ่น แบบอะซิงโครนัสแจ้งเพิกถอนต้องแพร่กระจายไปกระบวนการที่มีชีวิตทั้งหมดใน communicator ระบุ แม้เมื่อความล้มเหลวเกิดขึ้นในระหว่างการยกเลิกการเผยแพร่ ดังนั้น ในสาระสำคัญเป็นการออกอากาศที่เชื่อถือได้ หมู่ 4 กำหนดคุณภาพของการออกอากาศที่เชื่อถือได้มักถือว่าในวรรณคดี (สิ้นสุด อายุ ความสมบูรณ์ สัญญา) [19], ตัวแปรไม่สม่ำเสมอของคุณสมบัติไม่เพียงพอ และเงื่อนไขความสมบูรณ์สามารถผ่อนคลายในการบริบทของอัลกอริทึมการยกเลิก แรก ให้คุณสมบัติข้อตกลงและตั้งแต่วันที่ถ้าการกระจายมีค่า v กระบวนการทั้งหมดส่ง v ในกรณีข้อตกลงเหมือนกัน คุณสมบัติขยายเพื่อล้มกระบวนการ: ถ้ากระบวนการล้มเหลวได้ส่งค่า จากนั้นจะต้องจัดส่งกระบวนการที่ถูกต้อง ในการดำเนินการยกเลิก ฆ่าความล้มเหลวเริ่มต้นเป็นกระบวนการทั้งหมดแล้วแจ้ง แจ้งยกเลิกว่าแน่นอนกระบวนการหายไป และรอดตายอาจไม่ได้รับการแจ้งเตือน อย่างไรก็ตาม กระบวนการที่ถูกต้องไม่ต้องข้อความจากกระบวนการตาย จึง มีการดำเนินการสามารถการชะงักงัน หรือกระบวนการที่ถูกต้องโดยตรงพยายามแลกเปลี่ยนข้อความ ด้วยกระบวนการตาย และจะตรวจพบความล้มเหลว ซึ่งหมายความว่า ให้ ดำเนินการปิดกั้นจะทำผิดพลาด และปล่อยโอกาสสำหรับโปรแกรมประยุกต์การดำเนินการถอนออกใหม่ ในทุกกรณี ออกอากาศ nonuniform น่าเชื่อถือเพียงพอให้ตายฟรี นี่คือความจริงสำคัญ เนื่องจากการออกอากาศที่น่าเชื่อถือเคารพคุณสมบัติข้อตกลงเหมือนกันว่า ระบบไม่มีงดส่งความล้มเหลว (คือ การส่งเสร็จสมบูรณ์ แต่ผู้รับได้รับข้อความ) [19] ใน MPI เมื่อการดำเนินการส่งเสร็จสิ้น มันไม่ได้หมายความ ว่า ผู้รับมีส่งข้อความ ข้อความอาจยังคงมีบัฟเฟอร์ในกระบวนการของผู้ส่ง และเมื่อกระบวนการที่ตกเป็นเหยื่อของความล้มเหลวผิดพลาด มันจึงพร้อมกันอาจยอมรับความล้มเหลวส่งงด ฟรีงดส่งความล้มเหลวในเครือข่ายต้องการตอบรับของข้อความที่ส่ง หรือเพิ่มรอบแลกเปลี่ยนข้อความก่อนที่จะส่งออกอากาศที่เชื่อถือได้ สามารถดำเนินการยกเลิกด้วยการสม่ำเสมอไม่ยอมเผยแพร่ที่เชื่อถือได้ ที่ค่าใช้จ่ายมี spared ที่สอง คุณสมบัติความแจ้งว่า การส่งข้อความครั้งเดียวอย่างมาก และตัวแปรกับการสั่งซื้อเพิ่มเติมคุณสมบัติมีอยู่ เช่น FIFO หรือสั่งเชิงสาเหตุระหว่างการส่งออกแตกต่างกัน ในกรณียกเลิกการแจ้งเตือน ข้อความแรกที่ยกเลิกไปถึงกระบวนการมีผลของการเปลี่ยนแปลงสถานะของ communicator ที่ immutably ส่งเสริมยกเลิกข้อความสำหรับ communicator เดียวจะไม่มีผล ในทำนองเดียวกัน หลายระดับพร้อมออกอากาศการแจ้งยกเลิกบนกระบวนการเดียวกันกับ communicator ใบสั่งที่มีการจัดส่งการแจ้งเตือนเหล่านี้ได้ไม่สำคัญ เป็นผลสุดท้ายจะสลับไปยังสถานะถูกเพิกถอนนั้น ดังนั้น เราสามารถรักษาความสมบูรณ์ไม่ใช่สั่ง ผ่อนคลายเชื่อออกอากาศ ซึ่งเราให้จัดส่งคำสั่งหลายครั้ง แต่ยังคงสมมติฐานที่สมเหตุสมผลไม่ปรากฏยกเลิกข้อความจาก "อากาศดี" จากนั้น ตราบเท่าที่การยังคง ทำให้คุณสมบัติข้อตกลงไม่สม่ำเสมอ ไม่มีโอกาสสำหรับมุมมองที่สอดคล้องกัน ข้อกำหนดเหล่านี้ง่ายขึ้นเป็นการลดต้นทุนของการเลิกการดำเนินการ ขนาดของข้อความ และจำนวนรอบการแลกเปลี่ยนข้อความสามารถจะเพิ่มขึ้นมากเมื่อหนึ่งต้องดำเนินการออกอากาศเชื่อสั่ง เหมือนกัน รับข้อตกลงไม่สม่ำเสมอ คุณสมบัติความสมบูรณ์ไม่มีการสั่งซื้อ และหลวม ในการเลิกเชื่อถือออกอากาศ กระบวนการที่ได้รับการยกเลิกข้อแรกสามารถทำรอบเดียวปล่อยให้ทั้งหมดของเพื่อนบ้าน มีขนาดคงข้อความ แล้ว แจ้งยกเลิกทันที โดยไม่ต้องดำเนินการตรวจสอบเพิ่มเติม สิ่งสำคัญครั้งสุดท้ายคือ โทโพโลยีของ overlaynetwork มาใช้ในการดำเนินการออกอากาศ ในความน่าเชื่อถือออกอากาศอัลกอริทึม เมื่อกระบวนการได้รับการข้อความที่ออกอากาศเป็นครั้งแรก มันทันทีกระจายข้อความเดียวกันกับประเทศเพื่อนบ้านในกราฟซ้อน สามารถรับประกันคุณสมบัติข้อตกลงเท่านั้นเมื่อล้มเหลวอย่าถอดกราฟซ้อน ในช่วงต้นรุ่นต้นแบบของการใช้งานใน ulfm มีความน่าเชื่อถือกระบวนการออกอากาศงานทั้งเครือข่าย(ซึ่งรับประกันต่อ cliques ไม่ฟอร์ม)อย่างชัดเจน วิธีนี้เครื่องชั่งไม่เป็น มีหมายเลขหรือกระบวนการ ระดับกราฟเป็นเส้นตรง และจำนวนของแลกเปลี่ยนข้อความเป็นกำลังสอง ในทางปฏิบัติ ที่ชั่ง การส่งผลให้กราฟใหญ่ระดับในแอพลิเคชันที่ยกเลิกเนื่องจากสุด ๆ ทรัพยากร (มากเกินไปเปิดช่องพร้อมกัน หน่วยความจำไม่เพียงพอสำหรับข้อความที่ไม่คาดคิด ฯลฯ) ดังนั้น หนึ่งต้องพิจารณาซ้อนมากกว่าtopolog

ผลลัพธ์ (ไทย) 2:

3.1 ยืดหยุ่น Asynchronous ออกอากาศ
การแจ้งเตือนการเพิกถอนจะต้องมีการแพร่กระจายไปยังกระบวนการมีชีวิตทั้งหมดใน Communicator ระบุแม้ในขณะที่ความล้มเหลวที่เกิดขึ้นใหม่ในช่วงการขยายพันธุ์ยกเลิก ดังนั้นจึงเป็นสาระสำคัญในการถ่ายทอดความน่าเชื่อถือ ในบรรดาสี่กำหนดคุณภาพของการถ่ายทอดความน่าเชื่อถือมักจะพิจารณาในวรรณคดี (สิ้นสุดความถูกต้อง, ความสมบูรณ์ของสัญญา) [19], สายพันธุ์ที่ไม่สม่ำเสมอของคุณสมบัติที่มีเพียงพอและเกณฑ์ความสมบูรณ์สามารถผ่อนคลายใน
บริบทของ ยกเลิกการอัลกอริทึม ก่อนที่ข้อตกลงและความถูกต้องคุณสมบัติให้มั่นใจว่า
ถ้ากระบวนการเป็นกระบอกเสียงที่มีค่า V ทุกขั้นตอนการส่งมอบ V ในกรณีเครื่องแบบข้อตกลงว่าทรัพย์สินขยายไปถึงกระบวนการล้มเหลว:. ถ้ากระบวนการล้มเหลวได้ส่งค่าแล้ว
ก็จะต้องส่งมอบ กระบวนการที่ถูกต้องทั้งหมด ในการดำเนินการเพิกถอนถ้าความล้มเหลวฆ่าริเริ่มเช่นเดียวกับทุกกระบวนการการแจ้งเตือนแล้วการแจ้งเตือนยกเลิกแน่นอน
หายไปและมีชีวิตรอดกระบวนการอาจไม่เคยได้รับการแจ้งเตือน อย่างไรก็ตามทั้งกระบวนการที่ถูกต้องไม่ได้คาดหวังข้อความจากชุดของกระบวนการที่ตายแล้วดังนั้นการดำเนินการที่ไม่สามารถหยุดชะงักหรืออย่างน้อยก็เป็นกระบวนการที่ถูกต้องโดยตรงพยายามที่จะแลกเปลี่ยนข้อความด้วยกระบวนการที่ตายแล้วและจะตรวจสอบความล้มเหลวซึ่งหมายความว่าการปิดกั้นการดำเนินงานของ จะแล้วเสร็จในข้อผิดพลาดและปล่อยให้โอกาสในการประยุกต์ใช้ในการชำระเงินใหม่การดำเนินการเพิกถอน ในทุกกรณีการออกอากาศที่เชื่อถือได้ไม่สม่ำเสมอจะเพียงพอที่จะให้แน่ใจว่าการหยุดชะงักการดำเนินงานฟรี นี้มีความสำคัญในทางปฏิบัติเพราะการถ่ายทอดความน่าเชื่อถือเคารพทรัพย์สินเครื่องแบบข้อตกลงกำหนดว่าระบบที่เป็นอิสระของความล้มเหลวส่งละเลย (นั่นคือส่งได้เสร็จสิ้น แต่รับไม่ได้รับข้อความ) [19] ใน MPI เมื่อการดำเนินการส่ง
เสร็จก็ไม่ได้หมายความว่ารับได้ส่งข้อความ; ข้อความอาจจะยังบัฟเฟอร์เกี่ยวกับกระบวนการส่งและเมื่อกระบวนการที่เป็นเหยื่อของความล้มเหลวผิดพลาดก็อาจจะช่วยได้พร้อมกันกระทำความล้มเหลวส่งละเลย เพื่อให้มั่นใจว่าเครือข่ายที่เป็นอิสระของความล้มเหลวส่งละเลยต้องมีการรับรู้ของข้อความที่ส่งหรือรอบที่เพิ่มขึ้นของการแลกเปลี่ยนข้อความก่อนที่จะส่งออกอากาศที่เชื่อถือได้ ในฐานะที่เป็นเพิกถอนสามารถนำมาใช้กับ
การออกอากาศที่เชื่อถือได้ไม่ใช่สม่ำเสมอยอมรับว่าค่าใช้จ่ายเพิ่มเติมเป็น spared.Second คุณสมบัติสมบูรณ์ระบุว่ามีการส่งข้อความเพียงครั้งเดียวที่มากที่สุดและรูปแบบที่มีการสั่งซื้อเพิ่มเติม
คุณสมบัติที่มีอยู่เช่น FIFO หรือสั่งซื้อสาเหตุระหว่าง การจัดส่งของการออกอากาศที่แตกต่างกัน ในกรณีที่มีการแจ้งเตือนเพิกถอนข้อความเพิกถอนแรกที่ไปถึงกระบวนการที่ได้
ผลกระทบจากการเปลี่ยนแปลง immutably สถานะของ Communicator ที่ การส่งมอบเสริมของข้อความยกเลิกสำหรับ Communicator เดียวกันไม่มีผล ในทำนองเดียวกันถ้าริเริ่มหลายออกอากาศยกเลิกการแจ้งเตือนเกี่ยวกับการสื่อสารที่เดียวกันลำดับที่แจ้งเตือนเหล่านี้จะถูกส่งมีความสำคัญไม่เป็นผลสุดท้ายก็มักจะสลับไปเป็นรัฐเพิกถอนไม่เปลี่ยนรูป ดังนั้นเราจึงสามารถเก็บรักษาที่ไม่ได้มีคำสั่งให้สมบูรณ์ออกอากาศเชื่อถือได้ผ่อนคลายในการที่เราช่วยให้การส่งมอบหลายออกจากการสั่งซื้อ แต่ยังคงสมมติฐานที่เหมาะสมที่ยกเลิกข้อความไม่ปรากฏออกมาจาก "อากาศบาง" แล้วตราบใดที่อัลกอริทึม
ยังช่วยให้ไม่สม่ำเสมอคุณสมบัติข้อตกลงมีโอกาสสำหรับมุมมองที่ไม่สอดคล้องกันไม่มี ความต้องการที่เรียบง่ายเหล่านี้มีความสำคัญสำหรับการลดค่าใช้จ่ายของการดำเนินการเพิกถอนการเป็นขนาดของข้อความและจำนวนของการแลกเปลี่ยนข้อความรอบจะเพิ่มขึ้นอย่างเห็นได้ชัดเมื่อหนึ่งต้องการที่จะดำเนินการสั่งการออกอากาศที่เชื่อถือได้สม่ำเสมอ ได้รับข้อตกลงนอกเครื่องแบบที่ไม่มีการสั่งซื้อและความซื่อสัตย์หลวมคุณสมบัติในการถ่ายทอดความน่าเชื่อถือเพิกถอนกระบวนการที่ได้รับข้อความยกเลิกเป็นครั้งแรกสามารถดำเนินการรอบเดียวของการปล่อยก๊าซให้กับทุกประเทศเพื่อนบ้านที่มีขนาดของข้อความอย่างต่อเนื่องและ แล้วส่งการแจ้งเตือนยกเลิกทันทีโดยไม่ต้องตรวจสอบต่อไป สิ่งสำคัญสุดท้ายคือโครงสร้างของ overlaynetwork ที่ใช้ในการดำเนินการออกอากาศ ใน
ขั้นตอนวิธีการออกอากาศที่เชื่อถือได้เมื่อกระบวนการที่ได้รับ
ข้อความออกอากาศเป็นครั้งแรกทันทีที่ออกอากาศข้อความเดียวกันทุกประเทศเพื่อนบ้านในกราฟซ้อนทับ คุณสมบัติข้อตกลงสามารถรับประกันเฉพาะ
เมื่อความล้มเหลวอย่าถอดกราฟซ้อนทับ ในช่วงต้น
รุ่นต้นแบบของการดำเนินงาน ulfm ที่น่าเชื่อถือ
ขั้นตอนออกอากาศลูกจ้างเครือข่ายเชื่อมต่ออย่างเต็มที่
(ซึ่งรับประกันได้ว่าผู้คนเชื่อมต่อไม่เคยรูปแบบ).
เห็นได้ชัดว่าวิธีการนี้เครื่องชั่งน้ำหนักได้ไม่ดีเท่าที่มีจำนวน
หรือกระบวนการการศึกษาระดับปริญญากราฟเป็นเส้นตรงและ จำนวน
ข้อความแลกเปลี่ยนเป็นกำลังสอง ในทางปฏิบัติในระดับที่
ศึกษาระดับปริญญากราฟขนาดใหญ่ส่งผลให้ในใบสมัครยกเลิกเนื่องจาก
ทรัพยากรอ่อนเพลีย (เปิดช่องทางมากเกินไปพร้อมกันหน่วยความจำไม่พอสำหรับข้อความที่ไม่คาดคิด ฯลฯ .). ดังนั้นหนึ่งต้องพิจารณาการซ้อนทับที่ปรับขนาดได้มากขึ้น
topolog