文章詳目資料
管理資訊計算
加入收藏
下載文章
| 篇名 | Communication-Efficient Sequence Reconciliation and Its Application |
|---|---|
| 卷期 | 11:2 |
| 作者 | Ching-Yuan Kung |
| 頁次 | 298-304 |
| 關鍵字 | Communication Complexity 、 Computational Time 、 Sequence Reconciliation 、 Minimax Search Algorithm |
| 出刊日期 | 202209 |
| DOI | 10.6285/MIC.202209_11(2).0023 |
中文摘要
英文摘要
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.