Malins ID2201

What is a soft link in a file system?

a path that is resolved to another path

What is a hard link in a file system?

a mapping of a name to a file identifier

Can two Unix processes simultaneous write to different positions in a single file?

Yes, the two processes will have their own file table entries.

What is the purpose of the Unix lseek operation?

set the read/write pointer of an opened file

How is a NFS client-side cache entry validated?

if the validity was checked less than t seconds ago or if the server modification time is equal to the client modification time

How does a NFS server know at what position to read and write to?

each read and write operation holds the position

What is a dirty-read during a transaction?

reading a value that has not been committed

What is two-phase locking in a transaction?

not taking any locks once a lock has been released

What does it mean that a transaction meets the atomicity property?

either all or no operations in the transaction are performed

What does it mean that a transaction meets the isolation property?

intermediate results must not be visible to other transactions

What does it mean that a transaction meets the durability

property?

the effects of the transaction will remain even if we have a server crash

What is two-phase commit?

a protocol that ensures atomicity in a distributed transaction

What is the problem of using optimistic concurrency control when implementing a transactional server?

if a conflict occurs both transaction must be aborted

What problem could we still have even if two transactions are serially equivalent?

no problems since all conflicting operations are performed in the same order

If the coordinator dies, what information is not enough for a set of servers to complete a two-phase-commit operation?

A majority of servers have sent promises to be able to commit.

In a distributed transaction one often use two-phase commit, why is this better than one-phase commit?

We ensure that if one transaction commits then all transactions will commit.

What is a phantom deadlock?

one that is detected but not stable

What is a view, created by a group membership service?

the set of processes belonging to a group

In a view-synchronous group membership protocol, a process that enters the group, and is included in the delivered view, will be guaranteed to be delivered:

all messages starting from the view where it is included in the group

Assume we have a server that is up with the probability p and use n replicated servers to increase reliability of a service. What will the probability be that the service is up, assuming that we only need one node to be up in order to provide the service?

1 − (1 − p)^n

Why is view-synchronous communication different from reliable multicast?

a message is sent and delivered only by processes belonging to the same view

What is a view in view-synchronous communication?

A set of nodes considered to be alive.

In an active replicated server, how do we know that the replicas are in a consistent state?

they reliably receive all requests in a total order

Why is it important that a primary server in a passive replicated system uses view-synchronous group communication?

so that all or none of the backup servers have received an update before a new primary is elected

What is sent by the primary replica manager to the backup replica manager in a passive replicated system?

A unique identifier, the state change and the response.

Will an active replicated server with multiple front ends, that uses a total order multicaster, handle requests in causal order?

not if clients can communicate with each other in between sending request and receiving reply

A routing strategy, in a distributed hash table of n nodes, would typically have an asymptotic complexity of:

O(log(n))

If a node crashes with probability q and p is the risk of a node crashing during the time it takes to repair successor pointers and s is the number of successor pointers, then what is the risk of loosing a DHT ring?

1 − (1 − p)^s

What is the purpose of hashing in a DHT?

to generate uniformly distributed keys

What is the difference between a URL and a URN?

URN resolve into any replica of a resource matching the URI

How are inconsistencies of the resolver cache handled in the DNS architecture?

each entry has a time-to-live

What is the advantage of using recursive navigation for DNS queries?

servers can hide internal DNS hierarchy

How are inconsistent cached entries removed from a DNS resolver?

all entries have an expiration time set when cached

What is the advantage of a flat name space?

it is a simple solution

How can we make two computer clocks perfectly synchronized?

we can not

What accuracy can be provided using Christian’s algorithm?

±(Tround ÷ 2)

What is the purpose of the Berkeley algorithm?

to perform internal synchronization

What does the reply from a NTP server contain?

send and receive time of request and send time of reply

When is it better to use the Berkeley algorithm rather than NTP for clock synchronization?

when implementing internal synchronization

Assume that a NTP server can not respond to a received request in less than 40 ms, how does this influence the accuracy of synchronizing clients?

synchronization is limited by the network delay plus 40 ms

At time 117 you receive a NTP reply with the following information: request sent at 82, received at 111, reply sent at 120.

How should you adjust your time?

advance 9 steps

What is provided by UDP?

a best effort delivery of messages to a process

What does UDP give us that is not provided by IP?

port addressing

What is provided by TCP?

a full-duplex stream between two processes

What is not provided by TCP?

a guaranteed delivery of messages

When is the TCP window size a limiting factor for high capacity communication?

over a long fat communication link

Which address can be found in the TCP header?

the port number

What is a good reason for choosing UDP rather than TCP?

you have small messages that should be sent with little delay

What is a good reason for choosing TCP rather than UDP?

TCP will guarantee the delivery of a message

What is the maximum TCP capacity in a 100 Mbps link with 250 ms round trip latency using a 64 Kbyte window size?

2 Mbps

What is the maximum TCP capacity in a 100 Mbps link with 25 ms round trip latency using a 64 Kbyte window size?

20 Mbps

One can determine how large the receiver window should be, in for example a TCP connection, in order to maximize he capacity of a link. How is this calculated?

capacity of link times round trip latency of the link

The limiting factor for capacity in a TCP connection, T bps, where the link capacity is C bps, the round trip time R sec and the receiver window W bits is:

the lesser of C and W/R

When estimating the maximum capacity of a TCP connection you need to know:

the minimum link capacity and the round trip

What does it mean that you receive a TCP acknowledgment form a node?

A sequence of bytes have been received by the TCP process on the node.

What is the benefit of a reliable multicast?

messages are guaranteed to be delivered to all correct processes

Can we implement a reliable multicast using only basic multicast?

yes, by re-sending each received message to all other nodes

How can we implement uniform reliable multicast given that we have reliable point to point message passing?

Tag each message with a unique identifier and send it to each node. When receiving a new message you forward it to all nodes in the group and then deliver it to the application layer

We sometimes want to include the behavior of faulty nodes in our requirements and talk about uniform agreement for multicast. What do we mean by uniform agreement?

If any node, including faulty, deliver a message then all correct nodes deliver the message.

What is the difference between uniform agreement and non-uniform agreement for multicast?

Uniform agreement includes the behaviour of non-correct node.

What is the definition of total order multicast?

messages are delivered in the same sequence

What would you call a multicast service that would never deliver a message m2 before another message m1, if m2 was sent as a response to m1?

causal order

When does Ricart and Agrawalas mutual exclusion algorithm perform better than a central solution?

under low congestion when hardly any conflict will occur

What are the requirements for using the Bully algorithm?

we must have reliable failure detectors

How are FIFO, causal and total order multicast related?

a total order is also a FIFO order

In the Bully algorithm, having n nodes, what is the time it takes from calling an election and receiving the result? Assume that we have a multicast support in the network so we can multicast in constant time and that all decisions are in constant time.

O(1), since neither initiating the election nor sending out the result is depending on the number of nodes (we have multicast support)

What is the advantage of a ring based election algorithm compared to the bully algorithm?

more reliable if nodes fail

What is the advantage of a bully algorithm compared to a ring based algorithm?

better turnaround time

What does Lamport clocks give us when implementing distributed mutual-exclusion?

at most one process may enter the critical section at a time (safety)

How can we guarantee that processes, that can crash, communicating over a asynchronous network can reach a non-trivial consensus?

we can not, we can only hope for the best

What is true if A happened before B?

it is unknown if A occurred in real-time before B

What is true if A happened real-time before B?

A could have happened before B

What is true for events A and B?

if A caused B then A happened before B

What can we know with a and b if we use Lamport clocks?

if L(a) < L(b) then a could have caused b

What can we know if we use Lamport clocks?

if, but not only if, a happened before b then L(a) < L(b)

What can we conclude looking at the Lamport clock time stamps of two events?

if L(b) = L(a) then we cannot conclude anything about a and b

What is the most that we know if we use vector clocks?

V (a) < V (b) if and only if a happened before b

Which is the most natural representation of a vector clock?

a record with one element per process

What is the difference between a Lamport clock and a vector clock?

only the vector clock gives a complete description of the ”happened before order”

When is it problematic to use vectors clocks?

when we have a dynamic set of processes

An alternative way of implementing a vector clock would be to keep a set of the highest counters seen from each process (including own), send it along with any message, update own counter and merging the own set and received set when a message is received. This would have the following advantage:

new processes can easily be added

If events in a given set are to be ordered in a total order that respect the happened before order what is the advantage of using vector clocks?

if tow events are unordered only vector clocks can order them

Is it possible to produce a total order of a set of events stamped with a Lamport time that does not violate any causal relationship?

yes, order them in the Lamport time stamp order

What is the definition of a consistent cut?

if e is in the cut and f happened-before e then f is in the cut

Why is the notion of consistent cut important?

it defines a state that did occur during an execution

What is the definition of a stable global state predicate?

if a system enters a state where the predicate holds true it will remain true in all future states

What is the definition of a unstable global state predicate?

the predicate could hold true in a state but then be false in future states

Give an example of a stable global state predicate.

deadlock

What do we know if we record a snapshot using the algorithm by Chandy and Lamport?

there is a linearizations from the state described by the snapshot and a state that did occur in the execution

Assuming that we collect all state transitions of nodes and have them tagged with vector clocks what can we then do?

for any unstable predicates determine if it was true during the execution

How can we detect that a non-stable predicate definitely was true during an execution?

generate all consistent runs and show that the predicate is true at one point in all

What is the purpose of the marshaling procedure?

to encode application layer structures in an external form

What is a gossip protocol?

A protocol where peers randomly exchange messages to achieve, for example, unreliable multicast.

What is meant by time uncoupling in a communication framework?

Sender and receiver need not be active at the same time.

What is meant by space uncoupling in a communication framework?

A sender does not need to know the name or identifier of the receiver.

What is meant by an idempotent operation?

n operation that can be performed several times with the same effect as being performed once.

What is meant by causal ordering in a communication framework?

If a client is delivered two messages m1 and m2, then m1 could not have been sent by someone after having being delivered m2.

How are arguments passed in Java RMI?

remote objects as reference, all other as copies

Which invocation semantic is provided by Java RMI?

at most once

What level of transparency is provided by method invocation in Java RMI?

access and location transparency