aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-12 21:59:02 +0000
committertv <tv@krebsco.de>2026-11-12 21:59:02 +0000
commit8daa8d67b2df3586efcfcae0f0e39b06fee1c5c8 (patch)
tree710e7ae950302d776e4ec9ef45cebc6acf04856d
parent6bb6f99d744c7ef9aa18af33e0784f3d2536cbd8 (diff)
federation: a limit on the writers a user's nodes start
A writer (an Automerge actor) costs every node heap in proportion to the document's history: about 4 bytes per change, a slot in each clock Automerge 0.12 caches. A document of 10^5 changes takes 42 MB with 10 writers and 435 MB with 1000 (measured with Automerge alone). Screening counts no actors, so a party starting a writer with every change adds gigabytes to every node. `limits.writers` (256 recommended) bounds what a user's nodes start in an epoch, judged as a change's history shows, and a federated node keeps its writer over a clean stop. Out of each other's sight such writers are valid and held: the nodes that made them are refused as peers, a party's budget bounds how fast they came, a remake leaves them out. Not promised: a bound on what an epoch's document costs.
-rw-r--r--docs/federation.md82
1 files changed, 52 insertions, 30 deletions
diff --git a/docs/federation.md b/docs/federation.md
index ea13273..37714e8 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -146,6 +146,11 @@ What is not promised:
* **Time across a remake.** A length of time that had begun when a remake came
starts anew after it. What became gone, final or dropped after a remake's base
stays so where the nodes of a third of the voters carried it over (Remakes).
+* **A bound on what an epoch's document costs.** What is valid as written every node
+ holds until a remake: statements past a limit, and writers started out of each
+ other's sight, each of which costs memory in proportion to the history. A limit
+ bounds how many in sight, and a party's budget how fast; who did it shows, under
+ its nodes' signatures.
* **A swarm that never splits.** A node that forks its own actor (two changes with one
number) splits the honest nodes that took one from those that took the other, until
one side drops its own (Partitions). It is found, proven and named; it isn't
@@ -207,6 +212,7 @@ value:
| `limits.users` | 16 | users a user created that stand; a root: no limit |
| `limits.vouches`, `limits.bans` | 64 | vouches, and bans, of a user that stand |
| `limits.proposals` | 8 | proposals of a user that are open |
+| `limits.writers` | 256 | writers a user's nodes start in an epoch |
| `limits.name` | 255 | bytes of a name |
| `limits.entry` | 4096 | bytes of a node's member entry |
| a kind's `limit` | none | names of the kind a user holds by a claim |
@@ -285,6 +291,11 @@ grows. A statement is signed by one user and says one thing:
agrees. That node's changes witness for both, and it takes proposals up for both:
for the swarm, such a user is the party that carries for it. Nothing is signed in
its place.
+* **Writers.** A node writes as a writer (an Automerge actor), a fresh one each time
+ it starts, rejoins or drops *(docs)*. Every writer costs every node memory while
+ the epoch lasts, in proportion to the document's history: about 4 bytes per change
+ *(measured upstream)*. So a user's nodes start `limits.writers` in an epoch at
+ most, and a federated node keeps its writer over a clean stop.
* **Past a limit.** A user's statements of one kind are counted from the first: each
has, and states, the number after the highest of those it was signed in sight of,
and of two with one number the one with the lower digest comes first. A statement is
@@ -1094,7 +1105,9 @@ A change is valid if, in the document at its dependencies:
2. Its committer is a node that carries for a user there, one that isn't out and
hasn't stopped there, proven by the node's signature. Or the change is the one by
which a node comes to carry: it holds a `node` statement naming its committer, by
- a user that isn't out there, the committer's member entry, and nothing else.
+ a user that isn't out there, the committer's member entry, and nothing else. A
+ change that starts a writer is refused where its user's nodes have started
+ `limits.writers` in its history.
3. Apart from the node's own member entry (of the shape the policy's version gives it,
within `limits.entry`) and its own records of proposals, it writes only envelopes,
each naming the swarm, its epoch, its path, its user and user ID, and for a
@@ -1613,18 +1626,18 @@ continuum, with a policy of its own, where it hasn't; either way a decision.
What changes in continuum besides the rules, under the federated policy only: policy
version 2; the envelope's payload names the user ID, the epoch, and for a statement
-what its signer saw; a node is given its root, syncs under no policy it doesn't
-know, takes tokens and logins by key as its operator says, writes no sessions into
-the document, stamps as often as the policy says, keeps its seeds and its user's
-other nodes as neighbours, keeps the document of an epoch it left on disk and
-answers for it, takes no remake but one its voters decided, rejoins no epoch because
-peers advertise it, and refuses what its bounds say. For every swarm: the wire's
-version, with a handshake that says which epochs its node keeps, and a node that
-speaks the wire version before its own too. [`trust.md`](trust.md),
-[`access.md`](access.md), [`remakes.md`](remakes.md) and the glossary get the
-federated case: party, statement, line, root, voter, claim, cut, late, contested,
-settled, final, out, gone, uncovered, seen for, taking a proposal up, a decision
-that holds, bounds, and a ban of a user beside a ban of a node.
+what its signer saw; a node is given its root, syncs under no policy it doesn't know,
+takes tokens and logins by key as its operator says, writes no sessions into the
+document, keeps its writer over a clean stop, stamps as often as the policy says,
+keeps its seeds and its user's other nodes as neighbours, keeps the document of an
+epoch it left on disk and answers for it, takes no remake but one its voters decided,
+rejoins no epoch because peers advertise it, and refuses what its bounds say. For
+every swarm: the wire's version, with a handshake that says which epochs its node
+keeps, and a node that speaks the wire version before its own too.
+[`trust.md`](trust.md), [`access.md`](access.md), [`remakes.md`](remakes.md) and the
+glossary get the federated case: party, statement, line, root, voter, claim, cut,
+late, contested, settled, final, out, gone, uncovered, seen for, taking a proposal up,
+a decision that holds, bounds, and a ban of a user beside a ban of a node.
## Continuum changing under a swarm
@@ -1829,20 +1842,21 @@ Nodes and syncing:
| 100 | Lies in its member entry (ready, reached, stable); publishes a short window there to make every node stamp hourly; writes an entry of any size | Sync and trees bend; nothing gets in that way. How often nodes stamp is the policy's; an entry has a shape and a size, or the change is refused | 6 | unit: `an_entry_has_a_shape`, `stamps_by_the_policy`; argued (Reaching the others) |
| 101 | Sends envelopes that don't check, without end | Refuse each (a signature costs about 30 µs to check *(docs)*); the node is refused as a whole after the first of its own | 6 | sim: `a_refused_node_costs_little` |
| 102 | Writes its own member entry without end; fills the waiting changes; sends changes that say they saw little, each to be judged far back | Take them no faster than a budget per party: put off, never refused; a share of the waiting each | 6 | sim: `a_party_past_its_budget_waits` |
-| 103 | Crafts a change Automerge won't take, or that writes in an object nowhere to be found | Refuse *(checked: the rules refuse the second today)*; only the message that brought it fails | 1 | unit: `a_change_writing_nowhere` |
-| 104 | Crafts a change Automerge takes and shouldn't: bytes it wouldn't encode itself, an actor named that nobody wrote as, operations numbered far ahead of its dependencies' or below them | Refuse before Automerge sees it: applied, such a change makes a node panic, or its document save to bytes that don't load | 1, 2 | unit: `only_what_automerge_writes` |
+| 103 | Starts a writer with every change: each costs every node memory in proportion to the document's history | Refuse past `limits.writers` a user, as the change's history shows. Out of each other's sight they are valid, and held: the user's nodes have then shown more than the limit, under their signatures, and are refused as peers; the party's budget, which counts a new writer for more than a change, bounds how many came first. A remake leaves them out | 6; not bounded out of sight | unit: `limits_on_writers`; sim: `writers_out_of_sight` |
+| 104 | Crafts a change Automerge won't take, or that writes in an object nowhere to be found | Refuse *(checked: the rules refuse the second today)*; only the message that brought it fails | 1 | unit: `a_change_writing_nowhere` |
+| 105 | Crafts a change Automerge takes and shouldn't: bytes it wouldn't encode itself, an actor named that nobody wrote as, operations numbered far ahead of its dependencies' or below them | Refuse before Automerge sees it: applied, such a change makes a node panic, or its document save to bytes that don't load | 1, 2 | unit: `only_what_automerge_writes` |
Rules, and the swarm as it is:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
-| 105 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` |
-| 106 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` |
-| 107 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` |
-| 108 | A root that lies and isn't left out; a user nobody unvouches | The parties ban it from a cut on and read on without it | not promised | unit: `a_ban_for_those_who_follow` |
-| 109 | A banned user's name claimed by one who bans it | The node refuses its own user's write: the others would | 1 | unit: `no_write_by_ones_bans_alone` |
-| 110 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` |
-| 111 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |
+| 106 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` |
+| 107 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` |
+| 108 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` |
+| 109 | A root that lies and isn't left out; a user nobody unvouches | The parties ban it from a cut on and read on without it | not promised | unit: `a_ban_for_those_who_follow` |
+| 110 | A banned user's name claimed by one who bans it | The node refuses its own user's write: the others would | 1 | unit: `no_write_by_ones_bans_alone` |
+| 111 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` |
+| 112 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |
## The registry on it
```
@@ -1899,7 +1913,7 @@ the network at large reads.
## Stages
Each leaves the system working, and is a few patches with its tests, which leave
-their vectors. At every stage the existing tests pass untouched (111).
+their vectors. At every stage the existing tests pass untouched (112).
1. **A federated swarm's frame.** `--genesis-policy` (a file, written into the genesis
change with the roots, the voters and the users it starts with); a federated node
@@ -1908,7 +1922,7 @@ their vectors. At every stage the existing tests pass untouched (111).
key as its operator says, keeps ended sessions to itself, stamps as the policy
says, and writes a member entry of the policy's shape and size. What the genesis
change sets for the swarm as a whole is read from the policy. Tests: 97 to 100,
- 104, 107, 111, and the policy's existing tests under a policy from the root.
+ 105, 108, 112, and the policy's existing tests under a policy from the root.
2. **Statements.** The users' registers (`create`, `key`, `node`, `vouch`, `release`);
the user ID, the epoch and what its signer saw in an envelope; nodes carrying for
users by their own word, and the rule for committers by it; nothing plain; the
@@ -1936,9 +1950,9 @@ their vectors. At every stage the existing tests pass untouched (111).
gone, nothing taken from an unvouched user's nodes, what comes back with a vouch.
Tests: 15, 17 to 24.
8. **Coming back.** The drop an operator asks for, a forked actor proven and shown
- with what the roots' nodes hold, the budget and the share per party. Tests: 94, 101
- to 103.
-9. **Bans** for those who follow. Tests: 108, 109.
+ with what the roots' nodes hold, the budget and the share per party, the limit on
+ writers, a node keeping its writer over a clean stop. Tests: 94, 101 to 104.
+9. **Bans** for those who follow. Tests: 109, 110.
10. **The registry.** Import, export, and a federated swarm of the simulations with
the registry's kinds and a few hundred hosts. From here it can be tried: users,
hosts, names, a root that settles, names that become final. It isn't to be relied
@@ -1950,10 +1964,10 @@ their vectors. At every stage the existing tests pass untouched (111).
`GET /registry/decisions`. What is decided: a number, a user's first keys, the
names of a user that is out, whose a contested name is, a name the rules leave to
the voters. The simulations start from a root change naming several voters, as a
- remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 110.
+ remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 111.
12. **Versions.** The digest with every stamp, a node checking itself before it
writes; for every swarm, a node that speaks the wire version before its own, and a
- handshake that says which epochs its node keeps. Tests: 105, 106.
+ handshake that says which epochs its node keeps. Tests: 106, 107.
13. **Remakes.** The proposal with who votes and who the roots are; the coordinator
and the base, taking a remake up by its result, the snapshot every node builds,
what it leaves out and what can't be written again; carrying over, by every node
@@ -1963,7 +1977,7 @@ their vectors. At every stage the existing tests pass untouched (111).
its operator gave, and by none that peers advertise. Tests: 55, 56, 75 to 87.
14. **The policy by a decision.** The policy as a matter, a node that doesn't know it,
what it no longer covers: shown aside, taken away by its user only, dropped after
- a time, moved at a remake. Tests: 73, 74, 107.
+ a time, moved at a remake. Tests: 73, 74, 108.
15. **Going apart, and refusing.** A fork followed by an operator's word, with who
votes and who the roots are on its side. Refusing a decision: a node's bounds, the
epoch without the decision, what a node takes along. Tests: 64, 88 to 92. From
@@ -1993,6 +2007,8 @@ Checked in the code:
least, which is daily by default (`swarm::members`). A renewal overwrites the
stamp, so two stamps of one node are two changes, found in the history; nothing
reads them so today.
+* Screening names a change's node by the change's author, or that of its actor's
+ first change, and counts no actors (`access::screen`). A limit on writers is new.
* A drop exists and does what coming back needs (`AppState::drop_taken`); what is new
is an operator asking for one its own rules wouldn't make.
* Neighbours are computed from the member list by key hashes (`swarm::topology`); a
@@ -2018,6 +2034,10 @@ Measured upstream, with Automerge 0.12.0 alone, on histories of small writes to
where the document doesn't hold that actor, applying panics. It applies a change
whose first operation is numbered below its dependencies', and the save doesn't
load; one numbered 2^32 − 1, and the node's next write panics.
+* Every writer costs heap in proportion to the history. A document of 10^5 changes
+ takes 42 MB with 10 writers, 79 MB with 100 and 435 MB with 1000, where the nodes
+ write in turn: a slot of 4 bytes per writer in every clock Automerge caches, which
+ there is one for most changes, and one for every 16th at best.
From the docs: a node under an unknown policy receives without judging; every node
takes a token any member signed, and lets in by key any user of the registry; where
@@ -2059,6 +2079,8 @@ Assumed, to be shown as it is built:
* The digest of the registry as it resolves is cheap enough to make with every stamp
at a registry's size, and to make at another node's stamp now and then.
* A version can speak the wire version before its own.
+* The writers a user's nodes started in a change's history are counted cheaply
+ enough: a count kept per user.
* The three things asked of a change before Automerge sees it keep out every change
it applies and shouldn't. Six such changes were tried; operations on objects that
don't exist, and others crafted, weren't.