微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-COMP212
时间：2021-05-14
PAPER CODE NO. EXAMINER: Dr. Othon Michail Tel. No. 0151 7950395
COMP212 DEPARTMENT: Computer Science
SECOND SEMESTER EXAMINATIONS 2018/19
Distributed Systems
TIME ALLOWED : TWO Hours
INSTRUCTIONS TO CANDIDATES
Answer ALL TWO questions in Section A. Answer ONE of the two questions in Section B.
If you attempt to answer more questions than the required number of questions (in any section),
the marks awarded for the excess questions answered will be discarded (starting with your lowest
mark).
PAPER CODE COMP212 page 1 of 5 Continued
Section A
Answer ALL TWO questions (A1 and A2) in this section. Section A is worth 60 marks (30
marks for each question).
Question A1
1. Give at least three properties of distributed systems that make them harder to design and
deal with than conventional centralised systems. Then give an example of a real distributed
system and identify in it at least one of the properties that you mentioned before. 5 marks
2. Declare as true (T) of false (F) each of the following statements (1 mark each):
(a) When we say that distributed systems are open, we mean that their source code is freely
accessible by everyone.
(b) In distributed systems, there is no need to achieve scalability with respect to administra-
tive domains, as there are typically only a few service providers.
(c) Asynchronous communication is a scaling technique.
(d) By transparency in distributed systems we mean that the system has been designed in
such a way that we can always observe its internal workings.
(e) A single multiprocessor workstation is a type of distributed system.
5 marks
3. What do we mean when we say that modern distributed systems follow a layered organisa-
tion? What might be a benefit of this type of organisation for application developers? 5 marks
4. What do we mean by “middleware” in distributed systems? Give two examples of middleware
communication mechanisms. 5 marks
5. A client sends a message to a server using Remote Procedure Calls (RPCs). However,
the server is not online when the client sent this message. What will happen to this mes-
sage? 2 marks
6. A client sends a message to a server in a Message Oriented Middleware (MOM) platform.
However, the server is not online when the client sent this message. What will happen to this
message? 2 marks
7. Explain the purpose of each field that you can identify in the URL http://www.csc.liv.
ac.uk:80/intranet.csc.liv.ac.uk/student/ug-handbook.pdf. Describe the name-resolution
procedure that takes place for your Web browser to retrieve the above ug-handbook.pdf
file. 6 marks
PAPER CODE COMP212 page 2 of 5 Continued
Question A2
1. Explain two disadvantages of having a single coordinator managing and servicing a large
distributed system. 4 marks
2. Imagine that you want to resolve the url ftp://pcftp.liv.ac.uk through DNS. Describe with
the help of figures all the name resolution steps that will be involved if (a) iterative and (b)
recursive name resolution is employed for this. Which of the two methods would you prob-
ably prefer if you were initiating the DNS query from a computer based in the USA and
why? 8 marks
3. Give an example of a distributed application whose data (e.g., site, database, etc) should
better be replicated. State two advantages for doing so. Identify an issue that will emerge
after replication is applied. Provide a solution for that issue, explaining why the proposed
solution is best suited for your distributed application. 4 marks
4. Explain the Safety and Liveness conditions that must be satisfied by mutual exclusion algo-
rithms. 4 marks
5. Using an example, demonstrate how a deadlock can arise in transaction processing. 4 marks
6. Name two methods for undoing the actions of an aborted transaction. For one of these
methods explain how it would help an online flight reservation system recover if a customer
gets disconnected from the system server while operating some transaction. 3 marks
7. Consider the remote communication example using a Remote Procedure Call (RPC), de-
picted in the figure.
Briefly describe each of the steps 1 to 6 (highlighted in the figure) that are involved in the
RPC. 3 marks
PAPER CODE COMP212 page 3 of 5 Continued
Section B
Answer ONE of the two questions (B1 or B2) in this section. Section B is worth 40 marks.
Question B1
1. For the LCR algorithm (for leader election in a synchronous directed ring network, of n pro-
cessors)
(a) Give an assignment of unique ids on which LCR sends Θ(n2) messages. Explain your
reasoning. 7 marks
(b) Give an assignment of unique ids on which LCR sends O(n) messages. Explain your
reasoning. 7 marks
(c) In the non-terminating LCR a single processor eventually elects itself and all other pro-
cessors never do so. Describe a modification of the non-terminating LCR in which all
processors eventually terminate and know the id of the elected processor. 6 marks
2. Consider the following distributed system: General undirected (i.e., bidirectional communica-
tion) connected network G = (V ,E) on n = |V | processors. The processors have unique ids
and know in advance the size n of the network but not the diameter D of the network (neither
have any other knowledge about the network). The processors communicate in synchronous
rounds. You are asked to develop a distributed algorithm that will solve the leader election
problem in this setting. In this algorithm, all processors should eventually terminate knowing
who the elected processor is.
• Give an informal description of your algorithm. 6 marks
• Give pseudocode for your algorithm. 6 marks
• Comment about its correctness. 4 marks
• Comment about its complexity (number of rounds and number of messages). 4 marks
PAPER CODE COMP212 page 4 of 5 Continued
Question B2
1. Give a description of the FloodSet algorithm and explain why it correctly solves the agreement
problem in complete networks of n processors when at most f processors may crash (i.e.,
stop) during any execution (and the algorithm knows f in advance). 15 marks
2. Consider three communicating processes, P1, P2, and P3 (each column representing the
evolution of one of these processes over time), depicted in the figure.
0
7
14
21
28
35
42
49
56
63
70
77
84
91
98
105
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
0
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
A
B
C
D
P1 P2 P3
E
The processes run on different machines, each with its own clock running at its own speed.
When the clock has ticked 7 times in process P1, it has ticked 5 times in process P2 and 2
times in process P3. Each clock runs at a constant rate, but the rates are different. At time 4
process P3 sends message A to process P2. When it arrives, process P2 reads 15, and so
on for the other messages B, C, D, and E .
Show how Lamport’s algorithm synchronises the clocks in the described situation.
10 marks
3. Explain why if in a synchronous ring of processors all processors start from exactly the same
state (including the absence of unique ids) then (if the algorithm is deterministic, e.g., cannot
make random choices) it holds that all processors will necessarily forever remain in identical
states (10 marks). Comment on why this implies that it is impossible to develop a deterministic
algorithm that solves the leader election problem in such a setting (5 marks). 15 marks
PAPER CODE COMP212 page 5 of 5 End
学霸联盟
COMP212 DEPARTMENT: Computer Science
SECOND SEMESTER EXAMINATIONS 2018/19
Distributed Systems
TIME ALLOWED : TWO Hours
INSTRUCTIONS TO CANDIDATES
Answer ALL TWO questions in Section A. Answer ONE of the two questions in Section B.
If you attempt to answer more questions than the required number of questions (in any section),
the marks awarded for the excess questions answered will be discarded (starting with your lowest
mark).
PAPER CODE COMP212 page 1 of 5 Continued
Section A
Answer ALL TWO questions (A1 and A2) in this section. Section A is worth 60 marks (30
marks for each question).
Question A1
1. Give at least three properties of distributed systems that make them harder to design and
deal with than conventional centralised systems. Then give an example of a real distributed
system and identify in it at least one of the properties that you mentioned before. 5 marks
2. Declare as true (T) of false (F) each of the following statements (1 mark each):
(a) When we say that distributed systems are open, we mean that their source code is freely
accessible by everyone.
(b) In distributed systems, there is no need to achieve scalability with respect to administra-
tive domains, as there are typically only a few service providers.
(c) Asynchronous communication is a scaling technique.
(d) By transparency in distributed systems we mean that the system has been designed in
such a way that we can always observe its internal workings.
(e) A single multiprocessor workstation is a type of distributed system.
5 marks
3. What do we mean when we say that modern distributed systems follow a layered organisa-
tion? What might be a benefit of this type of organisation for application developers? 5 marks
4. What do we mean by “middleware” in distributed systems? Give two examples of middleware
communication mechanisms. 5 marks
5. A client sends a message to a server using Remote Procedure Calls (RPCs). However,
the server is not online when the client sent this message. What will happen to this mes-
sage? 2 marks
6. A client sends a message to a server in a Message Oriented Middleware (MOM) platform.
However, the server is not online when the client sent this message. What will happen to this
message? 2 marks
7. Explain the purpose of each field that you can identify in the URL http://www.csc.liv.
ac.uk:80/intranet.csc.liv.ac.uk/student/ug-handbook.pdf. Describe the name-resolution
procedure that takes place for your Web browser to retrieve the above ug-handbook.pdf
file. 6 marks
PAPER CODE COMP212 page 2 of 5 Continued
Question A2
1. Explain two disadvantages of having a single coordinator managing and servicing a large
distributed system. 4 marks
2. Imagine that you want to resolve the url ftp://pcftp.liv.ac.uk through DNS. Describe with
the help of figures all the name resolution steps that will be involved if (a) iterative and (b)
recursive name resolution is employed for this. Which of the two methods would you prob-
ably prefer if you were initiating the DNS query from a computer based in the USA and
why? 8 marks
3. Give an example of a distributed application whose data (e.g., site, database, etc) should
better be replicated. State two advantages for doing so. Identify an issue that will emerge
after replication is applied. Provide a solution for that issue, explaining why the proposed
solution is best suited for your distributed application. 4 marks
4. Explain the Safety and Liveness conditions that must be satisfied by mutual exclusion algo-
rithms. 4 marks
5. Using an example, demonstrate how a deadlock can arise in transaction processing. 4 marks
6. Name two methods for undoing the actions of an aborted transaction. For one of these
methods explain how it would help an online flight reservation system recover if a customer
gets disconnected from the system server while operating some transaction. 3 marks
7. Consider the remote communication example using a Remote Procedure Call (RPC), de-
picted in the figure.
Briefly describe each of the steps 1 to 6 (highlighted in the figure) that are involved in the
RPC. 3 marks
PAPER CODE COMP212 page 3 of 5 Continued
Section B
Answer ONE of the two questions (B1 or B2) in this section. Section B is worth 40 marks.
Question B1
1. For the LCR algorithm (for leader election in a synchronous directed ring network, of n pro-
cessors)
(a) Give an assignment of unique ids on which LCR sends Θ(n2) messages. Explain your
reasoning. 7 marks
(b) Give an assignment of unique ids on which LCR sends O(n) messages. Explain your
reasoning. 7 marks
(c) In the non-terminating LCR a single processor eventually elects itself and all other pro-
cessors never do so. Describe a modification of the non-terminating LCR in which all
processors eventually terminate and know the id of the elected processor. 6 marks
2. Consider the following distributed system: General undirected (i.e., bidirectional communica-
tion) connected network G = (V ,E) on n = |V | processors. The processors have unique ids
and know in advance the size n of the network but not the diameter D of the network (neither
have any other knowledge about the network). The processors communicate in synchronous
rounds. You are asked to develop a distributed algorithm that will solve the leader election
problem in this setting. In this algorithm, all processors should eventually terminate knowing
who the elected processor is.
• Give an informal description of your algorithm. 6 marks
• Give pseudocode for your algorithm. 6 marks
• Comment about its correctness. 4 marks
• Comment about its complexity (number of rounds and number of messages). 4 marks
PAPER CODE COMP212 page 4 of 5 Continued
Question B2
1. Give a description of the FloodSet algorithm and explain why it correctly solves the agreement
problem in complete networks of n processors when at most f processors may crash (i.e.,
stop) during any execution (and the algorithm knows f in advance). 15 marks
2. Consider three communicating processes, P1, P2, and P3 (each column representing the
evolution of one of these processes over time), depicted in the figure.
0
7
14
21
28
35
42
49
56
63
70
77
84
91
98
105
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
0
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
A
B
C
D
P1 P2 P3
E
The processes run on different machines, each with its own clock running at its own speed.
When the clock has ticked 7 times in process P1, it has ticked 5 times in process P2 and 2
times in process P3. Each clock runs at a constant rate, but the rates are different. At time 4
process P3 sends message A to process P2. When it arrives, process P2 reads 15, and so
on for the other messages B, C, D, and E .
Show how Lamport’s algorithm synchronises the clocks in the described situation.
10 marks
3. Explain why if in a synchronous ring of processors all processors start from exactly the same
state (including the absence of unique ids) then (if the algorithm is deterministic, e.g., cannot
make random choices) it holds that all processors will necessarily forever remain in identical
states (10 marks). Comment on why this implies that it is impossible to develop a deterministic
algorithm that solves the leader election problem in such a setting (5 marks). 15 marks
PAPER CODE COMP212 page 5 of 5 End
学霸联盟
