Today & maybe tomorrow I'd like to describe the basic theory behind various techniques for building distributed software. What some of the main building blocks are, how they work as nontechnically & briefly as I can, what they're useful for, and namedrop some implementations you might have heard of.

Feel free to expand on this thread with more indepth links or other techniques I've overlooked!

Explicitly out-of-scope is cryptography, that'll be discussed another day.

1/5

First off the most obvious solution is to send messages directly to the recipient without routing through a middleman who we don't trust. Because why have a fully-capable routing infrastructure when you're only sending messages to FAANG?

Unfortunately ISPs have refused to upgrade to IPv6 over the past decades, leaving walls ("NAT") in place for peer-to-peer (P2P) software to hack around. Also we need to lookup the address to mail messages to...

E.g. 1on1 videochats, Syncthing, Bittorrent

2/5

In the early 2000's we figured out a way to build distributed key-value stores using a technique called Distributed Hash Tables (DHTs, e.g. memcached).

DHTs maintain an invariant that every peer knows the values (e.g. IP address) for the keys who's hash is closest to it's own identifier, so we can simply ask around to get rapidly closer & closer to the peer who actually knows.

This invariant is established by having each node query it's own ID upon coming online.

3a/5

DHTs are the techniqued used to store data P2P, though usually there's layers of indirection to balance network costs & often fail to protect privacy. You may have heard of Bittorrent, GNUNet, IPFS, or Dat?

If a DHT's keys are hash of their value (as in many of those examples) it's called a Content Addressed Store.

DHTs were retrospectively to earlier successful P2P like Bittorrent & Tor networks to replace centralized components. Though it took too long for GNU Jami to add it to SIP.

3b/5

O.K., one final toot on DHTs to clarify some false marketting!

DHTs can loose data. The difference is that it's more like a human forgetting something due to it becoming irrelevant to them than like invoking your Right To Be Forgotten on Google. Cryptographers have even proposed using this to share time-limited secrets!

It is possible for DHTs to enforce *some* invariants by not forwarding/storing invalid data.

I am very keen on adding a DHT to my browsers given it protects privacy!

3c/5

Merkle trees, e.g. Git-era version control, are immutable datastructures (like you might write in e.g. Haskell) where pointers are represented as a hash of the addressed value. Which allows you to check you've got the correct dereferenced value from another peer.

In Git this serves to cut down on syncing costs. IPFS, & I think Dat, is characterized by combining a Content Addressed Store with Merkel trees to store larger structured data.

4/6 (I miscounted topics!)

The technique that really excites me, as well as Ink & Switch, are Conflict-free Replicated Data Types (CRDTs)!! They are inversely-linked immutable datastructures which blur the lines between the data & the operations which constructed it, making trivial to merge divirging documents.

CRDTs are how you do P2P collaborative document editing! (Google Docs is built on a precursor called Operational Transforms)

Maybe I need practical example to explain them... Plain text editing?

5a/6

You can implement a collaborative plaintext editor by representing the text as an inversely-linked list which you flatten for display. Each character (letter, etc) points to the one before it. You delete a letter by appending a new "tombstone" pointing to it (yes, CRDTs store the whole undo history, which *can* become wasteful).

To collaborate with others send these insert/delete operations directly to be merged into their copy at whatever rate you like.

5b/6

Since I failed to find a well-known implementation to namedrop (can you help?), here's some links:

A CRDT kanban board: https://github.com/automerge/trellis
CRDT library for JSON: https://github.com/automerge/automerge
Ink & Switch's writeup: https://www.inkandswitch.com/local-first.html

5c/6

Finally by now everyone has heard of blockchains (e.g. Bitcoin-era cryptocurrencies), many even have strong feelings for or against it. But what are they for?

They get everyone to agree on a order of events so large networks can agree on who called dibs on a name or whether you've already spent your last *coin. Allowing peers forwarding messages amongst themselves to enforce more invariants by choosing a random peer to chose the next block(s).

They don't actually store data for retrieval.

6/6

As for how they choose that random peer, it resembles slot machines.

They alter an otherwise meaningless number in the block until they get n bananas in the resulting hash. Where n is chosen by the network to keep blocks coming at a consistant rate. This is the "proof of work".

As an award that peer (or "miner") wins some predecided ammount of cryptocurrency & block's added to the chain.

6b/6

Wow, I've mentioned hashes a lot!

Any techniques I overlooked in this thread? Any good links to expand on these topics?

@grainloom mentioned NDNs. Is that Named Data Networking?

Just please don't argue over whether blockchains have any merit, or whether you value NFTs in my replies!

@alcinnz maybe mention naive gossip protocols? They probably should have gone between direct p2p and DHTs since DHTs were adopted in a lot of cases to solve the scaling problems of a flood-style gossip protocol...

@syntacticsugarglider Yeah that makes sense!

Can't say I'm all that familiar with them, can you please expand?