scalable-commutativity.md

• Scalability := linear increase in performance
• Scalability <= conflict-free memory access
  • aka "accesses disjoint memory (on a disjoint-access-parallel architecture)"
  • Memory is shared state
  • Cache coherence
  • 50 open() calls in the time it takes to read a contended cache line
• OS as bottleneck
  • OS primitives (files, processes/threads/signals, sockets) used by applications
• Linux scaling process
• Scalable interfaces
  • "creat returns lowest FD" example
• Scalable commutativity rule

  • Operations commute
    

  • => Results independent of order
  • => Communication is unnecessary
  • => No write conflicts
• Proof
  • Actions
  • SIM Commutativity
  • State-sensitive (eg create-or-error doesn't commute, but for different dirs)
  • Interface-sensitive (eg two differently-balanced binary trees)
• Commuter
  • Given an interface (eg POSIX), generate test cases that are not stopped from commuting by the interface
  • Run the test cases on an existing implementation
• How does commuter work?
  • Reference implementation of the effect of rename
  • SE solves for "under what states do two calls to rename commute?"
• Evaluation of commuter