distributed systems

• https://github.com/theanalyst/awesome-distributed-systems
  
• https://architecturenotes.co/fallacies-of-distributed-systems/
  

https://en.wikipedia.org/wiki/Lamport_timestamp
A→B (A happened before B), C(A) is the Lamport Clock value of A
Generates a partially ordered set (poset). Ordering is:

• Reflexive (each element is comparable to itself)
  
• Antisymmetric (no two different elements precede each other)
  
• Transitive (A→B and B→C ⇒ A→C)
  

Example: genealogical descendency. Some pairs are incomparable, with neither being a descendent of the other

https://en.wikipedia.org/wiki/Vector_clock

1. Each time a process experiences an internal event, it increments its logical clock by one
   
2. Each time a process sends a message, it increments its own logical clock by one (as in 1., but not twice for the same event) and then sends a copy of its own vector
   (transmmits would be more accurate, the message “goes through”)
   
3. Each time a process receives a message, it increments its own logical clock by one and updates each element in its vector by taking clock by one and updates each element in its vector by taking max(own[i], received[i]) for each element in the vector
   
   

https://en.wikipedia.org/wiki/Version_vector
Replicas can either experience local updates or sync with another replica

1. Each time a replica experiences a local update event, it increments its own counter by one
   

2. Each time a replica a and b sync, the both set the elements to the maximum of the element across both counters (identical vectors after sync)
   

      V_a[x] = V_b[x] = max(V_a[x], V_b[x])
   

3. Replicas can be compared
   
   1. Identical a == b
      
   2. Ordered a <= b, b>=a for all elements and strict inequality for at least one element
      
   3. Concurrent a || b, none of the above
      

Concurrent mutation of a given value in the same value in a time window in which there is no communication generates desynchronization (events are cannot be ordered using Lamport timestamps )

https://github.com/gilbertchen/duplicacy/blob/master/duplicacy_paper.pdf
https://www.computer.org/csdl/journal/cc/5555/01/09310668/1pXhHPUqvAY

• V1 : Uniqueness
  UUID v1 is generated by using a combination the host computers MAC address and the current date and time. In addition to this, it also introduces another random component just to be sure of its uniqueness.
  
• V4 : Randomness
  The bits that comprise a UUID v4 are generated randomly and with no inherent logic.
  chance that a UUID could be duplicated: possible combinations (2^124) → generating trillions of IDs every second, for many years.
  124: 128 bits - 4 bits that are always equal
  

• V5: Non-Random UUIDs
  UUID v5 is generated by providing two pieces of input information:
  

  • Input string: Any string that can change in your application.
    
  • Namespace: A fixed UUID used in combination with the input string to differentiate between UUIDs generated in different applications, and to prevent rainbow table hacks
    

  These two pieces of information are converted to a UUID using the SHA1 hashing algorithm.
  UUID v5 is consistent → given combination of input and namespace will result in the same UUID, every time
  

any distributed data store can only provide two of the following three guarantees:

• Consistency
  Every read receives the most recent write or an error.
  
• Availability
  Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
  
• Partition tolerance
  The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.
  

When a network partition failure happens, it must be decided whether to

• cancel the operation and thus decrease the availability but ensure consistency or to
  
• proceed with the operation and thus provide availability but risk inconsistency.
  

https://jolynch.github.io/posts/distsys_shibboleths/

• Idempotency
  Most useful distributed systems involve mutation of state communicated through messages. The only safe way to mutate state in the presence of unreliable networks is to do so in a way that you can apply the same operation multiple times until it explicitly succeeds or fails.
  
• Incremental progress
  partitions happen for all kinds of reasons: network delay/failure, lock contention, garbage collection, or your CPU might just stop running code for a bit while it does a microcode update.
  The only defense is breaking down your larger problem into smaller incremental problems that you don’t mind having to re-solve in the error case.
  
• Every component is crash-only
  I like to think of this one as the programming paradigm which collectively encourages you to “make operations idempotent and make incremental progress” because handling errors by crashing forces you to decompose your programs into small idempotent processors that make incremental progress.
  
• We shard it on <some reasonably high cardinality value>
  Distributed systems typically handle large scale datasets. A fundamental aspect of building a distributed system is figuring out how you are going to distribute the data and processing. This technique of limiting responsibility for subsets of data to different sets of computers is the well-known process of sharding. A carefully-thought-out shard key can easily be the difference between a reliable system and a constantly overloaded one.
  
• Our system is Consistent and Available.
  Coda Hale presented a compelling argument for this back in 2010 and yet I still hear this somewhat routinely in vendor pitches. What does exist are datastores that take advantage of PACELC tradeoffs to either provide higher availability to CP systems such as building fast failover into a leader-follower system (attempting to cap the latency of the failure), or provide stronger consistency guarantees to AP systems such as paying latency in the local datacenter operations to operate with linearizability while remote datacenters permit stale or phantom reads.
  
• at-least-once and at-most-once are nice, but our system implements exactly-once
  No it does not. Your system might implement at-least-once delivery with idempotent processing, but it does not implement exactly-once which is demonstrated to be impossible in the Two Generals problem.
  if you actually read what they built it is just idempotent processing of at-least-once delivery
  
• I just need Transactions to solve my distributed systems problems
  Transactions can still timeout and fail in a distributed system, in which case you must read from the distributed system to figure out what happened. The main advantage of distributed transactions is that they make distributed systems look less distributed by choosing CP, but that inherently trades off availability! Distributed transactions do not instantly solve your distributed systems problems, they just make a PACELC choice that sacrifices availability under partitions but tries to make the window of unavailability as small as possible.