The Beauty of Mathematics

Conveying the sheer wonder of mathematics to a six-year-old girl is no easy task. We can effortlessly compute in our heads the product of any number under 100 multiplied by 3, and we can offer up neat summaries like “multiplication is repeated addition” — but a six-year-old doesn’t grasp the mystery behind it. A couple of days ago, my wife — perhaps inspired by Sudoku — drew a ten-by-ten grid on a sheet of paper and showed Xiaobao the results of multiplying any number under 100 by 3, by 7, and by 11 (since division is the inverse of multiplication, you can also think of these as the numbers divisible by 3, 7, and 11). When the dry numbers transformed into shapes, and those shapes revealed statistically meaningful patterns, Xiaobao’s fondness for math was dramatically kindled, and she discovered many fascinating things in those patterns. So my wife asked me to build a simple app that would let Xiaobao better understand numbers and the operations behind them.

This is a grand undertaking — so I began with multiplication and division that Xiaobao could understand. After finishing the code, I ran it on a handful of numbers at random, and I could scarcely believe my eyes — these simple operations produce such beautiful distributions:

Note the units digits 9, 8, 7 … 3, 2, 1 and the tens digits 1, 2, 3, 4, 5 …

Units digits 1, 2, 3, 4, …, tens digits alternating by row: 2, 4, 6 … and 1, 3, 5 …

Again the units digits 9, 8, 7 … 3, 2, 1 and the tens digits 1, 2, 3, 4, 5 …, even more orderly

Both units and tens digits increase by one; past the hundreds, the units digits go 1, 2, 3, 4, 5, …, and the tens digits go 2, 3, 4, 5, … — tidy and beautiful

Reading diagonally to the right, the tens digits increase by one, skipping one every three; reading diagonally to the left, the units digits follow the same 9, 8, 7, 6, 5, … pattern

Units digits 9, 8, 7, 6, …, tens digits repeated twice, alternating 1, 3, 5, 7, 9 and 0, 2, 4, 6, 8

These patterns were discovered bit by bit as Xiaobao and I played. Most of the credit goes to her — I merely offered a bit of summary and the occasional nudge.

Of course, the point of this article isn’t these four arithmetic operations, which are far too simple for you. We are programmers. Mathematics has given us eyes that see across time and space; we will use them to probe the deepest mysteries of programs.

Idempotent

Idempotence is the weapon of choice for many a programmer’s swagger. When a fierce code review is raging, you elegantly exhale one last smoke ring, stub out your cigarette, clear your throat, and rasp: “Is this API idempotent?” It absolutely slaughters 99% of the plaid-shirt crowd on the spot. And if you can actually spell and pronounce idempotent correctly, you can pretty much ascend to godhood — and never worry about finding a girlfriend again.

So what exactly is idempotence?

Idempotent is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. - wikipedia

In plain terms: idempotence means that when an operation is applied repeatedly to itself, the result still equals itself. Or, put humanly: f ∘ f = f. Transposed into the world of computing, this weakens to: a function f(x) can be called any number of times, and its side effects remain unchanged. Note that “unchanged” here doesn’t mean “no side effects” — for example, deleting a record with primary key k from a database, no matter how many times it’s called, has the same side effect: record k no longer exists. In this sense, a pure function with no side effects is necessarily idempotent, but an idempotent function is not necessarily pure.

The benefit of idempotence is (side-effect) determinism. HTTP GET / PUT / DELETE were designed to be idempotent because fetching, replacing, and deleting a resource leaves the resource’s state unchanged whether called once or many times. That way, callers can invoke them repeatedly (refresh the page) without worrying about triggering errors.

In a distributed world, idempotence is the diamond in the crown. We should — or rather must — design systems to be idempotent in order to cope with all kinds of uncertainty. For example, Guo Jing transfers 10 gold leaves to Huazheng over the internet. Huazheng may not have received them, or she may have received them but her reply to Brother Jing was lost on the network. In both cases Guo Jing needs to retransmit the transaction — yet the consequence of retransmission might be that although he only needed to send 10 gold leaves, he ends up sending 20, and he has to swallow his grief with a broken tooth. If we design it to be idempotent, we can attach a unique identifier to the transfer transaction, so that duplicate transfers are discarded, guaranteeing consistent side effects.

Let’s abstract this example a little. In a message-processing system, if we can process messages idempotently — that is, the side effects of receiving the same message (1, n) times remain unchanged — then many complex transactional problems dissolve, and we can also reduce the complexity of the message system. As we know, in a message system, delivery modes are at least once or at most once. Both are easy to implement, but achieving exactly once is nearly mission impossible.

This idempotent message-handling capability is common in network protocols, chiefly as anti-replay protection; in the Ethereum world, the transaction nonce serves exactly this purpose.

Commutative

Unlike idempotence, commutativity and the associativity we’ll discuss next are topics elementary school math already touches (though $f(x) = x * 1$, $g(x) = x / 1$, $h(x) = x + 0$ are obviously also in the idempotent camp, elementary school doesn’t introduce the concept of idempotence). Unless the occasion calls for it, showing off with these will only make you a laughingstock.

Commutativity says that given any x, y, for the operation “*”, if $x * y = y * x$, we consider the operation commutative. In human terms: we can change the order in which events are processed without affecting the final result. For my daughter, this (additive) commutativity is easy to grasp:

In the computing world, commutativity means we can shuffle the order of instructions (or messages) and execute out of order. In this universe ruled by the second law of thermodynamics, out-of-order execution is guaranteed to be more energy-efficient than sequential execution. In a message system, if messages must be processed strictly in the order they were sent, that means the receiving end needs a queue to store and sort the messages already received; the next message can’t be processed until the previous one is done. Such a system is relatively inefficient. If we can improve it so that messages can be processed in the order they arrive — that is, commutativity is satisfied — efficiency can improve by orders of magnitude.

Suppose we want to compute the sum of the numbers from one to one hundred transmitted from the other end of the network; they might arrive in this order:

2 7 3 8 1 9 6 5 4 …

If our algorithm doesn’t satisfy commutativity, it must spend O($nlogn$) to O($n^2$) time maintaining an ordered list, and O(n) space to maintain a queue of pending items (e.g., before receiving 1, sorting and holding 2 3 7 8). The system’s worst-case latency is $na + nb + n^2c$ (assuming a is the latency to transmit one element, b the time to perform one addition, and c the time to move and compare once within the list).

If commutativity holds, then on receiving 2 I can compute $0 + 2 = 2$; on receiving 7 I compute $2 + 7 = 9$; and so on. No time or space is spent maintaining a list, and the system latency is only $na + b$ (assuming a > b: during the time a spent waiting for the next element, the time b to accumulate the current element is already absorbed).

From the above, in a message system, if an algorithm can satisfy commutativity, it dramatically reduces system complexity and sharply shrinks system latency.

Associative

Associativity says that given any x, y, z, for the operation “*”, if $(x * y) * z = x * (y * z)$, then we say the operation is associative. In human terms: as long as the order of the elements participating in the computation stays the same, I can freely change the order of operations without affecting the final result. In elementary arithmetic, addition and multiplication of real numbers are associative, e.g., $(1 + 2) + 3 = 1 + (2 + 3)$.

Note that commutativity does not imply associativity. For example, define “*” as f(x, y) = $x^2 + y^2$. Then $f(f(x, y), z) = f(z, f(y, x))$, i.e., $(x^2 + y^2)^2 + z^2 = z^2 + (y^2 + x^2)^2$, which clearly satisfies commutativity; but:

$f(f(x, y), z) != f(f(x), f(y, z))$, i.e., $(x^2 + y^2)^2 + z^2 != x^2 + (y^2 + z^2)^2$. Clearly it does not satisfy associativity.

In the computing world, associativity means the order of computation can vary. In quicksort, for example, after partitioning, it doesn’t matter whether you recurse into the sub-array smaller than the pivot first or the one larger — so it is associative.

Reflecting further, we find that associativity means the local state during processing is not affected by the global state — it is independent of it. Hence associativity also implies concurrent processing: for a given list, if the algorithm processing it is associative, then we can compute sub-lists concurrently without affecting the final result. Put the other way around: every algorithm that can be divided and conquered — map/reduce, for instance — satisfies associativity.

Idempotence x Commutativity x Associativity

In a distributed network, message delivery is uncertain in two ways:

1. Messages may be lost. Loss is a nasty business, so we add retransmission, which introduces new uncertainty: messages may be duplicated. The receiver may receive them (1, n) times.
2. Messages may arrive out of order. Out-of-order means that the n nodes in the same network may each end up receiving sequences in mutually different and unpredictable orders.

Suppose two nodes (A, B) in a network receive three messages (x, y, z); what they see might be:

• A: xzzyzy
• B: yyzzxxxzy

If A and B are both certain to receive all the messages, and from these messages they can derive a consistent state S, then we say the system has consistency.

Generally, we can introduce some synchronization mechanism so that everyone sees messages in the same order — for example, database systems use leader election to choose a primary node, which determines the order; blockchains use hash power or voting weight through some consensus algorithm to select a primary node at a given moment, and all nodes accept the order determined by that primary node.

However, we can also introduce idempotence, commutativity, and associativity simultaneously into the data structure and the operations upon it. Then, from a mathematical standpoint, we can compute that the final states of A and B both converge on x * y * z.

Let’s set aside how to design the data structure and algorithm. If we achieve this effect, then it means every node in the network can independently derive a consistent state without any synchronization at all. The network itself will then run extremely efficiently and can satisfy Crash Fault Tolerance (CFT) without paying much of a price — and even, with some improvements, Byzantine Fault Tolerance (BFT).

If this interests you, another time we can talk about CRDT (Conflict-free Replicated Data Types), the data structure that realizes this ideal.

Welcome back to the world of mathematics!