Two-way function computation

Abstract

본 논문에서는 양방향 컴퓨팅 시스템에서 인터렉션의 역할에 대해 살펴보았다. 가우시안 모델의 특징을 잘 나타내는 Avestimehr-Diggavi-Tse (ADT) 모델하에서 각 노드들은 다른 노드들로부터 오는 메세지들의 함수를 원하는 상황을 고려하였다. 한쪽 단에 위치한 두개의 노드들은 다른쪽 단에 위치한 두개의 노드들로부터 생성되는 메세지들의 modulo-2 sum 함수 계산을 원하는 상황이며, 메세지들을 생성했던 두 노드들 또한 다른쪽 단의 modulo-2 sum 함수를 계산하길 원하는 상황이다. 이러한 세팅하에서 인터렉션의 정도에 따라 세가지 시나리오를 고려하였다. 노드들간의 인터렉션이 없는 non-interactive scenario, 노드들간의 인터랙션이 제한적인 형태로 이루어지는 weak-interactive scenario, 그리고 노드들간의 인터렉션의 제한이 없는 strong-interactive scneario. 처음 두 시나리오에 대해서는 achievable scheme들과 matching upper bouds들을 보여 capacity region을 정립하였다. 이를 통해 우리는 컴퓨팅 상황에서 weak-interaction이 통신용량을 증대시킨다는 것을 알 수 있었다. 처음 두 시나리오를 바탕으로 우리는 인터렉션의 형태가 보다 일반적인 strong-interactive scenario로 상황을 확장하여 새로운 achievable rate region과 outer bound들을 보였다. 그 결과, 컴퓨팅 상황에서 마지막 시나리오를 고려하였을때인 인터렉션의 정도가 가장 강할때, 처음 두 시나리오하에서보다 통신용량이 증대되는 것을 보일 수 있었다.