อั ลกอริทึม Chang และ Roberts ^{[ 1 ]}เป็นอัลกอริทึมการเลือกผู้ประสานงานแบบวงแหวน ซึ่งใช้ในการคำนวณแบบกระจาย อัลกอริทึมนี้ได้รับการเผยแพร่ครั้งแรกโดยErnest ChangและRosemary Robertsในปี 1979

อัลกอริทึมนี้ตั้งสมมติฐานว่าแต่ละกระบวนการมีรหัสประจำตัวที่ไม่ซ้ำกัน (UID) และกระบวนการเหล่านั้นสามารถจัดเรียงตัวเองเป็นวงแหวนแบบทิศทางเดียวโดยมีช่องทางการสื่อสารจากแต่ละกระบวนการไปยังเพื่อนบ้านตามเข็มนาฬิกา อัลกอริทึมสองส่วนนี้สามารถอธิบายได้ดังนี้:

1. ในขั้นต้น กระบวนการแต่ละอย่างในวงแหวนจะถูกทำเครื่องหมายว่าไม่ได้มีส่วนร่วม
2. กระบวนการที่ตรวจพบว่าไม่มีผู้นำจะเริ่มการเลือกตั้ง โดยจะสร้างข้อความเลือกตั้งที่มี UID ของตนเอง จากนั้นจะส่งข้อความนี้ไปยังเพื่อนบ้านตามเข็มนาฬิกา
3. ทุกครั้งที่กระบวนการใดส่งหรือส่งต่อข้อความเกี่ยวกับการเลือกตั้งกระบวนการนั้นจะระบุตัวเองว่าเป็นผู้เข้าร่วมด้วย
4. เมื่อกระบวนการได้รับข้อความเกี่ยวกับการเลือกตั้ง กระบวนการ นั้นจะเปรียบเทียบ UID ในข้อความกับ UID ของตนเอง
   1. หากค่า UID ในข้อความเลือกตั้งมีขนาดใหญ่กว่า ระบบจะส่งต่อข้อความเลือกตั้งไปในทิศทางตามเข็มนาฬิกา โดยไม่มีเงื่อนไข
   2. หาก UID ในข้อความเลือกตั้งมีขนาดเล็กกว่า และกระบวนการนั้นยังไม่ได้เข้าร่วม กระบวนการนั้นจะแทนที่ UID ในข้อความด้วย UID ของตนเอง แล้วส่งข้อความเลือกตั้ง ที่อัปเดตแล้ว ในทิศทางตามเข็มนาฬิกา
   3. หาก UID ในข้อความเลือกตั้งมีขนาดเล็กกว่า และกระบวนการนั้นเป็นผู้เข้าร่วม อยู่แล้ว (กล่าวคือ กระบวนการนั้นได้ส่งข้อความเลือกตั้งที่มี UID อย่างน้อยเท่ากับ UID ของตนเองไปแล้ว) กระบวนการนั้นจะทิ้งข้อความเลือกตั้งนั้นไป
   4. หาก UID ในข้อความเลือกตั้งที่เข้ามาตรงกับ UID ของกระบวนการ กระบวนการนั้นจะเริ่มทำหน้าที่เป็นผู้นำ

เมื่อกระบวนการใดเริ่มทำหน้าที่เป็นผู้นำ กระบวนการนั้นจะเริ่มต้นขั้นตอนที่สองของอัลกอริทึม

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

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

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

เมื่อมีกระบวนการเดียวที่เริ่มต้นการเลือกตั้ง อัลกอริทึมจะต้องการข้อความเรียงลำดับ 3N-1 ข้อความ ในกรณีที่เลวร้ายที่สุด กรณีที่เลวร้ายที่สุดคือเมื่อกระบวนการที่เริ่มต้นการเลือกตั้งเป็นกระบวนการถัดจากกระบวนการที่มี UID มากที่สุด: จะต้องใช้ข้อความ N-1 ข้อความเพื่อให้ข้อความเลือกตั้งไปถึงกระบวนการนั้น จากนั้นต้องใช้ข้อความ N ข้อความเพื่อให้กระบวนการนั้นได้รับ UID ของตัวเองกลับคืนมา จากนั้นต้องใช้ข้อความอีก N ข้อความเพื่อส่งข้อความเลือกตั้งไปยังทุกกระบวนการในวงแหวน

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

• การประมวลผลแบบกระจาย
• การเลือกตั้งผู้นำ
• อัลกอริทึมบูลลี่
• อัลกอริทึม HS