Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Math Behind Distributed Systems

The Math Behind Distributed Systems

Algebraic Topology (and Graph Theory) used to explain the interconnections and verification of a distributed system

Verónica López

April 29, 2017
Tweet

More Decks by Verónica López

Other Decks in Research

Transcript

  1. whoami •Software Engineer •Former physicist; sci comp •Academia + Industry

    •Trying to make computers and science converge <- modern approach
  2. Math is very useful for programming and systems design, but

    that might not mean what you think it means.
  3. Math in CS •Basic: e.g.arithmetic, geometry (frontend), logic •Specific: e.g.

    linear algebra (machine learning, big data), calculus (simulations) •General: e.g. graph theory, topology
  4. Math in CS •Basic: e.g.arithmetic, geometry (frontend), logic •Specific: e.g.

    linear algebra (machine learning, big data), calculus (simulations) •General: e.g. graph theory, topology
  5. “A distributed system is one in which the failure of

    a computer you didn’t even know existed can render your own computer unusable” Leslie Lamport
  6. Probability •If the probability of something happening is one in

    10^13, how often would it happen? •“Real life”: Never •Physics: All the time. •Think about servers (infrastructure) at scale.
  7. Graph Theory •The study of graphs: the mathematical structures used

    to model pairwise relations between objects. •Two concepts: nodes (vertices) & lines (edges) •Might be directed or indirected
  8. The paper on the Seven Bridges of Königsberg (1736, Leonard

    Euler) is considered the first paper in history of graph theory.
  9. Graph Theory in Distsys •Design system’s connectivity •k-connectedness: how many

    nodes we need for a graph to disconnect a graph •Verify points of failure •Rearrange stuff
  10. Topology •The study of geometric properties and spatial relations unaffected

    by the continuous change of shape or size of figures (formal) •Interrelation (informal)
  11. Topological Properties •Properties that remain invariant under continuous stretching and

    bending of the object •E.g. Path connectivity, higher dimensional analogs
  12. The paper on the Seven Bridges of Königsberg (1736, Leonard

    Euler) is considered the first paper in history of topology (too!).
  13. Combinatorial (Algebraic) Topology •Studies spaces that can be constructed with

    discretized pieces •Allows to have all the (system) perspectives (of a node) available at the same time. •Perspectives evolve with communication
  14. Verification of a Distributed System •Talk & Article by Caitie

    McCaffrey (@caitie) •Article: List of methods that prove properties about a system. •Systems get a gold star. •Very hard to get! (Expensive and/or slow)
  15. Verification of a Distributed System •Formal Specification Languages (definition &

    correctness) <- AWS •Model Checking (execute all paths) •Composition (more than 1) •Instead: canaries, monitoring, SREs, etc.
  16. Combinatorial Topology could be used to (help) formally verify a

    distributed system (through algebraic expressions)
  17. Extra resources • Algebraic Topology and Distributed Computing, A Primer

    http://cs.brown.edu/~mph/HerlihyR96/sv.pdf • The Topology of Distributed Adversaries https:// link.springer.com/article/10.1007/s00446-013-0189-9 • The Topological Structure of Asynchronous Computability http://cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf • The Verification of a Distributed System http:// queue.acm.org/detail.cfm?id=2889274