DEV Community: Marius-Florin Cristian

Can We Compute the Minimum Spanning Tree in Linear Time?

Marius-Florin Cristian — Wed, 01 Apr 2026 11:43:03 +0000

Easter egg at the end of how the cover photo is related to the post

Given a connected graph with weighted edges, the minimum spanning tree (MST) is the cheapest set of edges that keeps all vertices connected. Boruvka gave the first algorithm in 1926. Kruskal, Prim, and others refined it. The best randomized algorithm runs in O(m) expected time (Karger-Klein-Tarjan, 1995). The best deterministic algorithm runs in O(m α(m,n)) (Chazelle, 2000), where α is the inverse Ackermann function.

α(m,n) ≤ 4 for any graph that could physically exist. In practice, the problem is solved. In theory, the question "can we do O(m) deterministically?" has been open for over forty years.

This post covers the three attack vectors from my 2018 thesis at DIKU, updated with connections to research published since then.

Where the bottleneck is

Every MST algorithm uses some form of the disjoint-set (union-find) data structure. You process edges, and for each edge you ask: are these two vertices already connected? If not, merge their components.

With path compression and union by rank, m operations on n elements cost O(m α(m,n)). That α factor is the bottleneck. It comes from the analysis of path compression on a pointer machine.

On a Word RAM, Gabow and Tarjan (1983) showed you can do O(m + n) — if you know the union tree structure in advance. You precompute lookup tables for small components and answer FIND queries in O(1).

The catch: knowing the union tree means knowing the MST, which is what you're computing.

Two computation models

This matters because the bottleneck lives in the gap between them.

A pointer machine can follow pointers, compare values, and create new nodes. No arithmetic on addresses, no random access. This is how most graph algorithms actually work. On this model, the α factor from path compression cannot be removed.

A Word RAM has O(1) random access and can do arithmetic and bitwise operations on words. This enables table lookups — precomputing answers for small inputs and reading them in constant time.

The MST gap is a model gap. On a pointer machine, O(m α(m,n)) seems tight. On a Word RAM, O(m + n) is possible if the structure is known. The question is whether you can learn enough structure during computation to exploit the RAM model.

Attack vector 1: Approximate union-find

What if you approximately know the union tree?

Build a predicted tree T' using some fast heuristic (a few Boruvka phases, random sampling, anything that runs in O(m)). Use Gabow-Tarjan lookup tables based on T'. When a FIND query returns an answer that disagrees with the true structure, pay for a correction.

If the prediction is close enough to the true MST, most queries hit the lookup tables and cost O(1). The faulty queries create "phantom cycles" — the algorithm temporarily believes two vertices are connected when they aren't, or vice versa. These phantoms are bounded by the prediction error and can be cleaned up in a linear-time verification pass using King's MST verification algorithm.

This approach fits a framework that didn't exist when the thesis was written: learning-augmented algorithms (Mitzenmacher and Vassilvitskii, 2020). The formal question is: what prediction quality guarantees O(m + n) total cost?

The thesis proves the disjoint-set operations can be bounded to O(m + n) on the RAM model when allowing a bounded degree of error. The precise bounds on prediction quality needed for this to work are stated but not tight.

Attack vector 2: Density partition

Different algorithms are linear at different densities. Prim is linear on dense graphs (m ≥ n^p for p > 1). Kruskal-style algorithms are nearly linear on sparse graphs. Neither covers all graphs.

The density partition classifies vertices by degree:

HD (high degree): degree > c · log³(n)
LD (low degree): degree < c · log³(n)

Then by neighbor types: HDN (high-degree neighbors), LDN (low-degree neighbors), MDN (mixed). This classification takes O(m + n) — two passes over the adjacency lists.

For HD-HDN components (dense), run Prim. For LD-LDN components (sparse), run modified Kruskal with the approximate union-find from attack vector 1. The MDN boundary edges form a small graph — O(n / log³(n)) edges — that can be solved recursively.

At each recursion level, total work is O(m + n). The recursion depth is bounded. This is the glue that combines the other two subproblems.

Attack vector 3: Cycle hierarchy

Consider a sparse graph that is almost a tree. Most vertices have degree 1 or 2. The MST must include all edges connecting degree-1 vertices — there is no alternative path. So you can trim those edges and contract the leaves.

The problem: trimming cascades. Removing a leaf can create a new leaf, which creates another, propagating across the graph. Naive trimming is O(n²).

If you know the cycle structure, you know where each cascade stops — at a vertex that participates in a cycle. With this information, trimming runs in O(n).

The cycle hierarchy organizes cycles by nesting depth:

Level 0: triangles
Level 1: 4-cycles not decomposable into triangles
Level k: (k+3)-cycles that may contain lower-level cycles

Building the hierarchy seems circular — you need a spanning tree to find cycles, but you're computing the MST. The escape: cycle detection doesn't require edge weights. Any spanning tree (from DFS or BFS, computed in O(m + n) without weight comparisons) reveals the cycle structure. Each non-tree edge closes exactly one fundamental cycle.

You compute the topological hierarchy weight-free, then apply it to the weighted MST computation. The hierarchy tells trimming where to stop.

This is the hardest subproblem. The construction is clear in outline, but the formal proof that it runs in O(m + n) for arbitrary graphs is incomplete.

How they compose

Subproblem 1                    Subproblem 3
(Approximate Union-Find)        (Cycle Hierarchy)
         \                          /
          v                        v
           Subproblem 2
           (Density Partition)
                  |
                  v
          Full MST Algorithm
              O(m + n)

Subproblems 1 and 3 are independent. Subproblem 2 combines their results. If all three are solved, they compose into a deterministic O(m + n) MST algorithm on the Word RAM.

On a pointer machine, this approach does not help. The disjoint-set operations without table lookup are bounded by O(m α(m,n)), and that factor cannot be removed without random access.

What's incomplete

Subproblem 1 has a theorem and proof sketch. The formal bounds on prediction quality are not tight. Subproblem 3 has a clear construction but the O(m + n) proof for arbitrary graphs is missing. Subproblem 2 depends on both.

Since 2018, each subproblem has connected to active research:

Approximate union-find → learning-augmented algorithms
Density partition → local graph algorithms and graph sparsification
Cycle hierarchy → dynamic connectivity and top trees

The three subproblems remain open. Whether O(m) MST is achievable deterministically, or whether α(m,n) is fundamental, is one of the oldest open problems in computer science.

The full technical writeup with proofs, definitions, and historical context is on my blog: The MST Problem: Three Subproblems to Linear Time.

The thesis was written at DIKU, University of Copenhagen, supervised by Jyrki Katajainen.

Easter egg time: Bernard Chazelle the CS professor from Toronto who has the best algorithm for the problem up to date is the father of Damien Chazelle, the director of Whiplash and LaLa Land.

Optimizing encrypted P2P file transfer - from 225 to 441 MB/s

Marius-Florin Cristian — Sun, 29 Mar 2026 08:36:21 +0000

Part of the KEIBIDROP development blog. KEIBIDROP is in active development. Release is coming soon.

KEIBIDROP transfers files between two peers over encrypted gRPC. The full stack:

Disk I/O -> FUSE kernel -> FUSE daemon -> gRPC framing -> ChaCha20-Poly1305 -> TCP -> Peer

We built micro-benchmarks for each layer and measured throughput with 1GB files on an Intel MacBook Pro.

Baseline numbers

Layer	Throughput	Overhead
Raw disk (SSD)	~5 GB/s	--
Raw gRPC (no encryption)	981 MB/s	5x vs disk
Encrypted gRPC (ChaCha20)	437 MB/s	2.2x vs raw gRPC
FUSE end-to-end	225 MB/s	1.9x vs encrypted gRPC

The encryption layer costs 2.2x. FUSE adds another 1.9x.

Six optimizations

1. Cache the AEAD cipher. The original code created a new ChaCha20-Poly1305 cipher for every message. Caching it in the constructor is safe because the nonce is a monotonic counter.

// Before: creating cipher per-message
aead, _ := chacha20poly1305.NewX(s.key)  // expensive!

// After: created once in constructor
type SecureWriter struct {
    aead cipher.AEAD  // created once
}

2. Single combined TCP write. Two syscalls per message (header + payload) became one. At 512KB chunks, this halves the write() call count.

3. In-place decryption. aead.Open(ciphertext[:0], nonce, ciphertext, nil) reuses the ciphertext buffer instead of allocating a new one. ~2000 fewer allocations per 1GB transfer.

4. Async cache writes in FUSE Read. FUSE needs the data returned to the kernel. Writing that data to the local cache file can happen in a background goroutine. A WaitGroup ensures everything completes before file close. Cache write overhead dropped from 16% to 1.8%.

n := copy(buff, data)
if cacheFD != nil {
    f.CacheWg.Add(1)
    go func() {
        defer f.CacheWg.Done()
        cacheFD.WriteAt(cacheData, cacheOffset)
    }()
}
return n

5. Push-based StreamFile RPC. The original streaming used request-response per chunk. A new server-streaming RPC pushes all chunks without waiting. On-demand reads (random access) still use bidirectional streaming.

6. Silencing hot-path logs. ~120 slog.Info/Debug/Warn calls in FUSE handlers. Even structured logging allocates. Commenting out non-error logs on Read/Write/Getattr gave 2-6% throughput improvement.

After optimizations

Layer	Before	After	Gain
Encrypted gRPC	437 MB/s	441 MB/s	+0.9%
FUSE end-to-end	225 MB/s	231 MB/s	+2.7%

The encryption tax: 1.49x

We built a controlled benchmark comparing identical gRPC transfers over plain TCP vs ChaCha20-Poly1305:

Transport	MB/s	Duration (100MB)
Plain TCP + gRPC	657	152ms
Encrypted (ChaCha20-Poly1305)	441	227ms

33% of transfer time goes to encryption. Our earlier 2.2x estimate was comparing across different test runs with different system load. The controlled A/B benchmark showed the real cost is much lower.

The irreducible 48%

The gap between encrypted gRPC (441 MB/s) and FUSE end-to-end (231 MB/s) is 48%. Every FUSE Read requires two kernel-to-userspace context switches. We confirmed this by measuring raw FUSE overhead (local file read through FUSE vs direct): ~48%, matching exactly.

Plain gRPC:     657 MB/s  (ceiling)
  -33% encryption
Encrypted gRPC: 441 MB/s
  -48% FUSE kernel overhead
FUSE E2E:       231 MB/s

The FUSE overhead is nearly twice the encryption cost. If we wanted to improve throughput, reducing FUSE transitions would have more impact than switching ciphers. But FUSE is the cost of running a userspace filesystem, and for secure P2P file sharing the tradeoff is worth it.

What we learned

Without isolating each layer, we would have optimized the wrong thing. The biggest win (async cache writes, 16% to 1.8%) was only visible when measured independently.
Caching the AEAD cipher and in-place decryption are tiny code changes with measurable impact at 2000+ messages per second.
Structured logging is not free on hot paths. Even checking the log level has overhead.
FUSE has an inherent 48% overhead from context switches. No amount of userspace optimization can fix this.
Server-streaming eliminates round-trip latency for sequential prefetch. Request-response is still needed for random access.
Our initial 2.2x encryption estimate was wrong. A controlled A/B benchmark (same test, same system) showed 1.49x. Always compare apples to apples.

More from the KEIBIDROP blog: full series | product page | FAQ

Make git clone work between encrypted P2P FUSE peers (7 bugs)

Marius-Florin Cristian — Sun, 29 Mar 2026 08:34:07 +0000

Part of the KEIBIDROP development blog. KEIBIDROP is in active development. Release is coming soon.

KEIBIDROP mounts a virtual FUSE filesystem for each peer. When Peer A creates or modifies files, the changes sync to Peer B's mount in real-time through encrypted gRPC. We already made git work on a single FUSE mount (previous post). The question was: what happens when Peer A clones a repo into their mount, and Peer B tries to use it through theirs?

Bob (FUSE mount)                     Alice (FUSE mount)
+-- .git/                            +-- .git/          <- synced from Bob
|   +-- HEAD                         |   +-- HEAD
|   +-- config                       |   +-- config
|   +-- objects/pack/                |   +-- objects/pack/
|   |   +-- pack-abc123.pack (2MB)   |   |   +-- pack-abc123.pack
|   +-- refs/heads/main              |   +-- refs/heads/main
+-- go.mod                           +-- go.mod
+-- README.md                        +-- README.md

Seven bugs appeared across three debugging sessions.

Bug 1: The rename race

Git uses atomic writes: create config.lock, write content, close, rename to config. KEIBIDROP sends ADD_FILE on close and RENAME_FILE on rename. The prefetch goroutine would download config.lock, finish before the RENAME_FILE arrived, and skip the disk rename because the in-memory path hadn't changed yet.

Fix: the RENAME_FILE handler now does os.Rename on disk before updating maps. The prefetch cleanup becomes a redundant safety net.

Bug 2: Pack file corruption (20 missing bytes)

Alice's pack file was 2,182,186 bytes. Bob's was 2,182,206 bytes. Git's index-pack appends a 20-byte SHA-1 checksum after the file is closed but before the rename. KEIBIDROP sent the ADD_FILE notification at close time with the pre-checksum size.

Fix: after renaming on disk, compare local file size with the size in the RENAME_FILE notification. If they differ, trigger a re-download.

Bug 3: macFUSE cache poisoning

git status showed deleted: go.mod even though the file existed on disk. macFUSE's negative_vncache option caches ENOENT results. macOS probed Alice's mount (Spotlight, fsevents) before the file arrived, the kernel cached "doesn't exist", and subsequent reads never reached our FUSE handler.

Fix: remove negative_vncache from mount options.

Bug 4: The 612-file hang

Cloning a large repo (612 files) hung after checkout completed. Every FUSE Release sent a gRPC notification. 612 files closing in rapid succession overwhelmed the connection.

Three-part fix:

BatchNotify RPC -- batch 64 notifications into a single gRPC call
Per-path debounce (200ms deadline, reset on each update) on the sender side
Prefetch semaphore (max 8 concurrent) on the receiver side

rpc BatchNotify (BatchNotifyRequest) returns (BatchNotifyResponse);

message BatchNotifyRequest {
  repeated NotifyRequest notifications = 1;
  uint64 seq = 2;
  uint64 timestamp = 3;
}

Bug 5: 190,000 log lines

After fixing the notification flood, the clone still hung for 30 seconds. Turns out we had 207,000 getattr calls and 190,000 ENOENT error logs, all written synchronously. macOS probes hundreds of paths per directory (Spotlight, fsevents, .DS_Store, resource forks) and without negative_vncache every probe hits our handler.

Fix: remove trace logs from hot-path handlers. Stop logging ENOENT as an error.

grep -c "FUSE getattr" Log_Bob.txt    207,137
grep -c "Failed to lstat" Log_Bob.txt  190,614

Bug 6: Hook permission denied

fatal: cannot exec '.git/hooks/post-checkout': Operation not permitted. macOS Gatekeeper blocks executing scripts from FUSE mounts.

Fix: add defer_permissions to mount options.

Bug 7: LFS corruption (intermediate sizes + stale notifications)

Git LFS downloads a 420MB XML file incrementally into .git/lfs/incomplete/<hash>. Each intermediate close triggers ADD_FILE with the current size. The peer starts prefetching at 100MB, restarts at 200MB, restarts at 300MB. Then LFS renames incomplete/<hash> to objects/<sha>/<hash>, but the debounced ADD_FILE for the old path fires after the rename, pointing to a file that no longer exists.

Fix: per-path debounce with RENAME retargeting. When a RENAME arrives, the pending ADD_FILE for the old path gets its path rewritten to the new path instead of being deleted or sent stale.

case bindings.NotifyType_RENAME_FILE:
    if old, exists := pending[req.OldPath]; exists {
        delete(pending, req.OldPath)
        old.req.Path = req.Path  // retarget to new path
        pending[req.Path] = old
    }
    immediate = append(immediate, req)

We tried three approaches: deleting the pending notification (broke content delivery), sending it stale (wrong path), retargeting (correct).

The result

After all fixes, the full git workflow works between encrypted P2P FUSE peers:

# Bob clones a repo
$ cd MountBob && git clone git@github.com:user/repo.git
Cloning into 'repo'... done.

# Alice sees it immediately
$ cd MountAlice/repo && git status
On branch main -- nothing to commit, working tree clean

# Alice creates a branch and commits
$ git checkout -b test_me
$ echo "test" > tst.txt && git add tst.txt && git commit -m "Commit for test"

# Bob sees the branch and commit
$ cd MountBob/repo && git log
commit 38e23bc (HEAD -> test_me)
    Commit for test

Tested with a small repo (24 objects, 2MB, 8 files) and a large repo (2339 objects, 257MB + 3.71 GiB LFS, 612 files).

What we learned

FUSE handlers must rename on disk, not just in memory. Goroutines race with notification handlers, especially for tiny files that download in milliseconds.
Git writes data, closes the file, then renames. Between close and rename, other processes can modify the file (index-pack appending checksums). The rename notification has the correct size. Use it.
macFUSE's negative_vncache silently caches ENOENT results. Our handler was never called. These bugs don't show up in FUSE logs because the kernel short-circuits the call.
612 files = 612 goroutines = 612 gRPC streams = connection collapse. A bounded channel + batching worker gives backpressure without blocking the caller.
190,000 synchronous log writes caused a 30-second hang. The logging seemed harmless with 20 files. 612 files with macOS probing turned it into 400,000 disk writes.
For debounce + rename: you can't delete the pending notification (peer never gets content) and you can't send it stale (wrong path). Retarget it to the new path. Three attempts to get this right.
None of these bugs are git-specific. Any application that creates files through one peer's mount and reads them through another would hit the same problems. Git just exercises every edge case.

More from the KEIBIDROP blog: full series | product page | FAQ

I built a peer-to-peer file transfer tool with post-quantum encryption

Marius-Florin Cristian — Thu, 26 Mar 2026 08:58:20 +0000

KEIBIDROP is in active development. Release is coming soon.

I've been building KEIBIDROP for the past year. It's a file sharing tool where files go directly from one computer to another. No cloud, no accounts, no middleman.

What it does

Two people run KEIBIDROP, exchange a short code over Signal or Telegram, and connect. Both sides can browse each other's shared files in real time. With FUSE mode, the peer's files show up as a virtual folder in your file manager. You can open, copy, and read files as if they were local.

The connection is encrypted with ChaCha20-Poly1305 over a hybrid ML-KEM + X25519 key exchange. ML-KEM is the NIST post-quantum standard (formerly Kyber). If quantum computers eventually break classical crypto, sessions established today are still protected.

How it's different from existing tools

WeTransfer and Dropbox upload your files to their servers. AirDrop only works between Apple devices. croc and magic-wormhole are one-shot transfers. Syncthing is for background sync across your own devices.

KeibiDrop is for two people who want to share files right now, see each other's files live, and not trust a third party with their data. Full comparison: KEIBIDROP vs alternatives

The stack

Go 1.24 for backend, networking, cryptography, FUSE
Rust + Slint for the native desktop GUI (no Electron, 20MB binary)
gRPC + Protocol Buffers for peer communication
cgofuse for cross-platform FUSE (macOS, Linux, Windows)
~11,000 lines of Go, ~5,000 lines of tests

Three interfaces

Desktop GUI for drag-and-drop. Interactive CLI for terminal users. Agent CLI (kd) with JSON output over Unix socket, built for AI agents and automation.

IPv6 only (for now)

Both peers need IPv6. This keeps the design simple and avoids leaking IP metadata to STUN/TURN servers. Most ISPs support IPv6 today. NAT traversal for IPv4 is planned.

DEV Community: Marius-Florin Cristian

Can We Compute the Minimum Spanning Tree in Linear Time?

Where the bottleneck is

Two computation models

Attack vector 1: Approximate union-find

Attack vector 2: Density partition

Attack vector 3: Cycle hierarchy

How they compose

What's incomplete

Optimizing encrypted P2P file transfer - from 225 to 441 MB/s

Baseline numbers

Six optimizations

After optimizations

The encryption tax: 1.49x

The irreducible 48%

What we learned

Make git clone work between encrypted P2P FUSE peers (7 bugs)

Bug 1: The rename race

Bug 2: Pack file corruption (20 missing bytes)

Bug 3: macFUSE cache poisoning

Bug 4: The 612-file hang

Bug 5: 190,000 log lines

Bug 6: Hook permission denied

Bug 7: LFS corruption (intermediate sizes + stale notifications)

The result

What we learned

I built a peer-to-peer file transfer tool with post-quantum encryption

What it does

How it's different from existing tools

The stack

Three interfaces

IPv6 only (for now)

Links