Exercises: networking#

Each problem comes from the exercise at the end of a gallery example. Try it in the example’s notebook first, then open the solution. Every solution is run by the documentation build, so its code is known to work.

2. Lamport clocks: making two events causal#

From Lamport clocks: ordering events without a shared clock (Lamport 1978). Add a message from P0 to P2 sent right after a and received before b.

Solution
>>> history = [
...     [("send", "m1"), ("local", "a"), ("send", "m4"), ("receive", "m3")],
...     [("receive", "m1"), ("send", "m2")],
...     [("receive", "m4"), ("local", "b"), ("receive", "m2"), ("send", "m3")],
... ]
>>> bk.network.lamport_timestamps(history)
((1, 2, 3, 8), (2, 3), (4, 5, 6, 7))
>>> vectors = bk.network.vector_timestamps(history)
>>> bk.network.happened_before(vectors[0][1], vectors[2][1])
True

b jumps from time 1 to 5, and the later events at P2 follow. Now a chain of events leads from a to b, so they are no longer concurrent. The receipt of m3 at P0 moves from 6 to 8, past the time at which P2 sent it.

3. Vector clocks: why no single number captures concurrency#

From Vector clocks: detecting concurrency (Fidge and Mattern 1988). Find events \(x, y, z\) with \(x\) concurrent to \(y\), \(y\) concurrent to \(z\), but \(x\) before \(z\).

Solution
>>> history = [
...     [("send", "m1"), ("local", "a"), ("receive", "m3")],
...     [("receive", "m1"), ("send", "m2")],
...     [("local", "b"), ("receive", "m2"), ("send", "m3")],
... ]
>>> v = bk.network.vector_timestamps(history)
>>> send_m1, a, b = v[0][0], v[0][1], v[2][0]
>>> bk.network.concurrent(send_m1, b), bk.network.concurrent(b, a)
(True, True)
>>> bk.network.happened_before(send_m1, a)
True

If “concurrent” meant “equal timestamps”, it would be transitive like equality, so sending m1 would be concurrent with a. It is not. And any other scalar encoding orders all events linearly, which loses the distinction. Exact concurrency needs as many counters as processes.

4. Rumor spreading: the ring#

From Rumor spreading in log2 n + ln n rounds (Frieze and Grimmett 1985, Pittel 1987). Run push on a ring instead of the complete graph. How do the rounds grow with \(n\)?

Solution
>>> rounds = {
...     n: sum(bk.network.spread_rumor(bk.network.ring_lattice(n, 2), seed=s).rounds
...            for s in range(5)) / 5
...     for n in (32, 64, 128)
... }
>>> 1.6 < rounds[64] / rounds[32] < 2.4 and 1.6 < rounds[128] / rounds[64] < 2.4
True

Doubling \(n\) roughly doubles the rounds: growth is linear, not logarithmic. On a ring the rumor can only advance one hop per round on each side, and an informed peer calls the uninformed neighbor only half the time, so it takes about \(n\) rounds. Fast gossip needs a graph with short paths, which random links provide.

5. Bracha broadcast: the echo quorum#

From Byzantine reliable broadcast: echo, then ready (Bracha 1987). Show that two echo quorums of size \(\lceil (n + t + 1)/2 \rceil\) share at least \(t + 1\) processes. What goes wrong with a simple majority?

Solution
>>> def overlap(quorum, n):
...     return 2 * quorum - n
>>> all(overlap(-(-(n + t + 1) // 2), n) >= t + 1
...     for n in range(4, 60) for t in range((n - 1) // 3 + 1))
True
>>> [(n, overlap(n // 2 + 1, n)) for n in (4, 7, 10)]
[(4, 2), (7, 1), (10, 2)]

Since \(2\lceil (n + t + 1)/2 \rceil \ge n + t + 1\), the overlap is at least \(t + 1\), so it contains a correct process, which echoes one value only. A majority quorum overlaps in one or two processes, which can all be faulty when \(t \ge 2\), so two values could both gather a quorum.

6. Random graphs: where the threshold comes from#

From Random graphs and the connectivity threshold (Erdős and Rényi 1959). Evaluate the expected number of isolated peers at \(p = c \ln n / n\), and derive the limit law.

Solution

The expected number of isolated peers is \(n(1-p)^{n-1} \approx n e^{-pn} = n^{1-c}\): it tends to infinity for \(c < 1\) and to 0 for \(c > 1\). If their number is roughly Poisson with that mean, the chance of none is \(\exp(-n^{1-c})\), and isolated peers are the last obstacle to connectivity.

>>> from math import exp, log
>>> n, c = 400, 1.2
>>> p = c * log(n) / n
>>> round(n * (1 - p) ** (n - 1), 3), round(n ** (1 - c), 3)
(0.288, 0.302)
>>> isolated = [
...     sum(d == 0 for d in bk.network.erdos_renyi(n, p, seed=s).degrees()) for s in range(60)
... ]
>>> abs(sum(isolated) / 60 - 0.3) < 0.15
True
>>> round(exp(-(n ** (1 - c))), 2)
0.74

7. Eclipse attacks: picking a bucket first#

From Eclipse attacks on Bitcoin’s peer table (Heilman et al. 2015). If the attacker owns 16 of 64 buckets outright, what is the probability that all eight picks land in its buckets?

Solution
>>> f"{(16 / 64) ** 8:.1e}"
'1.5e-05'

Each pick first chooses a random bucket, so the attacker’s chance per pick is the fraction of buckets it holds, \(1/4\), however many addresses it crammed into them. Eight independent picks all succeed with probability \(4^{-8}\), one in 65,536. The simulation, with 2000 trials, saw none.

8. Compact blocks: short-ID collisions#

From Compact blocks: send what the peer lacks (Corallo, BIP 152, 2016). With 6-byte short IDs, 2000 block transactions and a 300,000-transaction mempool, estimate the expected number of colliding pairs.

Solution
>>> pairs = 2000 * 300_000
>>> f"{pairs / 2**48:.1e}"
'2.1e-06'

Each block transaction is compared with each mempool entry, and a pair collides with probability \(2^{-48}\). About one block in 470,000 has a collision, and it costs only an extra round trip. Eight bytes would make collisions rarer still but add a third more to the short IDs of every block; BIP 152 accepts the rare fallback.