정보처리학회 논문지 컴퓨터 및 통신시스템
Current Result Document :
| 한글제목(Korean Title) |
협상 해법을 이용한 이더리움 샤드 부하 균형 알고리즘 |
| 영문제목(English Title) |
Adaptive Load Balancing Algorithm of Ethereum Shard Using Bargaining Solution |
| 저자(Author) |
백동환
김승욱
Baek Dong Hwan
Kim Sung Wook
|
| 원문수록처(Citation) |
VOL 10 NO. 04 PP. 0093 ~ 0100 (2021. 04) |
한글내용
(Korean Abstract) |
블록체인의 확장성 문제를 해결하기 위한 이더리움 샤드 시스템은 부하 균형 문제가 존재하며 이는 그래프 분할 문제로 모델링된다. 본 논문에서는 게임 이론의 협상 해법을 사용하여 이더리움 샤드 시스템의 상반된 효용에 대한 협상이 가능한 적응적 온라인 가중그래프 분할 알고리즘을 제안한다. 게임 이론의 협상 해법은 상반된 효용의 협상점을 공정하게 결정할 수 있는 공리적 해법이다. 제안 알고리즘은 기존 온라인 그래프 분할 알고리즘을 가중그래프에 적용할 수 있도록 개선하였으며 대표적인 교섭 해법인 내쉬 협상 해법을 확장한 확장 내쉬 협상 해법을 사용하여 이더리움 시스템 상황을 고려한 설계를 통해 효과적으로 부하 균형을 수행하였다. 실험 결과, 대표적인 온라인, 오프라인 그래프 분할 알고리즘에 비해 최대 37% 우수한 성능을 보였다
|
영문내용
(English Abstract) |
The Ethereum shard system for solving the scalability problem of the blockchain has a load balancing issue, which is modeled as a graph partitioning problem. In this paper, we propose an adaptive online weighted graph partitioning algorithm that can negotiate between two utility of the shard system using the game theory's bargaining solution. The bargaining solution is an axiomatic solution that can fairly determine the points of conflict of utility. The proposed algorithm was improved to apply the existing online graph partitioning algorithm to the weighted graph, and load balancing was performed efficiently through the design considering the situation of the sharding system 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.
|
| 키워드(Keyword) |
이더리움
블록체인
샤딩
협상 해법
게임 이론
그래프 분할
부하 균형
Ethereum
Blockchain
Sharding
Bargaining Solution
Game Theory
Graph Partitioning
Load Balancing
|
| 파일첨부 |
PDF 다운로드
|
