Almost Optimal Algorithms for Token Collision in Anonymous Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913473286373376 |
|---|---|
| author | Bai, Sirui Fu, Xinyu Wu, Xudong Yao, Penghui Zheng, Chaodong |
| author_facet | Bai, Sirui Fu, Xinyu Wu, Xudong Yao, Penghui Zheng, Chaodong |
| contents | In distributed systems, situations often arise where some nodes each holds a collection of tokens, and all nodes collectively need to determine whether all tokens are distinct. For example, if each token represents a logged-in user, the problem corresponds to checking whether there are duplicate logins. Similarly, if each token represents a data object or a timestamp, the problem corresponds to checking whether there are conflicting operations in distributed databases. In distributed computing theory, unique identifiers generation is also related to this problem: each node generates one token, which is its identifier, then a verification phase is needed to ensure all identifiers are unique.
In this paper, we formalize and initiate the study of token collision. In this problem, a collection of $k$ tokens, each represented by some length-$L$ bit string, are distributed to $n$ nodes of an anonymous CONGEST network in an arbitrary manner. The nodes need to determine whether there are tokens with an identical value. We present near optimal deterministic algorithms for the token collision problem with $\tilde{O}(D+k\cdot L/\log{n})$ round complexity, where $D$ denotes the network diameter. Besides high efficiency, the prior knowledge required by our algorithms is also limited. For completeness, we further present a near optimal randomized algorithm for token collision. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10519 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Almost Optimal Algorithms for Token Collision in Anonymous Networks Bai, Sirui Fu, Xinyu Wu, Xudong Yao, Penghui Zheng, Chaodong Distributed, Parallel, and Cluster Computing Data Structures and Algorithms In distributed systems, situations often arise where some nodes each holds a collection of tokens, and all nodes collectively need to determine whether all tokens are distinct. For example, if each token represents a logged-in user, the problem corresponds to checking whether there are duplicate logins. Similarly, if each token represents a data object or a timestamp, the problem corresponds to checking whether there are conflicting operations in distributed databases. In distributed computing theory, unique identifiers generation is also related to this problem: each node generates one token, which is its identifier, then a verification phase is needed to ensure all identifiers are unique. In this paper, we formalize and initiate the study of token collision. In this problem, a collection of $k$ tokens, each represented by some length-$L$ bit string, are distributed to $n$ nodes of an anonymous CONGEST network in an arbitrary manner. The nodes need to determine whether there are tokens with an identical value. We present near optimal deterministic algorithms for the token collision problem with $\tilde{O}(D+k\cdot L/\log{n})$ round complexity, where $D$ denotes the network diameter. Besides high efficiency, the prior knowledge required by our algorithms is also limited. For completeness, we further present a near optimal randomized algorithm for token collision. |
| title | Almost Optimal Algorithms for Token Collision in Anonymous Networks |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.10519 |