CS7210

Question 1

What is a distributed system?

Answer 1

A collection of computing units that interact by exchanging messages via an interconnection network and appear to external users as a single coherent computing facility

Question 2

What is the CAP theorem?

Answer 2

A distributed system can be two of:

• Consistent
• Available
• Partitioned

Question 3

What are some difficulties in client-server systems?

Answer 3

• Discovery and bundling
• Identifying the interface and parameter types
• Agreeing on the data representation
• Explicit data management
• Unpredictable delays
• Unknown cause of failures
• Must be explicitly handled

Question 4

What are the goals of an RPC system?

Answer 4

Hide complexity of distributed programming, and make it look more similar to local node programming.

Question 5

When we can look at two timestamps from a logical clock, and the timestamp of one event is greater than another event, if we can assume that the event with a greater timestamp happened later, we say that logical clock has ____ ____ ____

Answer 5

Strong clock consistency

Question 6

What type of value do Lamport clocks for their timestamp?

Answer 6

A scalar value

Question 7

Are Lamport clocks strongly consistent?

Answer 7

No, it is only consistent

Question 8

In the context of logical clocks, what is the difference between consistency and strong consistency?

Answer 8

Consistent: Difference in the order of two events implies difference in timestamps, but not vice versa

Strongly Consistent: Difference in timestamps implies the order of two events

Question 9

How does a vector clock work?

Answer 9

Each process maintains its own view of time at other nodes.

It keeps a vector (array) of values, which represent Lamport clocks for each node.

Question 10

When a vector clock receives a message, what does it do with the passed in vector value?

Answer 10

For each value in the vector, it updates its own with the maximum of the value in its own or the message vector. Then, after triggering an event, it increments its own value in its own vector.

Question 11

Suppose vector clock 0 has clock values [2,1,1] and receives a message with clock values [2,2,0]. What will its vector values be after processing the message?

Answer 11

[3,2,1]

Question 12

Are vector clocks consistent?

Answer 12

Yes

Question 13

Are vector clocks strongly consistent?

Answer 13

Yes

Question 14

Does a Lamport clock require more space as more nodes are added?

Answer 14

No

Question 15

Does a vector clock require more space as more nodes are added?

Answer 15

Yes, each node has its own element in the vector (array)

Question 16

If a scalar clock represents a node’s belief about the current time, and a vector clock represents a node’s belief about each node’s belief about the current time, what does a matrix clock represent?

Answer 16

A node’s belief, about each node’s belief, about each node’s belief about the current time.

Question 17

What benefit does a matrix clock provide over a vector clock?

Answer 17

It allows for garbage collection. If every node knows that every node has passed a time t , then every node knows about everything that has happened prior to t

Question 18

What is the Global State of a distributed system comprised of?

Answer 18

• Processes and Channels
• Process state defined by most recent event
  
  • Channel state defined by inflight messages

Question 19

Each event in a distributed system changes the state of at least one of the entities, therefore changing the ____ of the distributed system.

Answer 19

State

Question 20

In the context of distributed system state, what is a “run”?

Answer 20

A sequence of events. It can be actual, or observed.

Question 21

In the context of state in a distributed system, what is a cut?

Answer 21

The state of the system at a point in time.

Question 22

In the context of state in a distributed system, is a cut at the same point in time for all nodes?

Answer 22

No, it might be curved like this:

Question 23

In the context of state in a distributed system, what is a consistent cut?

Answer 23

A snapshot that corresponds to some possible point in the execution which could have been represented by a consistent ordering of the events.

Question 24

In the context of state in a distributed system, what is a prerecording event?

Answer 24

Events that occurred before a cut

Question 25

In the context of state in a distributed system, what is a postrecording event?

Answer 25

Events that happen after a cut

Question 26

Why is it difficult to capture state in a distributed system?

Answer 26

* Instant recording is impossible * We can't assume a global clock * Networks have delays * They're not deterministic

Question 27

How does the Chandy and Lamport snapshot algorithm to capture distributed system state work?

Answer 27

Question 28

Does the Chandy and Lamport algorithm promise to give a consistent state?

Answer 28

Yes

Question 29

In the context of distributed system state, what is a “stable property”?

Answer 29

Iff when it becomes true in a state *S* , it remains true for all states *S'* reachable from *S*

Question 30

What are some examples of Stable Properties?

Answer 30

Deadlock Termination

Question 31

In the context of distributed system state, what is an “unstable property”?

Answer 31

If when it becomes true in a state *S* , it is possibly (but not necessarily) true for a later state reachable from *S*

Question 32

What is consensus?

Answer 32

Agreement among distributed processes about something, e.g. the outcome of a transaction

Question 33

What are the key properties of a consensus?

Answer 33

All non-faulty processes eventually decide on a value, all processes decide on a single value, and the value that's decided on must have been proposed by some process

Question 34

In the context of consensus in distributed systems, what is an Admissible Run?

Answer 34

Run with 1 faulty processor and all messages eventually delivered (matches system model)

Question 35

In the context of consensus in distributed systems, what is a Deciding Run?

Answer 35

An admissible run where some non faulty processors reach a decision

Question 36

In the context of consensus in distributed systems, what is a Totally Correct Consensus Protocol?

Answer 36

When all admissible runs are also deciding runs

Question 37

In the context of consensus in distributed systems, what is a uni-valent configuration?

Answer 37

When only one decision is possible

Question 38

In the context of consensus in distributed systems, what is a bi-valent configuration?

Answer 38

When more than one decision is possible

Question 39

What is the FLP theorem?

Answer 39

The Fischer/Lynch/Patterson theorem says that in a system with one fault, no consensus protocol can be totally correct.

Question 40

How do existing consensus systems not violate the FLP theorem?

Answer 40

They change some of the assumptions and system properties

Question 41

In distributed systems, what is the goal of replication?

Answer 41

To make state available at more than one node

Question 42

What is the difference between active and standby (primary-backup) replication?

Answer 42

In active, both replicas can handle requests. In stand-by, one replica takes requests and others are kept consistent in preparation for a failover.

Question 43

What are the two main techniques to implement replication?

Answer 43

State replication, and replicated state machine

Question 44

What is the difference between state replication, and a replicated state machine?

Answer 44

State replication is where one replica processes a request, and then copies the new resulting state to other replicas. Replicated state machine is where a copy of each operation is sent to and executed at each replica, to produce the same state update.

Question 45

What are the pros and cons of the state replication approach to replication?

Answer 45

Pro: no need to re-execute multiple times Con: state may be large or hard to identify where all updates are

Question 46

What are the pros and cons of the replicated state machine approach to replication?

Answer 46

Pro: no need to send large state, operation logs may be smaller Con: must re-execute, and it requires that the operations be deterministic

Question 47

How does chain replication work?

Answer 47

The head node receives a write request, and forwards it down a chain of replicas. This prevents the head replica from having to interact with every other replica.

Question 48

With chain replication, which replica serves read requests?

Answer 48

The tail replica (last one in the chain), because it ensures that all of the replicas have received the updates.

Question 49

What are the pros and cons of chain replication?

Answer 49

Pros: the leader write node is scalable, it can handle a lot of writes, and it makes strong consistency possible Cons: many workloads are read heavy, and inefficient in that middle nodes may be underutilized

Question 50

How does CRAQ improve on chain replication?

Answer 50

It keeps both the old and new versions of data at each replica while the update propagates through the chain. If both versions are present, it checks with the tail to see if the new version has finished propagating. If it hasn't, it returns the old version. This makes it possible to send reads to the replicas in the middle of the chain.

Question 51

When a fault is ____ it leads to an error

Answer 51

activated

Question 52

When an error ____ it becomes a failure

Answer 52

propogates

Question 53

What is a transient fault?

Answer 53

A fault that appears and then disappears

Question 54

What is an intermittent fault?

Answer 54

A fault that appears on and off

Question 55

What is a permanent fault?

Answer 55

A fault that stays once it occurs

Question 56

What is a fail-stop failure?

Answer 56

One or more components of the distributed system stop working/responding, like a crash

Question 57

What is a timing failure?

Answer 57

The system components behave outside of some timing expectations, which can interfere with things like timeouts

Question 58

What is an omission failure?

Answer 58

When some action is missing

Question 59

What are some practical ways of managing failures?

Answer 59

Detection, Removal, and Recovery

Question 60

What are a couple basic techniques for tracking state change so that a node can roll back to a known good state?

Answer 60

Checkpoints and logging

Question 61

What is the checkpointing technique for tracking state change so that a node can roll back to a known good state?

Answer 61

Where the node periodically saves its state, so that it can reload from there

Question 62

What is the logging technique for tracking state change so that a node can roll back to a known good state?

Answer 62

Where the node logs information about the operations performed, so that it can undo or redo changes. The log is kept on persistent storage, but the changes are smaller so less I/O time is needed. The downside is that recovery takes longer than it does in checkpointing.

Question 63

How can we combine the checkpointing and logging techniques for recovering a failed node?

Answer 63

Checkpoint every so often, and keep logs since the last checkpoint

Question 64

What are the three different approaches to determining when to capture a checkpoint?

Answer 64

Uncoordinated, coordinated, and communication-induced

Question 65

What is uncoordinated checkpointing?

Answer 65

When processes take checkpoints independently

Question 66

What are the risks/downsides of uncoordinated checkpointing?

Answer 66

You might have to go very far back before finding a combination of processes' checkpoints that make up a consistent cut. aka domino effect Processes may capture checkpoints that can't be part of a consistent cut May need to keep more than the most recent checkpoints Creates the need to identify obsolete checkpoints

Question 67

What is coordinated checkpointing?

Answer 67

When the processes coordinate their checkpoints so that they get a consistent cut.

Question 68

What are the two kinds of communicaton-induced checkpoints?

Answer 68

Blocking: where an initiator uses 2-phase-commit or some other consensus algorithm to stop underlying application work and take a snapshot Non blocking: Using the global snapshot algorithm, piggybacking the info instead of using a marker to eliminate the need for FIFO networking

Question 69

What is the fundamental tradeoff of logging vs checkpointing?

Answer 69

Spending compute vs I/O

Question 70

What is pessimistic logging technique for failure recovery?

Answer 70

Logging everything to persistent storage before allowing an event to propagate and commit

Question 71

What is optimistic logging technique for failure recovery?

Answer 71

Assuming that log will be persisted before a failure occurs, but making it possible to remove effects if abort needed

Question 72

What is causality-tracking logging technique for failure recovery?

Answer 72

Ensuring causally related events are deterministically recorded