Comparison Tolerances and the Formal Majority Voter

7.1.5 Comparison Tolerances and the Formal Majority Voter


The formal majority voter

- variant results 간의 차이를 비교하기 위해 이 파라미터들(comparison tolerances-비교허용오차)을 사용한다.
- 그래서 때로는 tolerance voter나 inexact voting이라고 불리기도한다.

Comparison tolerances

- 실수(real number)를 비교할때 유용하다.
- voter의 많은 타입들에 향상되어 사용도 가능하다.

comparision tolerances의 사용을 설명하기 위해서 ε를  비교 허용오차 값이라 놓자.
voter는 variants results 두개를 한번에 계산한다.
예를 들어 만약 x, y, z가 variant results라면, voter는 이렇게 계산을 하게 된다.

| x - y | = δ1
| x - z | = δ2
| y - z | = δ3

이 계산의 결과가 주어지면서, voter는 variant results간의 차이를 특정 허용오차에 대해 확인한다.

δ1 ≤ ε
δ2 ≤ ε
δ3 ≤ ε

만약 모든 variant results가 허용오차 내에 있다면, agreement 이벤트가 존재하게 된다.
만약 하나 이상이 오차를 벗어나면, conflict 이벤트가 존재한다.

variants fail의 과반수보다 적을땐 no_failure event고,
variants fail의 과반수일땐 failure event가 된다.


comparison tolerances를 위한 voting event 타입은 아래와 같이 정의 되어있다.

ALL_CORRECT event : no_failure with agreement
FALSE_ALARM event : no_failure with conflict
UN_DETECTED_FAILURE event : failure with agreement
DETECTED_FAILURE event : failure with conflict

7.1.5.1 Operation


Adjudication functions은 그들의 기능들을 2단계로 수행하는 것들과 그렇지 않을 것들로 그룹화 할 수 있다.

2단계는 다음과 같다.

1.

몇몇의 기준에의해 틀렸다고 판단되는 variant outputs을 무시하고 Feasibility Set을 정의한다. 통상 기준은 AT나 FS에서 모든 요소들이 ε보다 작음으로써 차이가 나기 위한 필요성이다.

2.

그리고나서 FS내의 값들 중에서 r*을 고른다. 이 선택을 위해 가능한 기준/척도는 majority, median, average, or a random selection이 있다.

 

이러한 2단계의 효과는 ε의 선택에 좌우된다.

만약 ε가 너무 크면, FS는 옳지 않은 값을 포함하게 될 것이고, 그 중 하나가 r*로 판결이 날 것이다.

만약 ε가 너무 작으면, FS는 심지어 옳은 variant outputs이 있었음에도 불구하고 비어있게 될 것이다.

R을 variant results의 집합으로 놓자.
formal majority voter는 먼저 variant output인 x를 선택하고, FS를 x를 포함하여 x로부터 ε보다 작은 모든 R의 다른 값들을 이용해 R의 subset으로 만든다. 만약 FS내의 값들이 최소한 R의 값들의 과반수를 구성하면, r*은 FS에서 랜덤하게 선택된다.

Fig 7.13은 이 voter를 이용하기위한 result options를 보인다.
그 figure에서 n=3이고 는 비교의 기초로 선택되었다.

Fig7.13(a)에서 다른 variant results , A, B 둘 다 x의 ε내에 있다. 그래서 그것들과 x는 FS에 포함이 된다.
FS = { A, B, x }
따라서 판단된 결과는 이 FS내에서 무작위로 선택된다.

Fig7.13(b)는 x로부터 ε보다 큰 거리를 갖는 variant result,B를 보인다.
variant result, A는 x의 허용오차내에 있고, x와 함께 FS에 속해 있다.
FS = { A, x }
따라서 판단된 결과는 이 FS내에서 무작위로 선택된다.

Fig7.13(c)는 비슷하지만 A가 허용오차 밖에 있다.
FS = { B, x }
따라서 판단된 결과는 이 FS내에서 무작위로 선택된다.

Fig7.13(d)는 어떤 variant results도 허용오차 내에 없는 경우이다.
옳은 결과로 판단될 수 있는 결과가 없다. 따라서 예외가 발생한다.


Table 7.7은 formal majority voter를 보이고 있다.

Table 7.8은 신드롬 리스트와 formal majority voter를 사용한 결과를 제공하고 있다.
여기서 n=3이다.

이 테이블에서 사용한 표시들..

ri는 i번째 variant의 결과이다.
Ci = 1, 만약 ri가 옳은 결과 이면.
Ci = 0, 만약 ri가 틀리면.
FSi = 1, 만약 ri가 FSi안에 있으면.
FSi = 0, 만약 ri가 FSi안에 없으면.

 

변수 Status

Status 예.

Status = NIL

. voter가 아직 variant results를 시험하지 않았다.
. Status는 이값으로 초기화 된다.
. voter로 부터 돌아온 Status가 NIL이라면, adjudication중에 error가 발생했다.
. 되돌아 온 r*은 무시하라.

Status = NO CORRECT RESULT

. voter가 주어진 input variant results로부터 옳은 결과를 찾을 수 없었다.
. 되돌아 온 r*은 무시하라.

 

Status = SUCCESS

. voter가 processing을 마쳤고, r*을 찾았다.

Discussion 생략.