Distributed Systems

Question 1

What is a distributed system?

Answer 1

Software in which components are located on networked computers and can coordinate their actions by sending messages.

Question 2

What is the difference between a parallel system and a distributed system.

Answer 2

Parallel systems still share memory, while distributed systems don’t share any components.

Question 3

Pros of a DS?

Answer 3

Scalability
Reduced latency
Fault tolerance
Mobility

Question 3

Characteristics of DS?

Answer 3

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

Question 4

Challenges with a DS?

Answer 4

1. Partial failure
2. Unreliable networks
3. Unreliable time
4. No single source of truth

Question 5

What is a synchronous system?

Answer 5

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.

Question 6

What is a asynchronous system?

Answer 6

There are no assumptions about process execution speeds or message delivery times.

Question 7

Why is waiting for a reponse in an asynchronous system ambiguous?

Answer 7

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

Question 8

What are the two ways to keep time?

Answer 8

Real time clocks (RTCs), which are kept in sync with the NTP protocol with centralized servers.
Monotonic clocks which only move forward.

Question 9

Why are monotonic clocks useful and who maintains them?

Answer 9

They are maintained by the OS, and are helpful for maintaining order within a node.

Question 10

Why are RTCs useful.

Answer 10

THey can synchronize time across nodes with an accuracy of milliseconds, whereas modern CPUs can do millions of operations / ms.

Question 11

External ordering schemes?

Answer 11

Total order: Message rate is globally bounded, synchronized RTCs guarantee order
Causal order: Rely on the happens-before relationship

Question 12

When do we call events concurrent?

Answer 12

When they don’t have a happens-before relationship.

Question 13

What are lamport timestamps?

Answer 13

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.

Question 14

What are vector clocks

Answer 14

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

Question 15

How do VC updates work?

Answer 15

• Local events at node i increment Vi[i]
• WHen node i sends a message to node j, it includes Vi
• When node j received Vi, it updates all elements of Vj to Vj[x] = max(Vi[x], Vj[x])

Question 16

What are the guarantees of VCs?

Answer 16

• If a -> b then VC(a) < VC(b)
• If VC(a) < VC(b) then a -> b
• If VC(a) < VC(b) then RT(a) < RT(b)