algorithms
Tags: Computers
Sorting Algorithms
 pdqsort  https://github.com/orlp/pdqsort
Marzullo’s Algorithm

Fault tolerant algorithm designed for use in distributed systems

Algo
 Collects interval estimates from all sources
 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
 Determines the maximum overlap
 Finds the interval where the maximum overlap occurs, and the overlapping region is considered to be the most reliable estimate
 Fault tolerance: inherently tolerates faults

Uses
 Clock syncronization
 Sensor fusion
 When multiple sensors measure the same physical quantity
 Faulttolerant systems
 Provides resilable estimates from potentially faulty inputs
Links to this note
 adjacency lists
 algorithms for decision making
 algorithms for optimization
 approximate nearest neighbor
 binary decision diagrams
 broadcasting and multicast
 bully algorithm
 Consistent Hashing
 control theory
 graph based approximate nearest neighbor search (granne)
 graph traversal
 greedy search
 hierarchical navigable smallworld graph (HNSW)
 nearest neighbor
 paxos
 physalia  amazon ebs
 quantization/discretization
 reedsolomon encoding
 trees