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

What We Talk About When We Talk About Distribut...

What We Talk About When We Talk About Distributed Systems

Transcription of this talk with list of resources:

http://videlalvaro.github.io/2015/12/learning-about-distributed-systems.html

Distributed Systems are a complex topic. There's abundant research about it but sometimes it is hard for a beginner to know where to start. I would like to outline the main concepts of distributed systems, so the interested person can have a clear path on how to start their own research as well.

In this talk I will review the different models: asynchronous vs. synchronous distributed systems; message passing vs shared memory communication; failure detectors and leader election problems; consensus and different kinds of replication.

I will also review a series of books on distributed systems in order to recommend the best one according to the topics we would like to learn about, or the problems we would like to solve.

The goal of the talk is to set a good foundation for people interested in learning more about distributed systems.

Alvaro Videla

June 17, 2015
Tweet

More Decks by Alvaro Videla

Other Decks in Technology

Transcript

  1. “A DISTRIBUTED SYSTEM IS ONE IN WHICH THE FAILURE OF

    A COMPUTER YOU DID NOT EVEN KNOW EXISTED CAN RENDER YOUR OWN COMPUTER UNUSABLE” Leslie Lamport
  2. DISTRIBUTED SYSTEMS • Many entities trying to solve a problem

    (nodes, processes) • Partial Knowledge
  3. DISTRIBUTED SYSTEMS • Many entities trying to solve a problem

    (nodes, processes) • Partial Knowledge • Uncertainty
  4. PROPERTIES OF CONSENSUS • C-Termination: Every correct process eventually decides

    on some value • C-Validity: If a process decides v, then v was proposed by some process
  5. PROPERTIES OF CONSENSUS • C-Termination: Every correct process eventually decides

    on some value • C-Validity: If a process decides v, then v was proposed by some process • C-Agreement: No two correct processes decide differently
  6. PROPERTIES OF UNIFORM CONSENSUS • C-Termination: Every correct process eventually

    decides on some value • C-Validity: If a process decides v, then v was proposed by some process • C-Agreement: No two correct processes decide differently • C-Uniform Agreement: No two processes (correct or not) decide differently.
  7. WE NEED CONSENSUS WHEN: A SET OF PROCESSES HAVE TO

    AGREE TO TAKE A COMMON ACTION Atomic Broadcast
  8. WE NEED CONSENSUS WHEN: A SET OF PROCESSES HAVE TO

    AGREE TO TAKE A COMMON ACTION Atomic Broadcast Group Membership
  9. FLP TELLS US THAT IF CONSENSUS CANNOT BE ACHIEVED, THEN

    ATOMIC BROADCAST OR GROUP MEMBERSHIP CANNOT BE ACHIEVED EITHER
  10. FAILURE DETECTORS • External process • Provides information about suspected

    processes • Completeness property (crashed processes are detected)
  11. FAILURE DETECTORS • External process • Provides information about suspected

    processes • Completeness property (crashed processes are detected) • Accuracy (correct process are never suspected)
  12. EVENTUALLY ACCURATE FAILURE DETECTOR • Strong Completeness: Eventually, every process

    that crashes is permanently suspected by every correct process.
  13. EVENTUALLY ACCURATE FAILURE DETECTOR • Strong Completeness: Eventually, every process

    that crashes is permanently suspected by every correct process. • Eventual Weak Accuracy: There is a time after which some correct process is never suspected by the correct processes.
  14. EVENTUALLY ACCURATE FAILURE DETECTOR • Strong Completeness: Eventually, every process

    that crashes is permanently suspected by every correct process. • Eventual Weak Accuracy: There is a time after which some correct process is never suspected by the correct processes. http://dl.acm.org/citation.cfm?id=1052806
  15. “A QUORUM IN A SYSTEM WITH N CRASH-FAULT PROCESS ABSTRACTIONS

    […] IS ANY MAJORITY OF PROCESSES, I.E., ANY SET OF MORE THAN N/2 PROCESSES” QUORUMS
  16. “IF F < N/2 PROCESSES FAIL BY CRASHING, THERE IS

    ALWAYS AT LEAST ONE QUORUM OF NONCRASHED PROCESSES IN SUCH SYSTEMS” QUORUMS
  17. CONSISTENCY CONDITIONS • Atomic Consistency (Linearizabilty) • Sequential Consistency •

    Causal Consistency https://aphyr.com/posts/313-strong-consistency- models
  18. CONCLUSION • Deep Rabbit Hole • Computing Science where Science

    is Still a Thing™ • History of the Field Matters
  19. CONCLUSION • Deep Rabbit Hole • Computing Science where Science

    is Still a Thing™ • History of the Field Matters • Read, read, read