Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.09805 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912427175575552 |
|---|---|
| author | Hu, Xing Toueg, Sam |
| author_facet | Hu, Xing Toueg, Sam |
| contents | We define and show how to implement SWMR registers that provide properties of unforgeable digital signatures - without actually using such signatures - in systems with Byzantine processes. Intuitively, processes can use these registers to write values as if they are ``signed'', such that these ``signed values'' can be ``verified'' by any process and ``relayed'' to any process. All our register implementations are from SWMR registers, and they work in systems with $n > 3f$ processes, $f$ of which can be Byzantine. We show that these implementations are optimal in the number of Byzantine processes they can tolerate: more precisely, we prove that if $3 \le n \le 3f$, the registers that we propose cannot be implemented from SWMR registers without using signatures. The registers that we introduce in this paper can also be implemented without signatures in message-passing systems with $n > 3f$ processes, $f$ of which can be Byzantine: this is because SWMR registers can be implemented in such systems (Mostéfaoui, Petrolia, Raynal, and Jard 2017). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09805 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | You can lie but not deny: SWMR registers with signature properties in systems with Byzantine processes Hu, Xing Toueg, Sam Distributed, Parallel, and Cluster Computing We define and show how to implement SWMR registers that provide properties of unforgeable digital signatures - without actually using such signatures - in systems with Byzantine processes. Intuitively, processes can use these registers to write values as if they are ``signed'', such that these ``signed values'' can be ``verified'' by any process and ``relayed'' to any process. All our register implementations are from SWMR registers, and they work in systems with $n > 3f$ processes, $f$ of which can be Byzantine. We show that these implementations are optimal in the number of Byzantine processes they can tolerate: more precisely, we prove that if $3 \le n \le 3f$, the registers that we propose cannot be implemented from SWMR registers without using signatures. The registers that we introduce in this paper can also be implemented without signatures in message-passing systems with $n > 3f$ processes, $f$ of which can be Byzantine: this is because SWMR registers can be implemented in such systems (Mostéfaoui, Petrolia, Raynal, and Jard 2017). |
| title | You can lie but not deny: SWMR registers with signature properties in systems with Byzantine processes |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.09805 |