Pith Number

pith:3YJDDNEG

pith:2025:3YJDDNEG6ZWUC43KSXOSOXVWV2

not attested not anchored not stored refs pending

Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs

Diana Ghinea, Joel Rybicki, Marc Fuchs, Zahra Parsaeian

A synchronous protocol achieves optimal resilience for approximate agreement on trees with round complexity O(log D(T)/log log D(T)).

arxiv:2502.05591 v5 · 2025-02-08 · cs.DC

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{3YJDDNEG6ZWUC43KSXOSOXVWV2}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We present a synchronous protocol with optimal resilience and round complexity O(log D(T)/log log D(T)), where D(T) denotes the diameter of the input space tree. Complementing this result, we extend impossibility results for real-valued AA to any graph G by proving a lower bound of Omega(log D(G)/log log D(G) + log (n+t)/t) rounds. Together, these results establish the asymptotic optimality of our protocol whenever t in Theta(n).

C2weakest assumption

The impossibility results for real-valued AA can be extended to arbitrary graphs G while preserving the convex hull and 1-close output requirements (abstract, paragraph on lower bound extension).

C3one line summary

Optimal round complexity and resilience approximate agreement on trees with matching lower bounds, extended to block graphs in synchronous and asynchronous models.

Receipt and verification

First computed	2026-07-03T00:16:49.438561Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

de1231b486f66d41736a95dd275eb6aea409d487525e22c2c1db8c878a6a640c

Aliases

arxiv: 2502.05591 · arxiv_version: 2502.05591v5 · doi: 10.48550/arxiv.2502.05591 · pith_short_12: 3YJDDNEG6ZWU · pith_short_16: 3YJDDNEG6ZWUC43K · pith_short_8: 3YJDDNEG

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/3YJDDNEG6ZWUC43KSXOSOXVWV2 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: de1231b486f66d41736a95dd275eb6aea409d487525e22c2c1db8c878a6a640c

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "d2eb9cdd7a0f79f5760caefdef560652ce6694ff7e9c8f913c00438d970e2770",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DC",
    "submitted_at": "2025-02-08T14:39:28Z",
    "title_canon_sha256": "f65b29df08f6cf4e9c71a5d1d207e44c2fe26aecf3afaff6d94d4b85ccce2377"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2502.05591",
    "kind": "arxiv",
    "version": 5
  }
}