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 citation and reference.
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 web 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 currency
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 partial)
Plagiarism Related Penalty
Total for Assignment 3