|
Distributed Computing  This website demonstrates using wikis as teaching and learning tool. The course instructor is also happy to share the teaching materials here with those who find it readable. |
Lecture /
Revision Questions and AnswersA Distributed Computing Lecture by Steven Choy
Final Examination
3 hours, 100 marks
180 minutes, 100 marks
1.8 minutes per mark
~35 minutes to do one question
Scope of Examination
Distributed File SystemsQuestions (a) The design of distributed file systems should support many of the transparency requirements for distributed systems. Describe any three forms of transparency. [6] (b) Compare stateless servers and stateful servers in the context of distributed file systems. [4] (c) Compare NFS and AFS in terms of semantics of file sharing and cache consistency protocol. [4] (d) Explain the technique used in the AFS to addresses the scalability problem of distributed file systems. Discuss the consequence of this technique. [6] Answers
Access transparency enables local and remote resources to be accessed using identical operations. That means it doesn’t matter whether the resources are from local or remote machines — the way to access them should be identical.
Location transparency enables resources to be accessed without knowing their location. Users might need to know the name of the resources but not their location.
Failure transparency enables the concealment of faults, and allows users and application programs to complete their tasks despite the failure of hardware or software components
Concurrency transparency enables several processes to operate concurrently using shared resources without interference between them.
Replication transparency enables multiple instances (copies) of resources to be used to increase reliability and performance without the users or application programmers knowing anything about the replicas. The multiple instances of resources are usually distributed uniformly (through the system) so that users can always find one of the instances close to them.
Performance transparency allows the system to be reconfigured to improve performance as loads vary.
Scaling transparency allows the system and applications to expand in scale without changing the system structure or the application algorithms.
The advantage of stateful servers is their good performance. When there is any error, clients will retransmit their requests, but this time, servers need not re-execute the operations. They simply retransmit the reply from history.
A stateful server saves the processing time and thus its performance is better than a stateless server.
However, stateless servers have simple implementation, especially when we need to recover a server after it has crashed.
Semantics of file sharing: NFS uses UNIX semantics. AFS uses session semantics (No changes are visible until the file is closed).
Cache consistency protocol: NFS uses delayed write policy with cached file validity is checked periodically (30 sec). A timestamp is associated with the cached file for checking validity. AFS use callback promise to check whether the copy of a remote file in the client cache is updated or not. It also informs other clients when the file in the remote server is updated but not in client cache. Callback promise is used in the recovery of a workstation, too.
The scalability problem was addressed by taking a larger amount of work from the server to the client. When a client opens a file under the AFS, the whole file is fetched from the server. All subsequent read and write operations use a local copy stored on a local hard disk. Only when the file is closed—and if it was modified—it is transferred back to server. A consequence of this technique is that AFS presents session semantics rather than UNIX semantics.
TransactionsQuestions (a) Describe the four fundamental characteristics of an atomic transaction. (b) The concurrent execution of transactions may lead, if uncontrolled, to problems. Briefly describe two well-known problems due to uncontrolled and concurrent execution of transactions. (c) What does it mean by transaction serializabilty? (d) Define conflicting operations of two concurrently executed transactions. (e) Define serial equivalence in terms of conflicting operations of two transactions. Answer the following questions based on the information about two transactions T and U. (f) Give two interleavings of transactions T and U that are not serially equivalent. (g) Give two interleavings of transactions T and U that are serially equivalent but not with two-phase locking. (h) Give two interleavings of transactions T and U that are serially equivalent and with two-phase locking. Answers
The four essential properties of transactions are: Atomicity (all or nothingness), consistency, isolation, and durability (indivisibility). Note: 1 mark each for reasonable description of the above four properties.
2 marks each for explaining the following problems: the Lost Update Problem, the Incorrect Summary (inconsistent analysis) Problem, the Temporary Update (uncommitted dependency) Problem.
Transaction Serializabilty: the effect on a database of any number of transactions executing in parallel must be the same as if they were executed one after another
Conflicting operations: When we say that a pair of operations conflicts we mean that their combined effect depends on the order in which they are executed.
Serially equivalent: For two transactions to be serially equivalent, it is necessary and sufficient that all pairs of conflicting operations of the two transactions be executed in the same order at all of the objects they both access.
Concurrency Control Methods and Deadlock in Distributed SystemsQuestions (a) There are three basic methods for controlling concurrent execution of transactions, namely two-phase locking, optimistic concurrency control, and timestamp ordering. Describe the main idea for each of them. (b) Compare two-phase locking method with timestamp ordering method in terms of their strategies for aborting and nature of transactions suitable for them. (c) Wait-die and wound-wait are two practical algorithms for distributed deadlock prevention. Describe the common idea shared by these two algorithms. State one advantage and one disadvantage of wound-wait over wait-die. (d) What is the main difference between deadlock prevention and deadlock avoidance in handling deadlocks in distributed systems? Answers
Strategy for aborting: In timestamp ordering, a transaction aborts immediately once it cannot obey the read and write rules; In two-phase locking, it makes the transaction wait.
Timestamp ordering is good for transactions with predominately READ operations. Two-phase locking is good for transactions with predominately WRITE operations.
When a process is about to block waiting for a resource that another process is using, a higher priority is given to an order process rather than a young one.
Advantage: no process is killed. Disadvantage: a younger process may need to wait for a long time to complete its execution.
Deadlock prevention is to add an algorithm for transaction to follow. It may result in significant overhead and some transactions may abort to prevent a deadlock occurs.
In deadlock avoidance, we do not touch transactions but resources. We want to take care the distribution of the resources and avoid deadlocks by computing when they will happen.
Thanks for ReadingIf you would rather like to have this lecture note in printed format, please click the print action link in the top right corner. If you find any problem in this lecture note, please feel free to reach Steven by steven@findaway.hk |