교차로 알고리즘

교차로 알고리즘은 소음이 많은 여러 시간 소스로부터 정확한 시간을 추정하기 위한 선원을 선택하는 데 사용되는 합의 알고리즘이다.그것은 현대 네트워크 시간 프로토콜의 일부를 형성한다.마르줄로의 알고리즘을 변형한 형태다.^[1][2]

Marzullo의 알고리즘은 가장 많은 선원과 일치하는 가장 작은 구간을 반환하지만, 반환된 구간이 반드시 교차로에 있는 모든 선원의 중심점(계산된 오프셋)을 포함하지는 않는다.교차 알고리즘은 Marzullo의 알고리즘에 의해 반환된 간격을 포함하지만 중심점을 포함하므로 더 클 수 있다.이 큰 구간은 추가 통계 데이터를 사용하여 구간 내의 점을 선택할 수 있게 하여 반복 실행 시 지터를 감소시킨다.

방법

c ± r ([c-r,c+r]을 의미하는) 형식의 M 간격에 따라 알고리즘은 M-f 선원과 간격을 찾으려고 한다.값 f는 오류에 있는 출처(실제 값이 신뢰대 바깥에 있음)인 가성비자의 수라고 한다.가장 좋은 추정치는 가장 적은 위조범인 f를 가정하는 것이다.결과는 f < M/2일 경우 유효한 것으로 간주되며, 그렇지 않으면 알고리즘이 구간 대신 고장을 반환한다.

교차로 알고리즘은 튜플 <오프셋, 타입> 테이블을 만드는 것으로 시작한다.각 간격마다 하위 끝점, 중간점, 상위 끝점의 세 가지 항목이 있으며, 각각 -1, 0 및 +1 유형으로 라벨이 표시되어 있다.따라서 구간 c ± r은 항목 <c-r,-1>, <c,0>, <c+r,+1>이 된다.그런 다음 이러한 항목은 오프셋별로 정렬된다.

변수:이 알고리즘은 f를 false chickers, endcount, midcount가 정수인 것으로 사용한다.하한과 상한은 오프셋 값이다.

0. [최상의 f 초기화] 모든 입력 간격이 유효하다고 가정하여 f=0으로 시작한다.간격이 발견되지 않을 때마다 f는 간격이 발견되거나 f incre M/2가 될 때까지 증가된다.
1. [count=0] endcount=0과 midcount=0.
2. [하위 끝점 찾기] 목록 시작 시 시작(최저 오프셋) 각 튜플을 순서대로 고려한다.엔드카운트 = 엔드카운트 유형.엔드카운트 ≥ M-f이면 하위 엔드포인트가 발견되었기 때문에 하위 = 오프셋 및 3단계에 도달한다.유형이 0이면 중간 카운트 = 중간 카운트+1.다음 튜플을 사용하여 반복하십시오.목록의 끝에 도달하면 6단계로 이동하십시오.
3. [가칭 하부 끝점 발견, 상위 끝점을 찾기 위해 초기화] 설정 엔드카운트=0.
4. [중간점 수 결정] 목록 끝에서 시작하여 하위 오프셋을 향해 작업한다.Endcount = endcount+type.엔드카운트 ≤ M-f인 경우 상한 = 오프셋, 5단계.형식이 0이면 중간 카운트 = 중간 카운트+1.다음 튜플에 대해 반복하십시오.목록의 끝에 도달하면 6단계로 이동하십시오.
5. 상위 및 중간 카운트 ≤ f보다 낮은 경우, 신뢰 구간으로 [낮은 추세점, upperendpoint]를 반환한다.
6. [가성팬들의 수] f = f+1f ≥ M/2인 경우 종료 및 반환 실패, 1단계로 이동.

참조