Synchronization
การทำงานของระบบ Distributed ต้องมีการประสานงานของหน่วยทำงานเข้าด้วยกัน ดังนั้นเราต้องรู้ว่าหน่วยการทำงานไหนเกิดก่อนหรือเกิดหลัง เพื่อนำมาจัดลำดับเหตุการณ์โดยใช้ timestamp แบ่งออกได้เป็น physical, logical time
ในระบบต้องมีการควบคุมการใช้ทรัพยากรพร้อมๆกัน Distributed Mutual Exclusion

Physical clock
จะมีการเข้าไปเพิ่มค่าเวลาจากวงจรภายใน cpu ที่ memory ซึ่งเรียกว่า clock tick โดยอาศัยการทำงานจาก Quartz Crystal register และ interrupt ปัญหาก็คือ physical clock ในแต่ละเครื่องเดินไม่ตรงกันทำให้เวลาในแต่ละ process เรียงลำดับการเกิดได้ไม่ถูกต้อง ทำให้เราต้องทำการ synchonization ระหว่างเครื่อง
International Atomic Time ใช้การเปลี่ยนแปลงอะตอมของธาตุ cesium-133 แต่อย่างไรก็ตามต้องมีการชดเชยเวลาที่โลกหมุนช้าลง โดยเวลา atomic ที่ผ่านการชดเชย เรียกว่า UTC
ถือว่าเป็นเวลาที่เดินได้เที่ยงตรงที่สุดในโลก ในไทยก็ใช้ UTC+7
ในระบบเครือข่ายเราจะใช้ ntp ในการ sync

Christian’s Algorithm
client ส่ง req ไปหา time server (เริ่มต้นจับเวลา t0)
timeserver ส่งค่าเวลากลับมาด้วย replay message (หยุดเวลา t1)
เอา t1-t0 จะได้ช่วงเวลาในการเดินทางแบบ round trip time
สิ่งที่เราต้องการคือแค่ค่าเวลา reply กลับ ดังนั้นช่วงเวลาก็คือครึ่งหนึ่งของ RTT
เวลาที่ได้ก็คือ เวลาที่ reply + ครึ่งหนึ่งของ RTT
Berkeley Algorithm
ไม่มี Server แต่เป้าหมายคือตั้งเวลาของ servers ให้ตรงกัน โดยให้หาตัวแทนขึ้นมาหนึงตัวทำหน้าที่เป็น time daemon ตัว time daemon จะเป็นตัวเข้าไปร้องขอค่าเวลาจาก server สมาชิก แล้วนำค่าเวลาทั้งหมดมาหาค่าเฉลี่ย แล้วนำค่าเฉลี่ยนี้มาเป็นค่าอ้างอิงสำหรับแต่เละเครื่องต่อไป
Logical Clock
เราไม่ต้องการรู้เวลาจริงของเหตุการณ์เพียงแต่อยากรุ้ว่าเหตุการณ์ใดเกิดก่อนหลัง ไม่จำเป็นต้องอ้างอิงกับเวลาของโลกให้ยุ่งยาก
นั่นก็คือ Software counter ที่เพิ่มค่าขึ้นอย่างเดียวไม่มีลง (Logical Time) เพื่อนำไปเรียงลำดับเหตุการณ์

Lamport Timestamps
การเรียงลำดับของเหตุการณ์สามารถทำได้ง่ายถ้าอยู่ใน process เดียวกัน แต่หากว่าเป็นหลายๆ process เราจะใช้ทฤษฎี happens-before
a และ b อยู่ใน process เดียวกัน แล้ว a เกิดก่อน a -> b เป็นจริง
ถ้า a เป็น event ของ message แล้ว b เป็น event ที่ รับ message นั้น a->b เป็นจริง

มี transitive a->b b->c so a->c เราจะสามารถหาลำดับการเกิดได้

Election Algorithm
จะมี 1 process ที่ได้คัดเลือกให้เป็นตัวจัดการ โดยดูจาก ใครที่มี unique number มากที่สุดในเวลานั้นจะได้คัดเลือก (process number)

  • Bully Election Algorithm
  • แต่ละ process ในกลุ่มจะต้องรู้วิธีการติดต่อสื่อสารถึงแต่ละ process ได้โดยตรง และรู้ข้อมูลของแต่ละ process ว่าแต่ละ process มีหมายเลข process เบอร์อะไร โดยจะมี message 3 ชนิด
    election message ไว้หาตัวแทน
    answer message ไว้ตอบ election message
    coordinator message ไว้บอกว่าตัวเองได้เป็น coordinator

    เงื่อนไขการเป็น coordinator
    1. process ใดๆก็สามารถเริ่มต้นกระบวนการ election ได้โดยการส่ง election message ไปยัง processes ที่มีหมายเลขสูงกว่าตัวมัน แล้วรอ answer message ใดๆ ก็ได้ แปลว่าตัวที่ใหญ่กว่ายังทำงานอยู่ แสดงว่าตัวมันไม่สามารถเป็น coordinator ได้ แต่หากรอจน time out แล้ว answer message ยังไม่มา มันจะกลายเป็น coordinator
    2. process ใดๆเมื่อได้รับ election message ให้ตอบ answer message กลับไป และ process ที่ได้รับ election message ให้เริ่มกระบวนการ election message ด้วย โดยเข้าไปดูตารางสมาชิก หาสมาชิกที่มีหมายเลขสูงกว่า แล้วส่ง election message ไปหาสมาชิกเหล่านั้น แล้วรอ ถ้าหากไม่มี ตัวที่ใหญ่กว่า ตัวมันก็คือ coordinator
    หลังจากรู้แล้ว่า ตัวมันเป็น coordinator ให้ทำการส่ง coordinator message ออกไปยังหา process ที่มีหมายเลขน้อยกว่ามัน และให้สมาชิกจดจำว่าตัวใดเป็น coordinator ของกลุ่ม

  • Ring Election Algorithm
  • ติดต่อกันเป็นวงแหวน รู้จากซ้ายส่งต่อไปทางขวา ไปเรื่อยๆ
    มี election message กับ coordinator message
    การทำงาน
    process ใดๆ ส่ง election msg ออกไปในวงแหวนพร้อมกับหมายเลขของตัวเองลงไปด้วย
    เมื่อได้ process อื่นได้รับ election msg ตรวจสอบว่าตัวมันเองอยู่ใน list หรือไม่ ถ้ายังไม่ (ไม่ครบรอบ)
    ให้ใส่หมายเลขตัวเองต่อลงไป แล้วส่งต่อออกไปในวงแหวน จนเดินทางครบวงแหวน เมื่อพบหมายเลขตัวเองใน list ทำการตรวจสอบว่าหมายเลขตัวเองใหญ่สุดใน list หรือไม่ ถ้าใช่ตัวมันจะได้รับการคัดเลือกเป็น coordinator แล้วส่ง coordinator msg ออกไป ถ้าไม่ก็ส่งต่อไป
    Mutual Exclusion
    การควบคุมการทำงานของ processes ที่ใช้งาน Critical Region เดียวกัน ดังนั้น ณ เวลาใดก็ตาม มีไม่เกิน 1 process ที่ใช้งาน critical region นั้นๆ

  • Centralized Algorithm
  • มีตัวแทน 1 ตัว(coordinator) ทำหน้าที่เป็น central server โดยจะทำการสร้าง token ขึ้นมา 1 ตัว โดย 1 critical region จะมี token ได้เพียงตัวเดียว โดยใครที่ได้ token ไป คนนั้นสามารถเข้าไปใช้ critical region ได้
    process ต้องร้องของการใช้ critical region มายัง central server โดยจะทำหน้าที่จ่าย token ไปให้ แล้วจะทำการ reply กลับไป ถ้าหากมีการร้องขอมายัง central server อีก central server จะต้องไม่อนุญาติจนกว่าจะได้ token คืนมา

  • Distributed Algorithm
  • process เมื่อต้องการเข้าใช้ critical region จะต้องทำการส่ง msg ไปหาทุกสมาชิกในกลุ่มแล้วรอ reply กลับจาก ทุกสมาชิกในกลุ่ม ถึงจะเข้าใช้ critical region ได้ โดยส่ง timestamp ออกไปด้วย แล้วบันทึกว่าตัวมันเองส่งไปตอนไหน ให้ทำการเปรียบเทียบ timestamp ใครร้องขอก่อนจะได้รับ reply
    สมาชิกในกลุ่มเมื่อได้รับ request msg ก็ตรวจสอบว่าตัวมันเองใช้ critical region อยู่รึเปล่า ถ้าไม่ก็จะส่ง reply กลับ ถ้าใช้อยู่ก็ส่งกลับไป และถ้าตัวมันส่ง req msg ออกไปก่อนหน้านี้ แล้วเวลาที่ส่งไปน้อยกว่า เวลาของ msg ที่ได้รับ มันจะไม่ตอบ reply
    จะสังเกตได้ว่าไม่มีตัวไหน control สถานะ มีสิทธิเท่ากันทั้งหมด

  • Token Ring Algorithm
  • ใช้ token วิ่งวนไปเรื่อยๆ ถ้าใครใช้ก็เอาไป แล้วค่อยเข้าใช้ critical region ใช้เสร็จแล้วค่อยปล่อยคืน โดยจะมี token เดียวต่อ 1 region โดยจะเลือกตัวแทนเพื่อทำหน้าที่มา generate token