Long Exam 2 - Distributed Systems

Question 1

What is a distributed system?

Answer 1

A collection of autonomous computing elements that appear as a single coherent system with autonomous computing elements (nodes).

Question 2

What is it meant by a collection of autonomous nodes?

Answer 2

Each node is autonomous and has its own notion of time without a global clock. This however leads to fundamental synchronization and coordination problems.

Question 3

What is an overlay network?

Answer 3

Each node in the collection communicated only with the other nodes in the system.

Question 4

What are the two types of overlay networks?

Answer 4

Structured (well-defined set of neighbors through trees and rings) and unstructured (randomly select other nodes)

Question 5

What are the four goals of a distributed system?

Answer 5

• sharing of resources
• distribution transparency
• openness
• scalability

Question 6

What are the three types of scalability?

Answer 6

• size scalability
• geographical scalability
• administrative scalability

Question 7

How to design fault-tolerant systems?

Answer 7

1. Identify all possible faults
2. Detect and contain the fault
3. Handle the fault

Question 8

What is the acronym RAID for?

Answer 8

Redundant Array of Inexpensive Disks

Question 9

What is RAID 1?

Answer 9

• mirroring
• can recover form single-disk failure
• requires 2N disks

Question 10

What is RAID 4?

Answer 10

• dedicated parity disk
• can recover from single-disk failure
• requires N+1 disk
• performance benefits if you stripe a single file across multiple data disks
• all writes hit the parity disk

Question 11

What is RAID 5?

Answer 11

• spread out parity
• can recover from single-disk failure
• requires N+1 disk
• performance benefits if you stripe a single file across multiple data disks
• writes are spread across disks

Question 12

What is isolation?

Answer 12

Occurs either completely before or completely after every other concurrent threads

Question 13

What is the golden rule to achieve atomicity?

Answer 13

Never modify the only copy.

Question 14

How to make renaming shadow copies atomic?

Answer 14

By using single-sector writes.

Question 15

What is a shadow copy?

Answer 15

Shadow copies work because they perform updates/changes on a copy and automatically install a new copy using an atomic operation

Question 16

What are the shortcomings of shadow copies?

Answer 16

• Hard to generalize to multiple files/directories
• Require copying the entire file for even small changes
• Haven’t even dealt with concurrency

Question 17

What are transactions?

Answer 17

Transactions provide both atomicity and isolation. Each transaction will appear to have run to completion or not at all. When multiple transactions are run concurrently, it will appear as if they were run sequentially.

Question 18

What are the three types of records used in a log?

Answer 18

UPDATE records include old and new values of a variable. COMMIT records specify that transaction committed. ABORT records specify that transaction aborted.

Question 19

What is the drawback of using cell storage for logging?

Answer 19

The writes are okay but we write to disk twice instead of once. Recover is also slow as we have to scan the entire log.

Question 20

What is the drawback for using cache for logging?

Answer 20

Recovery takes longer as the log grows. Truncating the log may help by flushing all cached updates to cell storage and writing a checkpoint record.

Question 21

When does two operations conflict?

Answer 21

Two operations conflict if they operate on the same object and at least one of them is a write.

Question 22

What is conflict serializability?

Answer 22

A schedule is conflict serializable if the order of all of its conflict is the same as the order of the conflict in some sequential schedule.

Question 23

What is two-phase locking?

Answer 23

1. Each shared variable has a lock
2. Before any operation on a variable, the transaction must acquire the corresponding lock
3. After a transaction releases a lock, it may not acquire any other locks

Question 24

What are two phases in two-phase locking?

Answer 24

• Acquire phase, where transactions acquire locks. New locks on items can be acquired but none can be released;
• Release phase, where transactions release locks. existing locks can be released but no new locks can be acquired.

Question 25

How to address the possibility of deadlocking in two-phase locking?

Answer 25

Take advantage of atomicity and abort one of the transactions by using victim selection, typically avoiding the transaction that have been running for a long time.

Question 26

What are reader and writer locks?

Answer 26

Multiple transaction can hold reader locks for the same variable at once but only one transaction can hold a write lock for a variable.

Question 27

What are the two phases for two-phase commit?

Answer 27

Prepare – all tasks should be completed before sending prepare
Commit – all prepares should be ACKed before sending commit

Question 28

What to do if workers fail after commit point?

Answer 28

Recovery from crash.

Question 29

What is consistency?

Answer 29

All clients see the same data at the same time, no matter which node they connect to.

Question 30

What is strong consistency?

Answer 30

Whenever data is written to one node, it must be instantly forwarded or replicated to all the other nodes in the system before the write is deemed ‘successful’

Question 31

What is the CAP theorem by Eric Brewer?

Answer 31

Any distributed data store can provide only two of the following three guarantees: Consistency, Availability, Partition Tolerance

Question 32

What is ACID?

Answer 32

Atomicity, consistency, isolation, and durability.

Question 33

What is a view server?

Answer 33

A view server determines which replica is the primary. All requests go through from the coordinators to the view server.

Question 34

What happens if view server fails?

Answer 34

Election for a new view server

Question 35

What are the six consistency guarantees?

Answer 35