ECS656U Distributed Systems
Distributed Systems代做 | Network | 代写network | angular代做 | scheme作业 | – 这是一个关于Distributed Systems的题目, 主要考察了关于Distributed Systems的内容,是一个比较经典的题目, 涵盖了Distributed Systems/Network/network/angular/scheme等程序代做方面
Summer Examination Period 2020 May Semester B
ECS656U Distributed Systems Duration
This is an open-book exam, which should be completed within 2 hours. You MUST submit your
answers within 48 hours from the exam being released.
You can refer to textbooks, notes and online materials to facilitate your working, but you must
not copy and paste without citing the source.
You MUST complete the exam on your own, without consulting others.
You can chose to either:
a. Type your answers in a Word document (or equivalent), and then convert it to PDF, before
submitting on QM+.
b.Handwrite your answers on blank paper, which must be scanned and converted into a
SINGLE PDF, before submitting on QM+.
Answer FOUR questions.
You MUST adhere to the word limits, where specified in the questions. Failing to do so will
lead to those answers not being marked.
If you answer more questions than specified, only the first answers (up to the specified
number) will be marked. Cross out any answers that you do not wish to be marked.
Examiners:
Dr. Gianni Antichi and Dr. Joseph Doyle
Queen Mary University of London, 2020
Page 2 ECS656U (2020)
Question 1 The following questions are about consensus protocols. (a) Describe consensus, provide two real-world examples on when this is needed in computer networks and provide at least two examples where the Raft and the Paxos protocols differ. [10 marks]
Solution: Consensus is reaching agreement among a group of processes con-
nected by an unreliable communications network.
Example1: Bank transfers. It can happen that money goes out one account but
never arrives at the other one because a server or the network itself somewhere
had failed.
Example2: GoogleDoc.
Example3. GitHub.
Two example: (1) After one consensus Paxos needs to be reset, not Raft. (2) Raft
has a Leader that is always right and propose a value. Paxos does not.[10 marks -
Basic]
Two marks for describing the consensus correctly. Two marks each for providing good
examples in the context of computer networks. Six marks for the examples (three each).
(b) This question is related to Raft. How many roles are defined in the Raft protocol?
Name them and describe each of them. Can you think of a situation where the Leader
machine does not fail but the Raft protocol elect a new Leader? [10 marks]
Solution: 3 Roles.
Follower: is passive but expects regular heartbeats
Candidate: tries to get elected as leader
Leader: replicates its log and send regular heartbeats to maintain leadership
This is the case where the network is really unreliable. One of the follower does
not receive the heartbeat and goes in timeout.[10 marks - Medium]
One mark for mentioning three roles. three marks for providing name and description of
the roles (three marks each). Six marks for providing the required example.
(c)Do Paxos and Raft assure that consensus will be reached in a bounded amount of
time? (explain your answer) [5 marks]
Solution: No. This is the concept of Eventual Liveness.[5 marks - Medium]
Two marks if the answer is correct, three for the explanation.
ECS656U (2020) Page 3
Question 2 The following questions are about Peer to Peer systems. (a) Describe how a peer can search and download content in Napster. Lets assume Peer A starts downloading a file from Peer B using Napster. Lets also assume that at a given time during the download, Peer B disconnects. What Peer A can do now? Does it have to download again the file from another Peer from scratch or not? Motivate your answer. [10 marks]
Solution: Napster is based on Centralised Directory.
The idea is that clients upload a list of files that it wants to share and the server
maintains a global list of: filename,host. In this scenario, a client sends keywords
to the server to search for. The Server returns a list of hosts hosting that specific
content. The Client then pings each host in the list to find transfer rates and finally
fetches file from best host.
Peer A does have to contact another Peer and download the file from scratch.
This is because Napster does not provide chunk based downloading.[10 marks -
Basic]
Five marks for providing the description of Napster operation. Less marks if description
is incomplete. Two marks for explaining that Peer A has to download again the file from
scratch. Three marks for the motivation.
(b) Describe the hybrid scheme that KaZaA uses to satisfy queries, explaining how it
is similar to and different from the Napster and Gnutella approaches. Peer-to-peer
file-sharing programs typically use TCP rather than UDP to transfer the data between
peers. Provide one reason for this. [10 marks]
Solution: Supernodes add hierarchy, allowing regular nodes to direct queries
to the supernodes. The interaction between nodes and their chosen supernode
is similar to Napster, and the query flooding between supernodes is similar to
Gnutella.
TCP because of reliable connection.[10 marks - Medium]
Five marks each subquestion.
(c)Can you explain why the Memory complexity of Napster is O(N) while its communica-
tion overhead is O(1)? [5 marks]
Solution: Napster uses a central directory. The more peers, the more memory
requirements. This makes O(N).
Because Naspster uses a central directly, once a lookup is performed a peer does
know where a given resource is. This makes communication overhead O(1).[
marks - Medium]
Page 4 ECS656U (2020)
Two marks for memory, two marks each for communication, one mark if the explanation is
perfect.
ECS656U (2020) Page 5
Question 3 The following questions are about multiplayer game synchronization. (a) Describe the three types of player interaction and explain how the are handled differently. [10 marks]
Solution: The three types of player interaction are
Player updates Updates that only affect the player such as position updates
Player object interactions A player interacting with a mutable object such as
food is an example of this
Player player interactions A player interacting with another player such as wav-
ing to them (and the various less friendly alternatives)
Player updates may not need to be sent to the server immediately as the server
on needs to be informed if it will affect the view of another player. If the player is
in a isolated location updates may only need to sent to server once it enters the
zone of interest of another player. Player object interactions need to be sent to
the server so that they can take the appropriate action e.g. mark the object as no
longer available but they may not need to sent to other players unless the object is
withing the zone of interest of another player. Player player interaction need to be
communicated to the server and to the other player so that appropriate action can
be taken on the local game state e.g. reduce health if hit by an offensive action
[10 marks - Basic]
One mark for each interaction and one mark for each description. Two marks for each
correct description of how the interactions might be handled differently.
(b) Describe three types of zoning and give an advantage of each type. [10 marks]
Solution: Types of zoning include:
Free format Each zone is connected to other zones via a door or portal and
is isolated from other zones. This does not allow continuous movement
between zones and the area of interest for the player can simply be the
entire zone
Grid The entire game world is divided into a grid of square zones of equal size
and the area of interest for the player is can include objects from multiple
zones if they are on the border
Hexagonal The entire game world is divided into hexagonal zones of equal size
and the area of interest for the player is can include objects from multiple
Page 6 ECS656U (2020)
zones if they are on the border. They are structured so that there is less
overlap between the zones than can be found in the grid system.
Triangles The entire game world is divided into tri angular zones of variable size
and the area of interest for the player is can include objects from multiple
zones if they are on the border. They can be structured in a variety of
patterns depending on the performance requirements of each zone
The advantages of each type are as follows:
Free format This is the simplest system to implement but it does not allow con-
tinuous movement.
Grid This system allows continuous movement and is simpler to implement than
Hexagonal or Triangles.
Hexagonal Hexagons are a good approximation of the circular area of interest of
the player and as there are zones are not as connected as the Grid system
it reduces inter server communication required when players are on the
borders of zones. This improves performance
Triangles This system allows zones to avoid obstacles which reduces the object
replication required for the game copies. The variable size also allows the
system to adapt well to cases where flocking occurs by reducing the size of
zones with numerous player present
[10 marks - Medium]
Two marks for each correct description up to a maximum of five marks and two marks for
each correct advantage up to a maximum of five marks.
(c)You have been asked to select an architecture for a collaborative game. You can
choose the client server architecture, the multi-server architecture and the P2P
architecture. The capital available is limited and architecture should be able to support
up to a million users. Select an architecture and justify your choice. [5 marks]
Solution: The main thing here is that the answer addresses the large number
of users, the limited capital and the collaborative nature of the game. The most
obvious choice is a P2P architecture as this has a low cost base and can support
large numbers of users. It is more susceptible to cheating but as this is a collabo-
rative game cheating is less likely to frustrate users.[5 marks - Advanced]
Two marks for a justification dealing with each issue up to a maximum of five marks.
ECS656U (2020) Page 7
Question 4 The following questions are about Bitcoin and Blockchain. (a) List the four principal components of Bitcoin. Explain what problems would occur if the components were not used for each component. [10 marks]
Solution: The four principal components of Bitcoin are
- Identity
- Transactions
- Record-Keeping
- Consensus
Identify If the identify component was missing there would be no way to deter-
mine the sender and recipient of Bitcoin. It could also affect the anonymity
of the users
Transactions If there were no transactions there would be no records of the
movement of the currency. This would make it impossible to know how
many bitcoins each user possesses. It would also affect the traceability of
the currency which is useful in other application such as supply chains
Record Keeping If there were no record keeping it would be possible to introduce
fraudulent transaction. By arranging transactions in blocks and chaining
them together with hashes it is difficult to introduce fraudulent transaction
into old records and thus, the security of the currency is maintained.
Consensus If there were no consensus it would be impossible to determine which
transactions are valid and which are not. Using proof of work and proof
of stake prevent participants from trying to control the chain for fraudulent
purposes and ensure that it can be used in good faith.
[10 marks - Basic]
One mark for each correctly identified component. 2 marks for each problem up to a
maximum of 6 marks.
(b) What is the hashing function used in Blockchain proof-of-work and list three of its
properties which make it useful for securing the Bitcoin network. Give a potential
consequences to the hashing function not possessing these properties. [10 marks]
Solution: The hashing function used in Block proof-of-work is SHA-256 and
three of its properties which make it useful for securing the Bitcoin network are as
Page 8 ECS656U (2020)
follows:
- If a user has the hash it is computationally difficult to determine the input of the hashing function
- If a user has the hash it is computationally difficult to determine an input that would produce the same hash
- It is computationally difficult to find two inputs which will produce the same hash
A consequence of not possessing these properties would be that miners would be
able to identify a nonce that can satisfy the difficult target quickly. This would make
it possible to subvert the Bitcoin chain without more than 51% of the computation
resources available to all miners. It would essentially hand over control of the
chain to a single participant.
[10 marks - Medium]
One marks for correctly identifying the hashing algorithm. Two marks for each correctly
identified property. Thee marks for a identified consequence.
(c) Describe how blockchain could be used to manage a supply chain. [5 marks]
Solution: Solutions include
- Each item is recorded in the chain with an initial position similar to how bitcoin is initially given to miners.
- Each movement of an item is recorded as a transaction in the chain.
- These transactions are recorded in the chain with a hash making it difficult to edit the movement at a later date
- If the item is part of another larger item or sold to a client this is also recorded as a transaction so its origin can be traced in the event of a problem.
[5 marks - Advanced]
One mark for mentioning creation of items. One mark for mentioning movement of items
as transactions. Two marks for mentioning storing movement in a chain to make editing at
a later date difficult. One mark for mentioning tracing of origin.
End of questions