- Distributed systems = Computers + relativity
- Different machines have different clocks, perception of time, and views of the state of the system
- Challenges: Communication failures, hardware failures, latency, bandwidth
- All computer systems today are distributed at some level (nature obeys relativity after all), the extent to which this nature is exposed depends on the loads put upon the system.
- Decentralized systems = Distributed systems + society
- Challenges: Jerks, Laws, Powerful incumbents
- Need trustworthy and robust systems
- Combines: [Computer Science, Physics, Economics, Social Justice, Engineering]
- Decentralized systems can create social change, alter the balance of power
- How can we make it easier to build them?
- The "Java" model (aka pointer machine) (TODO: Look up pointer machine paper)
- Can allocate finite sized objects
- Objects can have pointers (aka references) to other objects
- Can modify these pointers later
- Cannot modify objects once they are created
- Consequence: No cycles, graph of object references is a DAG
- Lots of work in this area, see Okasaki, Bagwell, Clojure, etc.
- Distributed verification of functional data structures (see dat, IPFS, Git)
- Idea: Replace pointer with secure hash
- Works for any functional data structure! Just overload new!
- Complexity of Set Disjointness
- Work on Merkle Trees, BitTorrent
- General solution for replicating dynamic set of objects
- Merkleized trie of object hashes
- Maintain (large) set of immutable objects addressed by hashes
- Finite set of mutable pointers (aka fingers) into the object set
- Easier to reach consensus/update fingers
- Can replace most of Google with a secure peer-to-peer system!
- Search
- Maps
- Databases
hmm so would you use a Merkleized r-tree?