Sparser Shuffles Suffice

doi:10.1145/3772290.3772310

Sparser Shuffles Suffice

2026-01-01

0

PRE

AI

DOI：10.1145/3772290.3772310

Original

Original request for help

Save

Abstract

En 中文

Peer-to-peer networks are typically defended against adversarial attack by maintaining small groups of peers, each with a good majority. Unfortunately, maintaining a good majority is challenging in the presence of churn. A popular defense against churn is periodic shuffling: replacing all peers in the group after a certain number of peer additions and deletions. Unfortunately, shuffling is expensive. Peer relocations degrade performance by requiring peers to: add and delete communication links; transfer content to maintain search correctness; and frequently update routing tables to avoid stale routing information. These problems are compounded by the fact that all current shuffling algorithms require shuffling even when the system is not under attack. Here, we present SPARSE-SHUFFLE, a shuffling defense that asymptotically matches adversarial cost. Given B adversarial insertions and deletions, our algorithm preserves good majorities in every group with only O(B) relocations of good peers. In particular, no shuffles occur in the absence of attack, and the shuffling cost grows linearly with the attacker's actions.

Keywords:

Peer-to-peer networks

Byzantine attacks

security

randomized algorithms

shuffling

Sparser Shuffles Suffice

Abstract

Journal

Organization