Contention-Aware Cooperation

doi:10.4230/LIPIcs.OPODIS.2025.9

Contention-Aware Cooperation

2026-01-01

0

PRE

AI

DOI：10.4230/LIPIcs.OPODIS.2025.9

原文链接

原文求助

摘要

En 中文

如可靠广播和共识所示，一组独立计算实体（顺序进程）之间的合作在容错分布式计算中至关重要。针对n进程异步消息传递系统（其中某些进程可能是拜占庭式的），本文引入了一种新的合作抽象，即“争用感知合作”（CAC）。尽管可靠广播是一对n的合作抽象，共识是n对n的合作抽象，但CAC是d对n的合作抽象，其中d（1 <= d <= n）随每次运行变化，且对进程保持未知。正确进程接受来自d个提议进程的相同l对v, i（v是p(i)提议的值），其中1 <= l <= d，且（如同d）l对进程保持未知（除特定情况外）。这些l个值被逐个接受，可能在每个进程上以不同顺序接受。此外，CAC为每个进程提供一个不完美的预言机，提供关于它们未来可能接受的值的见解。有趣的是，当预言机变得准确时，CAC抽象在有利条件下特别高效，进程可以检测到这一点。为说明其实用价值，本文详细介绍了两种利用CAC的应用：一种针对低争用优化的快速共识实现（命名为“级联共识”），以及一种可在完全异步下解决的新型命名问题。所有提出的算法都需要签名。

Keyword:

Agreement

Asynchronous message-passing system

Byzantine processes

Conflict detection

Consensus

Cooperation abstraction

Distributed computing

Fault tolerance

Optimistically terminating consensus

Short-naming

Contention-Aware Cooperation

摘要

期刊

机构

引用论文