분산 k-서버 문제 - k-서버 알고리즘을 위한 경쟁적인 분산 변환기

저자들은 분산 환경에서 k-서버 문제를 고려합니다. n개의 프로세서와 k개의 동일한 이동 서버가 있는 네트워크가 주어질 때, 서비스 요청이 프로세서에 나타나고 서버는 요청 지점에 도달해야 합니다. k개의 동일한 이동 자원이 네트워크의 프로세서에 의해 공유되는 컴퓨터 네트워크의 문제를 모델링하는 것 외에도, 정보 전송이 비용이 많이 들고 서비스 요청을 충족하기 위해 이동하는 서버의 행동을 지배하는 중앙 제어가 없는 현실적인 상황을 모델링합니다. 문제는 서버의 이동뿐만 아니라 제어 메시지 전송에 발생하는 통신 비용을 최소화하는 알고리즘을 고안하는 것입니다. 주요 기여는 임의의 결정론적 글로벌 제어 경쟁 k-서버 알고리즘을 분산 경쟁 알고리즘으로 변환하는 일반 변환기를 제공하는 것입니다. 그 결과로 선, 트리 및 링에 대한 다항식(k)-경쟁 분산 알고리즘을 얻게 됩니다.