عجفت الغور

algorithms

Tags: Computers

Sorting Algorithms

Marzullo’s Algorithm

  • Fault tolerant algorithm designed for use in distributed systems

  • Algo

    1. Collects interval estimates from all sources
    2. Sort and process intervals based on their start times, and then processes each interval in the sorted order
      • Each interval the algo tracks the number of overlapping intervals
    3. Determines the maximum overlap
      1. Finds the interval where the maximum overlap occurs, and the overlapping region is considered to be the most reliable estimate
    4. Fault tolerance: inherently tolerates faults
  • Uses

    • Clock syncronization
    • Sensor fusion
      • When multiple sensors measure the same physical quantity
    • Fault-tolerant systems
      • Provides resilable estimates from potentially faulty inputs