Many Streams, One Global Answer
A nationwide service rarely observes one neat stream. Dublin, Cork, Galway, and edge devices each see local events, yet an analyst asks one global question: how many distinct users appeared, what was the latency distribution, or which items were frequent? Shipping every event to one machine is often too slow, expensive, or privacy-sensitive. A mergeable summary lets each partition compress its own data and lets a coordinator combine those summaries as though the data had been summarized together.
The familiar analogy is regional vote counting. Each station reports counts rather than every ballot. Addition is the merge operation: local counts can be combined in any grouping and still produce the same total. Sketches generalize this pattern to questions whose exact state may be too large. The summary may be approximate, but its meaning should not depend on whether events were split by region, worker, or day.
For a tiny exact example, streams $A=(a,b,a)$ and $B=(b,c)$ have frequency maps $\{a:2,b:1\}$ and $\{b:1,c:1\}$. Pointwise addition gives $\{a:2,b:2,c:1\}$, exactly the map for the concatenated stream. For a distinct-count sketch, the state is smaller and the answer approximate, but a valid merge must preserve the sketch’s estimator and error contract.
This raises the central questions: What algebraic law makes arbitrary aggregation trees safe? Does merging introduce fresh approximation error? Which metadata must match? Can duplicated, missing, or adversarial partitions invalidate the result even when the merge code is algebraically correct?
A mergeable sketch is a summary whose states can be combined into a valid summary of the union. Mergeability does not mean that every pair of byte-compatible states is semantically compatible: parameters, hash functions, units, windows, and population rules must agree.
| Concept | Intuitive meaning | Exact example | Non-example or boundary | Required assumption | Question answered |
|---|---|---|---|---|---|
| Local stream | Events assigned to one worker or domain | Events from one region in one hour | An overlapping copy counted as a new population | Assignment semantics are declared | What data did this node summarize? |
| Summary state | Compact information used by an estimator | Frequency map or fixed HyperLogLog registers | A dashboard number with no merge state | State retains information required by merge/query | What crosses the network? |
| Merge operation | Combine states for a union | Pointwise addition of frequency maps | Averaging two totals without weights | Inputs use compatible semantics | How are partial answers combined? |
| Monoid | State set with associative merge and identity | Integer counts under addition with identity zero | Subtraction with zero as a general merge | Closure, associativity, identity | Why may a tree regroup work safely? |
| Commutativity | Input order does not change state | Registerwise maximum | String concatenation | Merge represents an unordered union | May arrivals be reordered? |
| Partition invariance | Equivalent partitions yield equivalent estimates | Count totals independent of shard boundaries | Mean of unweighted shard means | Each event contributes once and merge is compatible | Does sharding change meaning? |
| Federated stream | Data remains under separate administrative control | Hospitals publish compatible summaries | Raw records silently centralized | Governance permits summary exchange | What can be learned without moving raw events? |
Many Streams, One Global Answer
Three workers observe item counts: $S_1=\{x:3,y:1\}$, $S_2=\{x:1,z:2\}$, and $S_3=\{y:4,z:1\}$.
- Merge $S_1$ and $S_2$ by pointwise addition: $\{x:4,y:1,z:2\}$.
- Merge $S_3$: the global state is $\{x:4,y:5,z:3\}$.
- Check the alternative grouping $S_1\oplus(S_2\oplus S_3)$; it gives the same result because addition is associative.
- The total event count is $4+5+3=12$ and the most frequent item is $y$.
- Now replace each state by its locally most frequent item. Those three labels cannot recover the global frequencies; locally useful output is not necessarily a mergeable state.
Reflection: which information was retained by the frequency maps but irreversibly discarded by the local-winner labels?
Merge Algebra and Partition Semantics
Let a stream segment be a finite multiset or sequence $X$, depending on the problem. A summarizer $\sigma$ maps $X$ to a state in $\mathcal S$, and a query map $q$ turns a state into an estimate. Exact mergeability asks for an operation $\oplus$ satisfying
$$ \sigma(X\uplus Y)=\sigma(X)\oplus\sigma(Y), $$
or an equivalent distributional/error guarantee when the sketch is randomized. The symbol $\uplus$ emphasizes multiset union: duplicate event identities remain duplicate contributions unless preprocessing defines deduplication.
Associativity, $(a\oplus b)\oplus c=a\oplus(b\oplus c)$, makes tree shape irrelevant. An identity $e$ with $a\oplus e=e\oplus a=a$ represents an empty partition. These laws make $(\mathcal S,\oplus,e)$ a monoid. Commutativity is additionally needed when partition order carries no meaning and workers may arrive in any order. It is not part of the monoid definition, and ordered sketches may deliberately omit it.
The strongest practical statement is not byte equality but semantic partition invariance: for every permitted partition of the same logical dataset, querying the merged compatible states has the promised relationship to querying a centralized state. Random seeds can make states differ while their distributions and guarantees agree.
Compatibility is part of the mathematical domain. Two states may merge only when sketch type, version, dimensions, hash family or seed policy, accuracy parameters, item encoding, weight semantics, window, units, and privacy treatment satisfy the construction’s preconditions.
flowchart TD
A[Define logical dataset and partition rule] --> B[Summarizer sigma and state space S]
B --> C[Closed merge operation]
C --> D[Associativity]
C --> E[Identity state]
D --> F[Monoid and arbitrary tree grouping]
E --> F
C --> G[Commutativity when order is irrelevant]
F --> H[Compatible metadata]
G --> H
H --> I[Partition-invariant semantics]
I --> J[Estimator and error guarantee]
H --> X[Reject incompatible states]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,C navy;
class D,E,F,G purple;
class H,I,J teal;
class X crimson;
| Definition or claim | Exact scope | Required assumptions | What it does not imply | Counterexample or consequence |
|---|---|---|---|---|
| Monoid state | $\oplus$ is closed and associative with identity $e$ | All operands belong to the same state domain | Merge is commutative or idempotent | String concatenation is a monoid but order matters |
| Commutative merge | $a\oplus b=b\oplus a$ | Dataset semantics ignore partition order | Duplicate delivery is harmless | Addition is commutative but counts a replay twice |
| Idempotent merge | $a\oplus a=a$ | Construction explicitly supports set-like replay behavior | Every union summary is idempotent | Count addition is not idempotent |
| Exact homomorphism | $\sigma(X\uplus Y)=\sigma(X)\oplus\sigma(Y)$ | Same summarizer and compatible parameters | Query is exact for the original problem | An exact mergeable sketch may still estimate cardinality |
| Distributional mergeability | Merged and centralized states have equivalent estimator guarantees | Randomness is coupled or analyzed as specified | State bytes or individual estimates match | Independent resampling may alter variance |
| Partition invariance | Repartitioning one logical dataset preserves target semantics | Each contribution follows the declared ownership rule | Faults cannot lose or duplicate data | At-least-once delivery biases additive summaries |
| Hierarchical aggregation | Any valid tree grouping preserves merge semantics | Associativity and compatible inputs | Every topology has equal latency or numerical stability | Floating-point roundoff may vary across trees |
The central invariant is that merging compatible summaries represents the same logical union regardless of tree grouping. Formally, the summary map is a homomorphism into an associative state algebra, while its estimator guarantee is interpreted under the construction’s stated randomness and compatibility domain.
Error Propagation Through Merge Trees
Two different mechanisms are often confused. A native merge combines fixed sketch states without recompressing them; for sketches such as registerwise maxima or linear sketches, tree depth need not create a new approximation factor. By contrast, a merge-and-reduce scheme unions summaries and then compresses them again. Each reduction may introduce error, so depth matters.
Suppose each reduction preserves every permitted query value within a multiplicative factor $1\pm\eta$. Along a root-to-leaf path with $L$ reductions, repeated application gives an upper factor $(1+\eta)^L$ and lower factor $(1-\eta)^L$. The step is valid because each intermediate summary lies in the domain of the next reduction guarantee. If the guarantee applies only to raw data, this induction is invalid.
For additive unbiased estimators from disjoint partitions, expectations add:
$$ \mathbb E\left[\sum_i \widehat T_i\right]=\sum_i \mathbb E[\widehat T_i]=\sum_i T_i. $$
If independent, their variances add too. Shared randomness or overlapping populations introduces covariance or double counting. Neither associativity nor unbiasedness alone supplies a high-probability global guarantee.
Communication is another dimension. A balanced tree with $p$ workers uses $p-1$ state transmissions and depth about $\lceil\log_2 p\rceil$; a centralized star has one hop per worker but concentrates ingress; gossip may tolerate churn yet sends repeated messages and requires duplicate-safe semantics or tracking.
flowchart TD
A[Declare logical union and compatible parameters] --> B{Native merge or recompression?}
B -->|Native| C[Use closure and associativity]
C --> D[Show merged state has centralized guarantee]
B -->|Recompress| E[State one-step guarantee]
E --> F[Verify summaries remain in its domain]
F --> G[Induct along each root-to-leaf path]
G --> H[Compose upper and lower factors]
D --> I[Add system fault analysis]
H --> I
I --> J[Global accuracy and communication claim]
F -->|Domain not closed| X[Proof fails]
A -->|Overlap or incompatible metadata| Y[Semantic claim fails]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,C,E navy;
class F,G,H purple;
class D,I,J teal;
class X,Y crimson;
Error Propagation Through Merge Trees
A balanced merge-reduce tree has $8$ leaves and therefore $L=3$ reductions on each path. Every reduction is guaranteed to preserve all permitted costs within $1\pm0.02$.
- Upper factor: $(1.02)^3=1.061208$.
- Lower factor: $(0.98)^3=0.941192$.
- A true cost of $10{,}000$ may therefore be represented between $9{,}411.92$ and $10{,}612.08$ under this simple worst-case composition.
- The global distortion is about $6\%$, not $2\%$. To target roughly $3\%$ over three levels, a first-order choice is $\eta\approx0.01$, followed by checking both exact products.
- If these are native merges of fixed registers rather than reductions, do not multiply error merely because there are three levels; prove that the merge reproduces the centralized sketch’s state law.
Assumption-breaking variation: let one internal reducer accept only raw, unweighted points, but feed it weighted summaries. The per-step theorem no longer applies, so the product calculation has no justified premise even though its arithmetic is correct.
| Analytical tool | What it establishes | Assumptions | Tightness or limitation | Representative failure case |
|---|---|---|---|---|
| Monoid induction | All tree parenthesizations yield the same merge state | Closure, associativity, identity | Says nothing about estimator accuracy | One worker uses a different register count |
| Homomorphism proof | Merged state represents union summary | Summary map respects union and merge | May be distributional rather than byte-exact | Different hash functions destroy alignment |
| Multiplicative composition | Bounds repeated reduction error by products | Each intermediate input satisfies the next theorem | Often pessimistic; depth-sensitive | Applying a raw-data theorem to weighted summaries |
| Linearity of expectation | Sum of local estimators is unbiased | Correct local targets and finite expectations | Gives no tail bound | Rare huge errors keep expectation correct |
| Variance addition | Quantifies precision of summed independent estimates | Independence or known covariance | Shared seeds require covariance terms | Correlated errors reinforce one another |
| Union bound | Controls probability any node fails | Valid per-node failure bounds | Can be loose for many nodes | Keeping local $\delta$ unchanged across millions of nodes |
| Communication analysis | Counts bytes, rounds, and bottlenecks | Explicit topology and state size | Accuracy and fault tolerance are separate | Gossip retransmission overwhelms a small sketch |
Regional Telemetry and Federated Analytics
In regional telemetry, workers can summarize request counts, latency distributions, distinct devices, or heavy hitters close to their sources. A centralized star is simple but creates a coordinator bottleneck. A balanced tree reduces fan-in and exposes logarithmic depth. Gossip is useful under churn but requires careful replay semantics because most additive sketches are not idempotent.
Federated analytics adds administrative boundaries. Hospitals, retailers, or devices may exchange summaries while retaining raw records. Mergeability reduces data movement, but it does not itself provide privacy: a small state can still leak rare membership or sensitive extremes. Differential privacy, secure aggregation, access control, and minimum cohort rules are additional mechanisms, each of which changes the estimator.
Three modeling traps matter. First, regions can overlap: a mobile user observed in two countries should not be blindly counted twice if the target is global unique users. Second, local thresholds can erase globally frequent items: an item just below every local cutoff can be large in aggregate. Third, incompatible windows or units can produce a perfectly lawful merge of states that answer no coherent real question.
Regional Telemetry and Federated Analytics: Distributed, Parallel & Mergeable Sketches
Three libraries count book loans by category during the same week:
- North: fiction $40$, science $20$, history $10$.
- Central: fiction $30$, science $35$, history $5$.
- South: fiction $25$, science $15$, history $20$.
Model selection: exact count vectors are small, associative, and preferable to an approximate sketch here.
- Add coordinates to obtain fiction $95$, science $70$, history $35$.
- Total loans are $200$; global shares are $47.5\%$, $35\%$, and $17.5\%$.
- Verify that merging North with Central first gives the same vector as merging Central with South first.
- A mean of the three local fiction shares would answer a different question because library totals differ. Weighted aggregation is required.
- Replay South once: the result becomes $(120,85,55)$, demonstrating that associativity does not provide exactly-once delivery.
Success criteria: reproduce all totals, explain why the exact monoid is the right model, and specify an event or batch identifier policy that detects the replay.
Regional Telemetry and Federated Analytics: Distributed, Parallel & Mergeable Sketches
A global observability platform serves $12{,}000$ tenants across $80$ regions, ingests $15$ million events per second, and must publish one-minute distinct-device counts, latency quantiles, and heavy hitters within $20$ seconds. Regional egress is capped at $5$ MB per minute, raw identifiers cannot cross some jurisdictions, workers use rolling upgrades, and delivery is at least once.
Theory-to-system design: use separate mergeable families for each objective; pin compatible versions and hash-seed epochs; align event-time windows; attach tenant, metric, unit, precision, and batch identity; validate at every boundary; aggregate through balanced regional trees; and keep exact control totals plus sampled raw-data audits where lawful. Do not infer that a quantile sketch, cardinality sketch, and heavy-hitter summary share the same merge theorem.
Risks: duplicated batches bias non-idempotent summaries; a seed mismatch corrupts cardinality registers; local heavy-hitter pruning hides globally frequent keys; late events cross window boundaries; Byzantine regions forge weights; privacy noise composed across repeated queries exceeds budget.
Evidence: centralized-versus-distributed replay tests, alternative partition and tree-shape tests, per-metric error distributions, duplicate and loss injection, mixed-version rejection, late-data correction, privacy accounting, regional slice accuracy, bytes and rounds, coordinator saturation, and audit logs proving provenance.
Decision: deploy only when compatible states reproduce centralized-contract accuracy across partitions, duplicate handling meets the delivery model, and privacy/security reviews cover the summary itself. Quarantine incompatible epochs rather than coercing them into a global state.
Design a Compatible Distributed Summary
A sound design begins by defining the logical dataset and answer, not by choosing a topology. State whether partitions are disjoint, how retries and late data behave, whether order matters, and what exact or probabilistic guarantee the centralized sketch already has. Then specify the state algebra, compatibility contract, aggregation pattern, and system fault model separately.
The expected artifact is a summary contract: target population, event identity, window, objective, state schema, merge law, identity, algebraic laws, randomness, estimator, error and failure probability, metadata compatibility, replay policy, privacy boundary, communication budget, numerical representation, version migration, validation evidence, and fallback behavior.
Practice: Design a Compatible Distributed Summary
Design a global distinct-user summary for four regions. During one aligned hour their exact audit sets are $A=\{1,2,3,4\}$, $B=\{3,4,5\}$, $C=\{6,7\}$, and $D=\{7,8,9\}$.
Tier 1 — Definitions. Define state, merge, identity, query, partition invariance, and compatibility. Explain why adding local distinct counts gives $12$ rather than the true global value $9$.
Tier 2 — Algebra. Use exact sets as the reference state. Show that union is associative, commutative, and idempotent with identity $\varnothing$. Trace both $(A\cup B)\cup(C\cup D)$ and $A\cup((B\cup C)\cup D)$.
Tier 3 — Sketch selection. Replace sets with a mergeable cardinality sketch. Specify common precision, hash/seed policy, item encoding, and registerwise merge. State whether tree depth adds new estimator error for native merges and justify the answer.
Tier 4 — Failure counterexamples. Analyze one replayed region, one region using another seed, a window shifted by five minutes, and the same person encoded differently. Separate algebraic, semantic, and system failures.
Tier 5 — Topology. Compare a star, balanced tree, and gossip plan for $1{,}024$ regions. Estimate tree depth, coordinator fan-in, number of state transmissions, and duplicate requirements.
Tier 6 — Professional contract. Produce a one-page specification covering population, windows, state/version, merge laws, error $\varepsilon$, failure probability $\delta$, seed rotation, privacy, provenance, retry identity, late data, communication limits, audits, and rejection behavior.
Debugging prompts: if estimates change with partitions, compare encoding and seeds; if totals jump after retries, inspect idempotency and batch identity; if old and new workers disagree, inspect version negotiation; if global heavy hitters disappear, inspect local pruning.
Stretch goal: design a compatibility lattice that permits safe precision downsampling without pretending it is lossless. Prove which direction of conversion is allowed and record the information discarded.
Rubric (10 points): model and vocabulary 2; algebraic proof 2; estimator/error reasoning 2; counterexamples 2; measurable operational contract 2. Full credit distinguishes sketch approximation from data loss, duplication, privacy noise, and floating-point effects.
Bridge: use distinct-count and quantile knowledge to compare native merge laws; use coreset knowledge to recognize merge-reduce recompression. The next step is fault-aware and privacy-preserving distributed streaming, where trustworthy aggregation requires more than mergeability.
Decision checklist: define population and ownership; prove the merge law; require compatible versions, randomness, units, and windows; distinguish native merge from recompression; budget accuracy, communication, privacy, loss, and replay separately; and test alternative partitions and tree shapes. A lawful merge cannot repair mismatched meaning, missing data, duplicate delivery, or an estimator used outside its theorem.
Next in the Series
In Communication Complexity & Streaming Lower Bounds, we'll explore Prove streaming space limits through communication reductions..