협상 해법을 이용한 이더리움 샤드 부하 균형 알고리즘 (Adaptive Load Balancing Algorithm of Ethereum Shard Using Bargaining Solution)

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회논문지. 컴퓨터 및 통신시스템 / 10권 / 4호 / 93 ~ 100페이지
· 저자명 : 백동환, 김승욱

초록

블록체인의 확장성 문제를 해결하기 위한 이더리움 샤드 시스템은 부하 균형 문제가 존재하며 이는 그래프 분할 문제로 모델링된다. 본 논문에서는게임 이론의 협상 해법을 사용하여 이더리움 샤드 시스템의 상반된 효용에 대한 협상이 가능한 적응적 온라인 가중그래프 분할 알고리즘을 제안한다.
게임 이론의 협상 해법은 상반된 효용의 협상점을 공정하게 결정할 수 있는 공리적 해법이다. 제안 알고리즘은 기존 온라인 그래프 분할 알고리즘을 가중그래프에 적용할 수 있도록 개선하였으며 대표적인 교섭 해법인 내쉬 협상 해법을 확장한 확장 내쉬 협상 해법을 사용하여 이더리움 시스템 상황을 고려한설계를 통해 효과적으로 부하 균형을 수행하였다. 실험 결과, 대표적인 온라인, 오프라인 그래프 분할 알고리즘에 비해 최대 37% 우수한 성능을 보였다.

영어초록

The Ethereum shard system for solving the scalability problem of the blockchain has a load balancing issue, which is modeled as agraph partitioning problem. In this paper, we propose an adaptive online weighted graph partitioning algorithm that can negotiate betweentwo utility of the shard system using the game theory's bargaining solution. The bargaining solution is an axiomatic solution that canfairly determine the points of conflict of utility. The proposed algorithm was improved to apply the existing online graph partitioningalgorithm to the weighted graph, and load balancing was performed efficiently through the design considering the situation of the shardingsystem using the extension of Nash bargaining solution, which is extended to apply solution to non-convex feasible set of bargaining problem.
As a result of the experiment, it showed up to 37% better performance than typical load balancing algorithm of shard system.

참고자료

· 없음