Communication-Efficient Sequence Reconciliation and Its Application

10.6285/MIC.202209_11(2).0023

Ching-Yuan Kung

Communication Complexity ； Computational Time ； Sequence Reconciliation ； Minimax Search Algorithm

管理資訊計算

11卷2期（2022 / 09 / 01）

298 - 304

英文

We consider the problem of reconciling two sequences of integers held by different hosts by taking the pairwise maximum values using nearly optimal communication complexity. We show that this problem can be reduced to the set reconciliation problem with little overhead, so the communication complexities of the two problems are alike. We implement the devised algorithm to see its practicability and find that if the number of different corresponding integers in the two sequences is large, the computation time of our algorithm dominates its communication time. To remedy this, we propose a randomization trick to reduce the computation time greatly while retaining the communication time unchanged.

1. Lipton, R. J.(1990).Efficient checking of computations.Annual Symposium on Theoretical Aspects of Computer Science
2. Marsland, T. A.,Campbell, M.(1982).Parallel search of strongly ordered game trees.ACM Computing Surveys (CSUR),14(4),533-551.
3. Minsky, Y.,Trachtenberg, A.,Zippel, R.(2003).Set reconciliation with nearly optimal communication complexity.IEEE Transactions on Information Theory,49(9),2213-2218.
4. Parthasarathy, S.(2012).Algologic Technical ReportAlgologic Technical Report,未出版
5. Schaeffer, J.(1989).The history heuristic and alphabeta search enhancements in practice.IEEE transactions on pattern analysis and machine intelligence,11(11),1203-1212.
6. Zippel, R.(1993).Effective polynomial computation.Springer Science & Business Media.