กลับไปหน้าบทความ

อ่าน 3 นาที

ไม่มีชื่อบทความ

อัลกอริทึมของมาเอคาวะ เป็นอัลกอริทึมสำหรับ การกีดกันซึ่งกันและกัน ใน ระบบกระจายศูนย์ พื้นฐานของอัลกอริทึมนี้คือ แนวทางที่คล้ายกับ โควรัม...

อัลกอริทึมของมาเอคาวะ

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

อัลกอริทึม

ศัพท์เฉพาะ

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

อัลกอริทึม

เว็บไซต์ที่ร้องขอ :

  • เว็บไซต์ที่ร้องขอพีฉัน{\displaystyle P_{i}}ส่งข้อความขอ(ที,ฉัน){\displaystyle {\text{request}}(ts,i)}ไปยังทุกไซต์ในกลุ่มองค์ประชุมอาร์ฉัน{\displaystyle R_{i}}.

สถานที่รับข้อมูล :

  • เมื่อได้รับขอ(ที,ฉัน){\displaystyle {\text{request}}(ts,i)}ข้อความ ไซต์ผู้รับพีเจ{\displaystyle P_{j}}จะ:
    • หากเว็บไซต์พีเจ{\displaystyle P_{j}}ไม่มีความโดดเด่นยินยอม{\displaystyle {\text{grant}}}ข้อความ (นั่นคือ ข้อความ)ยินยอม{\displaystyle {\text{grant}}}ข้อความที่ยังไม่ได้เผยแพร่) จากนั้นเว็บไซต์พีเจ{\displaystyle P_{j}}ส่งยินยอม(เจ){\displaystyle {\text{grant}}(j)}ส่งข้อความไปยังเว็บไซต์พีฉัน{\displaystyle P_{i}}.
    • หากเว็บไซต์พีเจ{\displaystyle P_{j}}มีผลงานที่โดดเด่นยินยอม{\displaystyle {\text{grant}}}ข้อความที่มีกระบวนการที่มีลำดับความสำคัญสูงกว่าคำขอ จากนั้นจึงส่งไปยังเว็บไซต์พีเจ{\displaystyle P_{j}}ส่งล้มเหลว(เจ){\displaystyle {\text{ล้มเหลว}}(j)}ส่งข้อความไปยังเว็บไซต์พีฉัน{\displaystyle P_{i}}และไซต์พีเจ{\displaystyle P_{j}}จัดคิวคำขอจากไซต์พีฉัน{\displaystyle P_{i}}.
    • หากเว็บไซต์พีเจ{\displaystyle P_{j}}มีผลงานที่โดดเด่นยินยอม{\displaystyle {\text{grant}}}ข้อความที่มีกระบวนการที่มีลำดับความสำคัญต่ำกว่าคำขอ จากนั้นจึงส่งไปยังไซต์พีเจ{\displaystyle P_{j}}ส่งสอบถาม(เจ){\displaystyle {\text{สอบถาม}}(j)}ข้อความถึงกระบวนการที่ได้รับอนุญาตให้เข้าถึงส่วนสำคัญโดยไซต์ในขณะนี้พีเจ{\displaystyle P_{j}}(นั่นคือ เว็บไซต์ที่มีความโดดเด่น)ยินยอม{\displaystyle {\text{grant}}}ข้อความ.)
  • เมื่อได้รับสอบถาม(เจ){\displaystyle {\text{สอบถาม}}(j)}ข้อความ เว็บไซต์พีเค{\displaystyle P_{k}}จะ:
    • ส่งผลผลิต(เค){\displaystyle {\text{ผลผลิต}}(k)}ส่งข้อความไปยังเว็บไซต์พีเจ{\displaystyle P_{j}}หากและเฉพาะในกรณีที่เว็บไซต์พีเค{\displaystyle P_{k}}ได้รับล้มเหลวล้มเหลวข้อความจากเว็บไซต์อื่น หรือหากพีเค{\displaystyle P_{k}}ได้ส่งผลผลิตไปยังเว็บไซต์อื่นแล้ว แต่ยังไม่ได้รับผลผลิตใหม่ยินยอม{\displaystyle {\text{grant}}}.
  • เมื่อได้รับผลผลิต(เค){\displaystyle {\text{ผลผลิต}}(k)}ข้อความ, เว็บไซต์พีเจ{\displaystyle P_{j}}จะ:
    • ส่งยินยอม(เจ){\displaystyle {\text{grant}}(j)}ส่งข้อความไปยังคำขอที่อยู่ด้านบนสุดของคิวคำขอของตนเอง โปรดทราบว่าคำขอที่อยู่ด้านบนสุดจะมีลำดับความสำคัญสูงสุด
    • สถานที่พีเค{\displaystyle P_{k}}เข้าสู่คิวคำขอ
  • เมื่อได้รับปล่อย(ฉัน){\displaystyle {\text{ปล่อย}}(i)}ข้อความ, เว็บไซต์พีเจ{\displaystyle P_{j}}จะ:
    • ลบพีฉัน{\displaystyle P_{i}}จากคิวคำขอของมัน
    • ส่งยินยอม(เจ){\displaystyle {\text{grant}}(j)}ส่งข้อความไปยังคำขอที่อยู่ลำดับต้นๆ ของคิวคำขอ

ส่วนวิเคราะห์ที่สำคัญ :

  • เว็บไซต์พีฉัน{\displaystyle P_{i}}เข้าสู่ส่วนที่สำคัญเมื่อได้รับยินยอม{\displaystyle {\text{grant}}}ข้อความจากทุกเว็บไซต์ในอาร์ฉัน{\displaystyle R_{i}}.
  • เมื่อออกจากส่วนที่สำคัญแล้วพีฉัน{\displaystyle P_{i}}ส่งปล่อย(ฉัน){\displaystyle {\text{ปล่อย}}(i)}ข้อความถึงทุกเว็บไซต์ในอาร์ฉัน{\displaystyle R_{i}}.

องค์ประชุมครบแล้ว (อาร์x{\displaystyle R_{x}}) : ชุดองค์ประชุมต้องมีคุณสมบัติดังต่อไปนี้:

  1. ฉันเจ[อาร์ฉันอาร์เจ]{\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}
  2. ฉัน[พีฉันอาร์ฉัน]{\displaystyle \forall i\,[P_{i}\in R_{i}]}
  3. ฉัน[|อาร์ฉัน|=เค]{\displaystyle \forall i\,[|R_{i}|=K]}
  4. เว็บไซต์พีฉัน{\displaystyle P_{i}}บรรจุอยู่ในอย่างแน่นอนเค{\displaystyle K}ชุดคำขอ
ดังนั้น:|อาร์ฉัน|เอ็น1{\displaystyle |R_{i}|\geq {\sqrt {N-1}}}

ผลงาน

  • จำนวนข้อความเครือข่าย;3เอ็น{\displaystyle 3{\sqrt {N}}}ถึง6เอ็น{\displaystyle 6{\sqrt {N}}}
  • ความล่าช้าในการซิงโครไนซ์: ความล่าช้าในการส่งต่อข้อความ 2 ครั้ง
  • อัลกอริทึมสามารถเกิดภาวะหยุดชะงักได้หากไม่มีการป้องกัน[ 1 ] [ 2 ]

ดูเพิ่มเติม

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

อัลกอริทึมของมาเอคาวะ เป็นอัลกอริทึมสำหรับ การกีดกันซึ่งกันและกัน ใน ระบบกระจายศูนย์ พื้นฐานของอัลกอริทึมนี้คือ แนวทางที่คล้ายกับ โควรัม...

ศัพท์เฉพาะ

ไซต์คือ อุปกรณ์คอมพิวเตอร์ใดๆ ที่ใช้งานอัลกอริทึมของมาเอคา วะ สำหรับการร้องขอใดๆ เพื่อเข้าสู่ ส่วนที่สำคัญ : เว็บไซต์ ที่ร้องขอ คือเว็บไซต์ที่ร้องขอให้เข้าสู่ส่วนสำคัญ ไซต์ ผู้รับ คือไซต์อื่นๆ ทุกแห่งที่รับคำขอจากไซต์ผู้ร้องขอ ts...

ผลงาน

จำนวนข้อความเครือข่าย; 3 เอ็น {\displaystyle 3{\sqrt {N}}} ถึง 6 เอ็น {\displaystyle 6{\sqrt {N}}} ความล่าช้าในการซิงโครไนซ์: ความล่าช้าในการส่งต่อข้อความ 2 ครั้ง อัลกอริทึมสามารถเกิดภาวะหยุดชะงักได้หากไม่มีการป้องกัน [ 1 ] [ 2 ]

ดูเพิ่มเติม

อัลกอริทึมเบเกอรี่ของแลมพอร์ต อัลกอริทึมการกีดกันร่วมกันแบบกระจายของแลมพอร์ท อัลกอริทึมริคาร์ต-อากราวาลา อัลกอริทึมของเรย์มอนด์