서로 다른 호스트 간에 동일한 데이터셋을 보유하도록 재정합(set reconciliation)하는 것은 수많은 분산 애플리케이션에서 중요한 선행 조건이다. 각 호스트가 보유한 데이터의 대부분이 서로 동일하다면, 집합 재정합을 달성하기 위해 전체 데이터셋을 전송하는 것은 비효율적이다. 각 호스트는 통신 복잡도를 최소화하기 위해 자신의 집합에만 독특하게 포함된 배타적 요소를 다른 호스트에게 보내야 한다. 본 논문은 ternary Bloom filter의 재귀적 비교를 이용하여 호스트가 자신의 배타적 요소를 식별하는 효율적인 알고리즘을 제안한다. ternary Bloom filter는 요소의 부분집합에 대한 서명을 나타내며, 동일한 요소를 포함한 부분집합을 걸러내는 데 사용된다. 따라서 배타적 요소를 포함한 부분집합이 식별되고, 해당 부분집합에 포함된 요소는 반전 가능 블룸 필터(invertible Bloom filter, IBF)에 프로그래밍되어 다른 호스트로 전송된다. 그 결과 IBF에 프로그래밍되는 요소의 수가 크게 감소한다. 시뮬레이션 결과는 동일한 데이터 통신량이라는 제약 하에서, 제안된 알고리즘이 기존 집합 재정합 알고리즘에 비해 우수한 성능을 제공함을 보여준다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.