| 英文摘要 |
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. |
本站僅提供期刊文獻檢索。
