[Quorum] Quorum 소개

맹주현 (JuHyun Maeng)

센서 네트워크 환경에서 센서 노드의 저전력 구현은 매우 중요한 이슈 중 하나입니다. 그래서 Quorum을 이용하여서 노드의 저 전력을 구현할 수 있는 방안을 도출하는 것을 목표로 합니다. 이번 게시글은 Quorum의 개요(Overview)에 대한 글로써, 대략적인 설명을 다룹니다. 이후 Quorum을 노드의 저 전력 구현에 이용한 논문들을 검토하고, 이를 정리하여서 설명할 것입니다.

Quorum 개요

1. Quorum 정의

두 집합에 대한 교집합의 원소가 1개 이상 존재한다는 것을 의미한다．

임의의 두 집합을 가지고 교집합을 만들면 공집합이 되지 않는 것을 말한다．

2. Quorum 시스템 정의

집합들의 모임을 의미한다．

분산 시스템에서 프로세서 사이의 조정을 통하여 일관된 작업의 처리를 제공하는 시스템을 말한다．

3. Quorum 시스템 예시

｛１，２，３｝， ｛１，４，５｝， ｛２，５，７｝은 Quorum 시스템이다．

• ｛1,2,3｝∩｛1,4,5｝=｛1｝, ｛1,2,3｝∩｛2,5,7｝=｛2｝, ｛1,4,5｝∩｛2,5,7｝=｛5｝
• 이처럼 두 집합으로 교집합을 만들면 공집합이 되지 않기 때문에 Quorum 시스템이라고 말할 수 있다．

｛１，２，３｝， ｛１，４，５｝， ｛２，６，７｝은 Quorum 시스템이 아니다．

• ｛1,2,3｝∩｛1,4,5｝=｛1｝, ｛1,2,3｝∩｛2,６,7｝=｛2｝, ｛1,4,5｝∩｛2,６,7｝=∅
• 이처럼 두 집합으로 교집합을 만들면 공집합이기 때문에 Quorum 시스템이 아니라고 말할 수 있다．

Quorum 시스템

1. Grid Quorum 시스템

이 시스템은 전체 원소 n개를 정사각형 모양의 ２차원 평면 상에 줄지어서 위치시켜 구성한다．

시스템을 구성하기 위하여 각 집합은 행과 열을 각각 하나씩 선택한다．

일정한 규칙에 따라서 임의로 선택한 두 집합 사이에 겹치는 부분（공통 원소）은 최소 ２개 이상 존재한다．

아래 그림은 Grid Quorum 시스템의 예시이다.

• 각 집합 A와 B는 행과 열을 각각 하나씩 선택하여서 시스템을 구성한다.
• 전체 １００개의 원소 중에서 집합 A, 집합 B 각각은 １９개의 원소를 선택한다.
• 두 집합 A와 B 사이에 겹치는 부분（공통 원소）은 최소 ２개 이상 존재한다는 것을 확인할 수 있다.

Grid Quorum 시스템 예시

아래 그림은 Grid Quorum 시스템의 또 다른 예시이다.

• Transmitter와 Receiver 사이의 통신을 Jammer가 방해하는 환경 구성이다.
• 각 구성 요소가 선택한 행과 열에 따른 집합 중 두 집합으로 교집합을 만들면 공집합이 되지 않기 때문에 Quorum 시스템이 된다．
• 이때, 세 집합 사이의 공통원소는 6이며, 이 6은 해당 환경에서는 같은 주파수 대역이라는 의미를 나타내고 있다.
• 결국, 구성 요소 모두의 주파수 대역이 같기 때문에 Transmitter와 Receiver 사이의 통신을 Jammer가 방해할 수 있게 된다는 것을 확인 할 수 있다.

Grid Quorum 시스템 예시

2. Torus Quorum 시스템

이 시스템은 전체 원소 n개를 가로가 세로 보다 ２배 더 긴 직사각형 모양의 ２차원 평면 상에 줄지어서 위치시켜 구성한다．

시스템을 구성하기 위하여 각 집합은 각각 한 열을 선택하고, 선택한 열부터 오른쪽으로 한 열씩 이동하면서 이동한 열 마다 임의의 행에서 한 원소를 선택한다．

선택한 열부터 오른쪽으로 이동할 때, 전체 가로 길이의 절반만큼 이동한다.

일정한 규칙에 따라서 임의로 선택한 두 집합 사이에 겹치는 부분（공통 원소）은 최소 １개 이상 존재한다．

아래 그림은 Torus Quorum 시스템의 예시이다.

• 각 집합 A와 B는 각각 한 열을 선택하고, 선택한 열부터 오른쪽으로 한 열씩 이동하면서 이동한 열 마다 임의의 행에서 한 원소를 선택한다．
• 선택한 열부터 오른쪽으로 ５칸만큼 이동한다．
• 전체 ５０개의 원소 중에서 집합 A, 집합 B 각각은 １０개의 원소를 선택한다.
• 두 집합 A와 B 사이에 겹치는 부분(공통 원소)은 최소 １개 이상 존재한다는 것을 확인할 수 있다.

Torus Quorum 시스템은 Grid Quorum 시스템보다 적은 원소를 선택하여도 공통 원소를 보장할 수 있다．

Torus Quorum 시스템 예시

3. Cyclic Quorum 시스템

이 시스템은 Difference set을 기반으로 하여서 구성한다．

아래는 Cyclic Quorum 시스템의 예시이다.

Difference set D를 구하는 과정 예시

• D={0,1,2,4}를 아래 수식에 따라서 구하면 Cyclic Quorum 시스템 Q={{0,1,2,4}, {1,2,3,5}, {2,3,4,6}, {3,4,5,7}, {4,5,6,8}, {5,6,7,1}, {6,7,1,3}, {7,1,2,4}}를 얻을 수 있다.

Cyclic Quorum 시스템 Q를 구하는 수식

Quorum 응용

1. 환경 구성

적진의 동태를 살피거나 침입자를 탐지하는 등의 상황을 고려한다．

Quorum 시스템 Q={…}와 셀 C={…}로 구성한다．

공유키는 셀에 선 분배한다．

통신하려는 두 센서 노드는 키 공유를 통하여 서로를 인증한 후, 암호화된 데이터를 서로 간 송·수신한다．

2. 목표

각 센서 노드가 가지고 있어야 하는 키의 양을 최소화 하면서, 동시에 노드 사이의 연결성과 각 노드의 보안성을 보장한다.

3. 예시

아래 그림은 Quorum 기반의 키 분배 기법에 대한 예시이다.

• Q={A,B,C,…,P}이고, C={1,2,3,…,9}이다.
• 구성한 Quorum 시스템의 교차지점에 센서 노드가 분포된 셀들을 줄지어서 위치시킨다.
• 각각의 셀은 ４개의 Quorum 시스템과 만난다．
• １번 셀의 센서 노드는 ４개의 Quorum 시스템（A,B,E,F）에서 키를 선택한다．
• ２번 셀의 센서 노드는 ４개의 Quorum 시스템（B,C,F,G）에서 키를 선택한다．
• 각각의 셀들은 이웃한 셀과는 적어도 같은 Quorum 시스템을 １개 이상 공유한다．
• 각 센서 노드는 이웃 노드와 키의 공유를 보장받을 수 있다．

Quorum 기반의 키 분배 기법 예시

Edit by

맹주현
한양대학교 컴퓨터·소프트웨어학과 박사과정
maengjuhyun@gmail.com
관심 분야 : Blockchain, Network

참고 문헌

• 센서 네트워크에서의 쿼럼 시스템을 이용한 키 사전 분배， 한국정보과학회， ２００６
• IoT에서 중요한 데이터를 위한 쿼럼 기반 적응적 전파 알고리즘의 설계 및 평가， 한국멀티미디어학회， ２０１９

그림 출처

• Grid Quorum 시스템 예시
  센서 네트워크에서의 쿼럼 시스템을 이용한 키 사전 분배
• Grid Quorum 시스템 예시
  Game-theoretic Quorum-based Frequency Hopping for Anti-jamming Rendezvous in DSA Networks
• Torus Quorum 시스템 예시
  센서 네트워크에서의 쿼럼 시스템을 이용한 키 사전 분배
• Cyclic Quorum 시스템 Q를 구하는 수식
  센서 네트워크에서의 쿼럼 시스템을 이용한 키 사전 분배
• Quorum 기반의 키 분배 기법 예시
  센서 네트워크에서의 쿼럼 시스템을 이용한 키 사전 분배