Distributed Systems Flashcards
What is a distributed system?
Software in which components are located on networked computers and can coordinate their actions by sending messages.
What is the difference between a parallel system and a distributed system.
Parallel systems still share memory, while distributed systems don’t share any components.
Pros of a DS?
Scalability
Reduced latency
Fault tolerance
Mobility
Characteristics of DS?
Each entity has its own memory, distributed state needs to be synchronized
Entities communicate using message passing
Each entity maintains parts of the complete picture
Fault tolerant
Challenges with a DS?
- Partial failure
- Unreliable networks
- Unreliable time
- No single source of truth
What is a synchronous system?
The process execution speeds or message delivery times are bounded. This means that timed failure detection, time-based coordination, and worst case performance can exist.
What is a asynchronous system?
There are no assumptions about process execution speeds or message delivery times.
Why is waiting for a reponse in an asynchronous system ambiguous?
Because you cannot tell if
The request was lost
The remote node is down
The response was lost
The usual remedy is to set timeouts and retry until success
What are the two ways to keep time?
Real time clocks (RTCs), which are kept in sync with the NTP protocol with centralized servers.
Monotonic clocks which only move forward.
Why are monotonic clocks useful and who maintains them?
They are maintained by the OS, and are helpful for maintaining order within a node.
Why are RTCs useful.
THey can synchronize time across nodes with an accuracy of milliseconds, whereas modern CPUs can do millions of operations / ms.
External ordering schemes?
Total order: Message rate is globally bounded, synchronized RTCs guarantee order
Causal order: Rely on the happens-before relationship
When do we call events concurrent?
When they don’t have a happens-before relationship.
What are lamport timestamps?
Each process p maintains a counter LT(p)
* p performs action, increments LT(p)
* p sends a message, includes LT(p)
* P receives a message from q. LT(p) = max(LT(p), LT(q)) + 1
For two events a -> b then LT(a) < LT(b). The reverse is not true.
What are vector clocks
On a system of N nodes, each node i maintains a vector Vi of size N. As such:
* Vi[i] is the number of events that occurred in node i
* Vi[j] is the number of events that node i knows occurred at node j