This dissertation studies communication schemes for fast and secure retrieval and consensus of distributed information. First of all, a novel capacity achieving scheme for the private information retrieval is proposed. Private information retrieval is a communication scheme that aims to retrieve a desired information without disclosing the identity of the desired information. Differentiated from the traditional capacity achieving scheme for the private information retrieval, the proposed scheme is based on stochastic and asymptotic approach. Compared to the conventional scheme, the proposed scheme offers less complex solution of designing answering strings that ensures privacy and achieves the capacity at the same time. In addition, fundamental limits of private information retrieval aided with coded side information are discovered. Specifically, the cost for retrieving the desired information is examined by the normalized download cost, which counts the number of bit downloaded for a single desired bit with securing the privacy. The achievability of the fundamental limits are also shown via stochastic and asymptotic approach as done for the private information retrieval without side information. Next, a fast and scalable distributed consensus protocols are studied in the perspective of wireless communication. The traditional consensus protocols were usually ill-suited for the network that is composed of many users. In this context, this paper proposes a fast consensus protocol based on a co-design of communication and consensus process. Its feasibility and effectiveness is shown both analytically and numerically, Moreover, its applicability is underpinned by the study on of the fast consensus protocol applied dynamic spectrum access technique called `Consensus-Before-Talk'.
본 논문은 분산 정보의 사적 검색 및 합의를 위한 통신 기법을 연구한다. 사적 정보 검색은 사용자가 검색하는 정보가 어떤 것인지 데이터베이스에 노출하지 않고 정보를 검색하는 방법이다. 본 논문에서는 기존에 알려진 방식과는 다른 확률적, 점근적 접근을 통해 새로운 사적 정보 검색 최대 용량 달성 기법을 제안한다. 또한, 사용자가 부호화 부가 정보를 활용할 경우의 사적 정보 검색의 본질적인 한계를 탐구한다. 한편, 공간적으로 분산된 정보는 합의 및 공유 과정을 통해 보편적 정보가 될 수 있다. 일반적으로 이러한 과정은 사용자가 증가할수록 지연 시간이 길어지는데 이를 효과적으로 줄일 수 있는 통신 기법 또한 탐구한다. 특히, 지연 시간과 합의의 신뢰도 간의 절충 관계를 보이고 이를 바탕으로 통신과 합의 과정의 통합 설계 기준을 제시한다. 그뿐만 아니라 제안하는 기법의 응용하여 다수의 사용자를 서비스하는 임의 접속 기술을 또한 함께 탐구한다.
