The Assignment 3 Specification and Marking Criteria
Some Theoretical Issues in Distributed Systems
In the assignment, you are to address some theoretical issues in the area of distributed systems or distributed computing. You will need to demonstrate your understanding of these theoretical issues or competence to apply these theoretical issues. These theoretical issues have been introduced by this unit through the textbook, weekly lectures or tutorials/labs. You will need to review these learning materials to address the following questions and prepare to do personal research if necessary.
Please note: copying from the unit learning materials or internet resources cannot show your understanding of the following issues, but may incur plagiarism or loss of marks. Thus you will need to address the following issues in your own word with proper in-text citations and references.
Question 1
Address the following issues that are related to replication and fault tolerance.
1. Explain the difference between the passive replication model and active replication model.
2. Explain the difference between the crash of a server and the Byzantine failure of a server.
Assume the active replication and passive replication models are available for fault tolerance.
3. If s of s+1 servers crash, explain whether the passive or active model is still fault-tolerant.
4. If s of 2s+1 servers have byzantine faults, explain whether the passive or active model is still fault-tolerant.
Question 2
Recall the internet Domain Name System (DNS), which is detailed in the Week 7 unit contents and practised by Week 8 and Week 9 lab tasks, and answer the following questions.
1. Explain the hierarchical structure/arrangement of the DNS servers.
2. If the Recursive Server-Controlled Navigation is used, explain the workflow when a client sends a name resolution request.
3. If you program/implement a DNS server in Java, what multi-threading strategy will you use? Justify your answer.
Question 3
Address the following issues that are related to security in distributed systems.
1. What is a public key and a private key? Given a public key, is it possible to derive/calculate its private key?
2. Assume that Alice’s public key is available on a web site, describe the simplest way that Bob sends a secrete message to Alice by using Alice’s public key.
3. There is a potential problem caused by the simple use of public key in step (2), describe the problem.
4. Describe why digital certificate can solve the problem in step (2).
Question 4
Read the following scenario and address the following issues that are related to transaction and concurrency control.
Assume that objects a1, a2, and a3 are managed by a server, which provides two operations to operate the objects.
read(a): returns the value of object a write(a, v): assigns the value v to object a Assume that the following two concurrent transactions T and U are performed on these objects. T: read(a2); read(a1); write(a2, a2-25); read(a3); write(a1, a1+52)
U: read(a3); read(a2); write(a2, a2+33); write(a3, a3-26)
Assume that the original values of a1, a2, and a3 are 111, 106 and 125 respectively. Answer the following questions based on the above scenario.
1. If there is no concurrency control, transactions T and U may perform the following interleaving operations on objects a1, a2 and a3. What problem can be caused by the operations? Justify your answer.
T: read(a2); U: read(a3); U: read(a2); T: read(a1); T: write(a2, a2-25); T: read (a3); U: write(a2, a2+33); T: write(a1, a1+52); U: write(a3, a3-26)
2. What requirement must be satisfied in order to avoid the problem?
3. When the above requirement in question (1) is satisfied, what would be the correct values of a1, a2 and a3 after T and U commit?
4. Give an example of possible interleaving operations that can produce the correct values of a1, a2 and a3. Note: no marks is given to this question if the operations are not interleaved.
5. The following is an example to use exclusive locks to solve the problem in question (1). Give your explanation why it can solve the problem.
6. We rearrange T’s operations as follows and keep U’s operations unchanged.
T: read(a2); read(a1); read (a3); write(a2, a2-25); write(a1, a1+52)
If we use the locks as below, what problem would happen?
7. What will be the solution to the problem in question (6)? Give at least two different methods. Submission
You will need to address the above issues in a Microsoft Word document. You must submit your assignment via the online submission system from the unit Moodle site. Any hardcopy or email submission will not be accepted. After the marked assignments are returned, any late submissions will not be accepted.
The Marking Criteria
Marking Criteria Available Marks
Question 1: Replication and Fault Tolerance 8
1. Difference between passive model and active model 2
2. Difference between server crash and the byzantine failure 2
3. Whether passive or active model tolerates server crash 2
4. Whether passive or active model tolerates byzantine failure 2
Question 2: Domain Name System (DNS) 6
1. Explanation of DNS hierarchical structure 2
2. Explanation of sever-controlled navigation 2
3. Explanation of DNS multi-threading strategy 2
Question 3: Security in Distributed System 7
1. Explanation of public and private key 2
2. Encryption by using a public key 1
3. The potential problem of using public key 2
4. How digital certificate solves the problem 2
Question 4: Transaction and Concurrency Control 14
1. Explanation of the problem caused by no concurrency control 2
2. Explanation how to avoid the problem 2
3. The correct values produced by the transactions 2
4. The interleaving operations that can produce the correct values 2
5. Explanation of the given interleaving operations 2
6. Explanation of the problem caused by the locks 2
7. The solutions to the problem in question (6) 2
Sub Total for Assignment 3 35
Late Penalty -1.75 (5% each calendar day, either full or part)
Plagiarism Related Penalty
Total for Assignment 3
GET ANSWERS / LIVE CHAT