Marzullo's algorithm
E234530
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Marzullo's algorithm canonical | 1 |
Statements (38)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
clock synchronization algorithm ⓘ |
| advantage |
provides robust time interval estimate
ⓘ
simple to implement ⓘ |
| appliedIn |
distributed clock services
ⓘ
fault-tolerant distributed systems ⓘ network time synchronization ⓘ |
| assumes |
each time source provides an interval estimate
ⓘ
some time sources may be faulty ⓘ |
| basedOn |
interval intersection
ⓘ
voting among intervals ⓘ |
| complexity | O(n log n) ⓘ |
| field |
computer science
ⓘ
distributed systems ⓘ time synchronization ⓘ |
| goal | find an interval consistent with the maximum number of sources ⓘ |
| handles |
possibly conflicting time sources
ⓘ
uncertainty in time measurements ⓘ |
| input | set of time intervals from different sources ⓘ |
| limitation |
assumes intervals correctly model uncertainty
ⓘ
requires bound on number of faulty sources ⓘ |
| origin | proposed by Keith Marzullo ⓘ |
| output | time interval with maximum support ⓘ |
| property |
selects interval with maximum overlap count
ⓘ
tolerates a bounded number of faulty sources ⓘ works with overlapping time intervals ⓘ |
| relatedTo |
Cristian's algorithm
ⓘ
Network Time Protocol ⓘ |
| representation | time as closed intervals ⓘ |
| step |
identifies region with highest overlap
ⓘ
scans endpoints while maintaining overlap count ⓘ sorts all interval endpoints ⓘ |
| use |
clock synchronization
ⓘ
combining multiple time interval estimates ⓘ fault-tolerant time estimation ⓘ selecting the most likely correct time interval ⓘ |
| usedFor |
building reliable time services over unreliable networks
ⓘ
estimating correct time in presence of faults ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.