협상 해법을 이용한 적응적 이더리움 샤드 부하균형 알고리즘
Adaptive Load Balancing Algorithm of Ethereum Shard using Bargaining Solution
- 주제(키워드) 게임이론 , 이더리움 , 협상해법 , 부하균형
- 발행기관 서강대학교 일반대학원
- 지도교수 김승욱
- 발행년도 2020
- 학위수여년월 2020. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- UCI I804:11029-000000065255
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
최근 몇 년간 블록체인은 탈중앙 시스템에서 신뢰를 기반으로 한 네트워크 시스템이라는 점에서 큰 인기를 얻었다. 하지만 성능 및 확장성 문제로 인해 실질적인 적용에 어려움을 겪었다. 이더리움 등의 블록체인은 분산 시스템의 확장성을 높이기 위해 샤딩을 이용한다. 상호운용성을 위해 각 샤드에서 발생하는 거래는 서로 다른 샤드에 의존적이며 이러한 시스템은 그래프로 표현된다. 이는 샤드 내의 계산부하 및 여러 샤드 간 발생하는 교차거래에 따른 부하에 관한 균형문제를 일으키며 그래프 분할 문제로 모델링된다. 본 논문에서는 다양한 그래프 분할 알고리즘을 비교하고 게임이론의 협상 해법을 사용하여 이더리움 샤드 시스템의 상반된 효용에 대한 협상이 가능한 적응적 온라인 가중그래프 분할 알고리즘을 제안한다. 게임이론의 협상 해법은 상반된 효용의 협상 점을 공정하게 결정할 수 있는 공리적 해법이다. 제안 알고리즘은 기존 온라인 그래프 분할 알고리즘을 가중그래프에 적용할 수 있도록 개선하였으며 대표적인 교섭 해법인 내쉬 협상 해법을 확장한 확장 내쉬 협상 해법을 사용하여 이더리움 시스템 상황을 고려한 설계를 통해 효과적으로 부하 균형을 수행하였다. 실험결과, 대표적인 온라인, 오프라인 그래프 분할 알고리즘에 비해 평균 37% 우수한 성능을 보였다.
more