Section B

Front 1

Describe why an TCP acknowledgment does not mean very muchto the application layer.

Back 1

A TCP acknowledgment means that a TCP segment was placed in the receive buffer. It does not imply, that it was picked up by the application layer.

Front 2

Assume you're implementing a message passing middle layer andhave the option of choosing UDP or TCP as the network transport layer. Whatwould the advantages be of choosing UDP? When would it not be practical touse?

Back 2

* Many small unordered messages

* Don't care about lost messages

* Lower delay.

* Multicast support.

* Less prone to congested networks.

Front 3

When designing a request message layer, one has the option of chosingto provide at-most-once or at-least-once semantics. Describe an advantage with the at-least-once semantics but also describe what it means to the applicationlayer.

Back 3

When using at-least-once semantics, the server does not need to store the request he received and the replies sent. For the application layer it means that retransmission of request could result in an undesired state. To work around this problem idempotent operations are usually used.

Front 4

Briefly describe a situation that meets the requirements of FIFOorder multicast but not to total order multicast.

Back 4

1: s(m1), s(m2), r(m1), r(m2), r(m3)

2: r(m1), r(m3) , r(m2)

3: s(m3), r(m3), r(m1), r(m2)

FIFO order: in the order of the sender

Total order: the same order for all nodes

Front 5

Briefly describe a situation that meets the requirements of totalorder multicast but not to FIFO order multicast.

Back 5

1: s(m1), s(m2), r(m2), r(m1)

2: r(m2), r(m1)

3: r(m2), r(m1)

FIFO order: in the order of the sender

Total order: the same order for all nodes

Front 6

Describe briefly how is NFS client-side caching is implemented andhow file blocks are validated in a read operation.

Back 6

Entry is valid if: last check is within freshness interval (clause 1) or the data is unmodified (clause 2). Checking clause 1 does not require communication.

(T – T_c < t) ∨ Tm_{client} = Tm_{server}

T := current time

T_c := time of last cache entry validation

t := freshness threshold (adaptive)

Tm_{client} := time block was modified at client

Tm_{server} := time block was modified at server

NB: writes are flushed on close and sync

Front 7

Describe the rules to maintain a Lamport clock.

Back 7

1: Increase on local event.

2: Increase on send event and piggyback.

3: Merge on receive: max(local, received) + 1.

Front 8

In a passive replicated system we have a primary that uses a viewsynchronous multicaster to deliver state changes to the back-end replicas. Whydo we use a view synchronous communication layer?

Back 8

The replica managers that survive must agree on which operations had been performedat the point when the replacement primary takes over. This is achieved when using view synchronous communication.

When the primary crashes, the communication system eventually delivers a new view to the surviving backups, one that excludes the old primary. The backup that replaces the primary can be chosen by any function of that view.

Front 9

In an active replication implementation of a fault tolerant server the group service will multicast messages in total order, why is this important and how does the total order help?

Back 9

Replica manager are state machines and have to process all the requests in the in the same order such that they all end up with the same state as one another after each request.

Front 10

If you need to replicate a server that mainly handles computeintensive read request i.e. request that do not change the state of the server,what would then be the best startegy for replication, active or passive, andwhy?

Back 10

Active, to enable load balancing.

Front 11

Give one reasons why we are interested in examining a global stateof a distributed system. Decribe a problem that can be determine by lookingat the global state but not by looking at each local node independently?

Back 11

When we want to know if a predicate is true in a distributed system.

Detection of a distributed dead-lock.

Front 12

Show by example how a dead-lock situation is falsely detected, aphantom lock, if one only consider information gathered from the nodes in asystem one by one.

Back 12

Information gathered from the nodes:

A waits for B

B waits for C

C waits for A

=> look like a dead-lock

We are possibly missing that there is a release message in a channel that releases C. This will break the cycle in the wait-for-graph.

Front 13

Describe briefly quorum based mutual exclusion and its advantages.

Back 13

Every node asks only for permission form a subset of nodes. Any two subsets mustshare at least a node.

To enter: ask your subset, enter when all agree. when leaving, inform subset. meanwhile: queue requests.

To vote: if request arrives and not voted: vote immediately. otherwise, queue request. when vote is returned, dequeue request.

Advantages: Robust to node failures to some degree. Lower count of messages compared to Ricart–Agrawala.

Front 14

Describe the usage of a leaf set in a DHT and why it is important.

Back 14

Leaf sets are used for faster routing in a DHT.

Front 15

In a DHT a large numbers of nodes are connected in a logicalring structure. In order to maintain the ring even if nodes dies, one will keeptrack of a number of successors, not only the closest one. The question is howmany successors to keep track of, the more successors we keep track of the moreresilient we are to node failures, but it also means more links to check. Whatdo we need to consider when deciding how many successors to keep track of?

Back 15

The probability of a node failure.

And the probability of a node failure during the time it takes to repair the successor pointers.

Front 16

A distributed hash table uses a hashing of object names as thekey for each object. Assuming we have names on objects that could be used askeys, for example phone numbers of subscribers, what would the problem be ifthe phone numbers were used instead of the hash of the numbers?

Back 16

Non-uniform distribution of keys.

Front 17

When using two-phase commit in a distributed transaction thesystem could get stuck if the coordinator dies. There are however situationswere the participants in the transaction safely can determine if they shouldcommit or abort. Describe situation were the system is stuck and an situationwhere the participants can decide even if the coordinator is dead.

Back 17

Not stuck:

The coordinator crashes before asking for a promise => participant can discard, since no promise was made

Stuck:

the coordinator crashes but you have made a promise => participant cannot discard statemust wait for recovery