Motivation
Splitting a large calculation among machines is useful only when the pieces can be recombined into the intended answer. An average of averages fails when pieces have different sizes. A retry counted twice changes the data even when every machine computes its local answer correctly. A floating-point sum may change when the partition tree changes. These are distinct problems, and increasing the worker count does not resolve them together.
We begin with an exact histogram reduction because its algebra is transparent. A fixed set of categories gives a bounded summary whose merge is componentwise addition. We then use that example to reason about dependencies, communication and load imbalance. Finally, we analyze floating-point summation, where the same tree that organizes computation also changes numerical error. The aim is a framework-neutral reference calculation with explicit contracts, rather than an endorsement of particular software or a benchmark of distributed hardware.
The MapReduce viewpoint means applying a map to independent input partitions and reducing the resulting summaries. It does not prescribe a product, an operating system or a fault-tolerance protocol. Our code runs the reference reduction locally. Its execution is serial; the dependency graph explains what a parallel implementation could execute concurrently under stated resource assumptions, but it does not measure the speed of a real distributed system. This boundary lets us discuss algebraic correctness separately from practical performance.
Definitions
Three kinds of object recur: the summary that is merged, the contract that says which summaries are merged, and the cost model in which parallel time is measured.
Definition 5.1.1
(Histogram summary and merge)
Let records have category labels in , where . The histogram of a finite multiset is , with coordinate equal to the number of occurrences of label . Merge is , and its identity is the zero vector.
Repeated values are allowed as distinct observations; repeated processing of one intended observation is a data-handling error unless duplication is part of the target.
Definition 5.1.2
(Exactly-once partition contract)
Partition identifiers label disjoint pieces of a fixed input version. The reducer's contract requires exactly one accepted summary for every expected identifier, and none for any other identifier. A deterministic merge tree additionally fixes which summaries meet at each internal node.
Identity correctness and arithmetic reproducibility are different properties: a perfectly repeatable tree can summarize a wrong collection of leaves.
Definition 5.1.3
(Work, span and list scheduling)
Work is total arithmetic performed across all workers. Span is the longest chain of dependent operations in a computation graph under unlimited available processors. In the scheduling model, a job has a positive processing cost on any one of identical workers, and list scheduling sends the next waiting job to a free worker without preemption.
Elapsed time on a finite system is at least both work divided by processor count and span, but may also include communication, input movement and waiting. Counts such as use a unit-cost arithmetic model; exact integers of arbitrarily large magnitude have growing bit costs. The scheduling model ignores network contention and changes in job speed caused by other jobs. A scheduling theorem under these assumptions is not a wall-clock guarantee for a system with shared input or overloaded links.
Theorem/proposition
Theorem 5.1.4
(Exact summaries and partition independence)
If are disjoint input partitions, then . Any binary merge tree with those leaves gives the same histogram in exact integer arithmetic. A worker can compute its histogram in work and summary storage, without retaining its records.
Theorem 5.1.5
(A list-scheduling bound that exposes skew)
Let and . List scheduling on identical workers has completion time
Every schedule has . The upper bound assumes jobs are immediately available and a worker never idles while a waiting job can run.
Proposition 5.1.6
(A floating-point tree-sum error bound)
Suppose each addition satisfies with , and there is no overflow or underflow invalidating this model. For a binary sum tree of height , if , its computed result obeys
A balanced tree for leaves has height ; a serial chain can have height . The bound is absolute and does not promise small relative error when the exact sum nearly cancels.
Proof sketch or proof idea
Proof
(Proof of partition independence)
For each category, its count in a disjoint union is the sum of its counts in the pieces. This proves the merge identity coordinate by coordinate. Induction over a tree then says every internal node summarizes precisely the union of its descendants. Associativity, commutativity and the zero identity permit regrouping, reordering and empty partitions. They do not permit omitting a leaf or accepting its retry as an additional leaf. The local map touches each of its records once and initializes counters, which gives the work and storage bounds.
Disjointness is the one hypothesis that the algebra cannot supply.
Counterexample mode
Overlapping pieces double-count
Claim: summing the histograms of any pieces that together cover the input gives its histogram. Take records with label and with label , so the true histogram is . A retry produces the pieces and , which cover the input but overlap. Their histograms are and , with sum : record is counted twice, although every worker counted its own piece correctly. The repaired statement requires a partition into disjoint pieces, which is exactly what the exactly-once contract enforces.
Proof
(Proof of the list-scheduling bound)
Inspect the job that finishes last, of cost . If it starts at time , it was waiting during , and under list scheduling no worker idles while a job waits, so all workers were busy throughout with other jobs. Hence . Therefore . Replacing by gives the bound. The lower bounds follow because all work must be done and the largest job cannot be divided under this model. Making other jobs tiny cannot make an indivisible large job disappear.
Proof
(Proof of the tree-sum bound)
Expand the computed tree from root to leaves. Each input is multiplied by the rounding factors along its path, at most factors. Their product differs from one by at most : an upper product is bounded by , while . Subtract the exact sum and use the triangle inequality. Paths shorter than can be padded by factors one. This is a proof for summation, not a general error theorem for every nonlinear summary merge.
The last proof turns a statement about a whole tree into a statement about individual leaves.
Proof X-ray
A tree has an algebraic meaning and a numerical height
The rounding model is used once per internal node: every computed addition is the exact sum of its two computed inputs times one factor with . The key move is to unfold the tree, so that the computed result becomes the sum of each input times the product of the factors on its own root-to-leaf path. Tree shape then enters only through path lengths, which is why height, not the number of leaves, controls the bound, and why exact associativity, which makes tree shape irrelevant to the mathematical histogram, plays no role here. The hypothesis keeps the bound on each product finite. The argument closes with the triangle inequality, and this is where it becomes an absolute bound in the sum of magnitudes. Fixing a tree fixes one source of numerical variation and balancing it limits path length, but neither proves that an ill-conditioned cancellation problem has a small relative error.
Worked examples
Worked example 5.1.7
(An executable map and balanced reduction)
This complete Python program constructs a tiny input, maps consecutive partitions to histograms, rejects repeated identifiers, verifies that none are missing, and reduces with a fixed binary tree. It uses lists to make the example inspectable; the local map itself needs only its count array and can consume a streaming iterator.
def map_counts(values, q):
counts = [0] * q
for value in values:
if not isinstance(value, int) or not 0 <= value < q:
raise ValueError("invalid category")
counts[value] += 1
return counts
def merge(a, b):
return [x + y for x, y in zip(a, b)]
def reduce_once(messages, expected_ids, q):
by_id = {}
for pid, summary in messages:
if pid not in expected_ids or pid in by_id:
raise ValueError("unexpected or repeated partition")
if len(summary) != q or any(not isinstance(x, int) or x < 0
for x in summary):
raise ValueError("invalid summary")
by_id[pid] = summary
if set(by_id) != set(expected_ids):
raise ValueError("missing partition")
level = [by_id[pid] for pid in sorted(expected_ids)]
if not level:
return [0] * q
while len(level) > 1:
level = [merge(level[i], level[i + 1])
if i + 1 < len(level) else level[i]
for i in range(0, len(level), 2)]
return level[0]
values = [(7 * i + 3) % 5 for i in range(37)]
blocks = [values[i:i + 7] for i in range(0, len(values), 7)]
messages = [(pid, map_counts(block, 5))
for pid, block in enumerate(blocks)]
answer = reduce_once(messages, set(range(len(blocks))), 5)
assert answer == map_counts(values, 5)
assert sum(answer) == 37
print(answer)
The result is [8, 7, 7, 8, 7]. The local reducer retains summary fields in this demonstration. A distributed tree moves summaries between levels instead; its architecture must still enforce the same identifier and input-version contract. Checks of shape and nonnegative counts alone cannot prove that a worker actually read the intended data.
Worked example 5.1.8
(The same work can finish at different times)
Consider three workers and jobs with costs eight and nine copies of one. Total work is seventeen. If the nine unit jobs come first, they occupy all workers for three time units; the final cost-eight job then finishes at time eleven. If the large job comes first, it occupies one worker while the other two finish the nine small jobs by time five. Completion is then eight, attaining the lower bound from the largest job.
The theorem gives , so it allows both outcomes and is attained by the first order. This small simulator reproduces the calculation without sleeping or measuring a machine:
import heapq
def completion(costs, workers):
free = [(0, worker) for worker in range(workers)]
heapq.heapify(free)
for cost in costs:
start, worker = heapq.heappop(free)
heapq.heappush(free, (start + cost, worker))
return max(time for time, worker in free)
assert completion([1] * 9 + [8], 3) == 11
assert completion([8] + [1] * 9, 3) == 8
Partitioning by equal record counts can still create unequal costs if some records need far more processing. Smaller jobs can improve load balance, but create more scheduling and communication overhead. A mathematical work bound does not select an optimal partition size without a cost model.
Worked example 5.1.9
(A deterministic floating sum can consistently lose one)
For stored binary64 values , a left-to-right sum rounds the first addition to and returns zero. Grouping the two large opposite numbers first returns one, the exact real sum. Thus a fixed tree can reliably repeat a less accurate answer. In Python, math.fsum([1e16, 1.0, -1e16]) also returns one using a more careful summation procedure. That example is an observed calculation, not a proof that every library's sum is exact.
For nonnegative inputs the sum condition number is one, so the tree bound also bounds relative error when the sum is positive. For mixed signs the ratio can be arbitrarily large. Reproducibility and conditioning should therefore be reported separately from worker counts.
Common mistakes
The merge operation must match its state. Concatenating summaries whose identifiers overlap, or applying a nonlinear postprocessing step before a justified merge, changes the problem. A reduction service also needs to know which input version its identifiers describe; a reused identifier with different contents is not the same partition.
Common mistake
(Averaging partition means without their counts)
The pieces and have means and , whose average is ; the mean of all four records is . A mean is not a mergeable summary on its own. The pair (count, sum), here and , merges by addition to and recovers the correct mean.
Concept lensStructural
Mergeable summaries are monoid homomorphisms
The first theorem says that turns disjoint union of multisets into vector addition and the empty input into : it is a homomorphism of commutative monoids, and that alone makes every merge tree correct. The mean admits no such merge rule at all, not merely a different one. The inputs and have the same mean , yet adding the piece gives means and ; no function of the two piece means can produce both. The pair (count, sum) is a homomorphism, and the mean is computed from it only at the end.
Communication has a mathematical size as well. Mapping records to dense histograms uses summary fields, but a very large category universe can make dense summaries expensive. Sparse summaries help when few categories occur locally, while a key occurring almost everywhere can still create a heavily loaded aggregation path. Tree depth, total bytes, message latency, worker memory and the largest partition are separate bottlenecks.
For example, suppose a message with fields takes time on an otherwise uncontended link, where is latency and is transfer time per field. A balanced tree has about sequential communication rounds, while a reducer receiving all messages through one serial bottleneck can spend order there. This is an explicit toy link model, not a prediction for every network. Batching reduces the number of latency payments, but enlarges messages and can delay the first available result. Splitting a heavy key among several local partial sums can distribute map work, yet those partial sums must still meet in a final reduction. The dependency has moved; it has not vanished.
Common mistake
(Treating a fixed tree as a portable bitwise guarantee)
A fixed tree yields bitwise repeatability only under controlled arithmetic choices. Changing precision, compiler transformations, local summation order or accepted leaves may change the result. The algebraic real-arithmetic answer remains well defined, but that statement is weaker than a portable bitwise guarantee.
Summary
Partition correctness is an exactly-once contract about disjoint input pieces. Exact merge algebra permits regrouping, while work and scheduling bounds describe different limits on parallel execution. Floating summation adds a path-dependent error that can be bounded by tree height under an explicit rounding model. Runnable local reference calculations make these distinctions checkable without pretending to measure a distributed system.
Exercises
Quick check
(For categories zero, one and two, map blocks and . Merge their summaries and explain why an empty block does not change the result.)
Count each label in each block.
Solution · Answer
The summaries are and , giving with total five. The empty histogram is , the additive identity. This follows from the count interpretation of every coordinate and does not depend on the grouping order.
Quick check
(On two workers, compare job orders and . Compute their completion times and the list-scheduling upper bound.)
Simulate both orders, then evaluate the bound with and .
Solution · Answer
The first two cost-three jobs finish at time three, after which the cost-ten job finishes at thirteen. In the second order, one worker handles ten while the other completes two cost-three jobs by six, so completion is ten. Total work is sixteen and the maximum job is ten. The upper bound is , attained by the first order.
Quick check
(For inputs , compute the sum condition number. Explain why a small absolute tree-sum bound need not imply small relative error.)
Compare with .
Solution · Answer
The exact sum is and the sum of magnitudes is . Their ratio is . Dividing the absolute estimate by the tiny exact sum multiplies by this large ratio. A short tree helps control rounding stages, but cannot remove the conditioning created by cancellation.
Quick check
(A reducer expects partition identifiers zero through three, but receives only zero, one and three. Suppose their reported record counts accidentally add to the expected total. Should it accept? What changes if identifier one appears twice instead?)
Check the exactly-once contract, not the totals.
Solution · Answer
It should reject because partition two is missing. A coincidentally correct count cannot establish that the intended records were processed. A repeated identifier one must also be rejected under the contract, rather than accepted as an additional independent leaf. Detecting those cases protects input identity; it does not replace validating the mathematical content of each summary.