.png){kind=icon}
.png){kind=icon}
Return
Contention-Aware Cooperation
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.OPODIS.2025.9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is crucial in fault-tolerant distributed computing. Considering nprocess asynchronous message-passing systems where some processes may be Byzantine, this paper introduces a novel cooperation abstraction, Contention-Aware Cooperation (CAC). While Reliable Broadcast is a one-to- n cooperation abstraction and Consensus is an n-to- n cooperation abstraction, CAC is a d-to- n cooperation abstraction where d (1 <= d <= n) varies with each run and remains unknown to the processes. Correct processes accept the same set of l pairs v, i ( v is the value proposed by p(i)) from the d proposer processes, where 1 <= l <= d and (as d) l remains unknown to the processes (except in specific cases). Those l values are accepted one at a time, potentially in different orders at each process. In addition, CAC provides each process with an imperfect oracle that provides insights into the values that they may accept in the future. Interestingly, the CAC abstraction is particularly efficient in favorable circumstances, when the oracle becomes accurate, which processes can detect. To illustrate its practical utility, the paper details two applications leveraging CAC: a fast consensus implementation optimized for low contention (named Cascading Consensus), and a novel naming problem that can be solved under full asynchrony. All algorithms presented require signatures.
Keywords:
Agreement
Asynchronous message-passing system
Byzantine processes
Conflict detection
Consensus
Cooperation abstraction
Distributed computing
Fault tolerance
Optimistically terminating consensus
Short-naming
Journal
2
IF:
0
Papers:
35
Citations:
0
View more organizations