Cloud Computing Concepts Part 1 | Week 3

Quiz 1: Homework 3

Q1. Napster servers, as discussed in lecture, do not store which of the following? ( )

• Files
• Addresses of some of the peers (clients)
• Addresses of other Napster servers
• File pointers, i.e., (filename, peer address) pairs

Q2. Which of the following Gnutella messages is reverse-routed? ( )

• OK
• Query
• Take
• QueryHit

• B4
• B2
• B6
• B3

Q4. A Pastry DHT has a peer P with the following neighbors. P currently has to route a query to key 101001011010. Which of the following neighbors is the best next-hop for this query? ( )

• 111111100000
• 111001011010
• 101001011000
• 101101011010

Q5. In a Pastry DHT that is locality-aware, the path of a query is very likely to: ( )

• None of the above.
• Take short network jumps in its early hops and long network jumps in later hops.
• Take random-sized network jumps throughout its path
• Take long network jumps in its early hops and short network jumps in later hops

Q6. A Gnutella topology looks like a balanced ternary tree with 4 levels of nodes, i.e., peers, as shown in the picture below. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4 – thus, there are a total of 40 nodes.

If the root node (Level 1) sends a Query message with TTL=2, then what are the number of nodes receiving the Query message, not including the originating node? Enter your answer as a numeric value in the text box below. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q7. A Gnutella topology looks like a balanced ternary tree with 5 levels of nodes, i.e., peers. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4, which in turn each have 3 children at Level 5 – thus, there are a total of 121 nodes.

If a leaf (Level 5) node sends a Query message with TTL=2, then what are the number of nodes receiving this message, not including the originating node? Enter your answer as a numeric value in the text box below. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q8. A Gnutella topology looks like a balanced ternary tree with 5 levels of nodes, i.e., peers. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4, which in turn each have 3 children at Level 5 – thus, there are a total of 121 nodes.

If a child of the root (i.e., a Level 2 node) sends a Query message with TTL=5, then what are the number of nodes receiving the Query message, not including the originating node? Enter your answer as a numeric value in the text box below. ( )

Q9. A Gnutella topology looks like a balanced ternary tree with 4 levels of nodes, i.e., peers, as shown in the picture below. Thus, there is one root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4 – thus, there are a total of 40 nodes.

If the originating node of the Query is a leaf (Level 4 node), what is the minimum TTL to ensure all nodes in the system receive the Query? Enter your answer as a numeric value in the text box below. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q10. In a Chord ring using m = 8, nodes with the following peer ids (or node ids) join the system: 45, 32, 132, 234, 99, 199. What node id is the file with id 120 stored at (assuming only one replica)? Enter your answer as a numeric value in the text box below. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q11. In a Chord ring using m = 8, nodes with the following peer ids (or node ids) join the system: 45, 32, 132, 234, 99, 199.

What is the successor of node 199? Enter your answer as a numeric value in the text box below. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q12. In a Chord ring using m = 9, nodes with the following peer ids (or node ids) join the system: 1, 12, 123, 234, 345, 456, 501.

Node 234 initiates a search (query) for key 10. What is the comma-separated list of all nodes traversed by this query, including the final destination (including both originating node and final node)?

Use the text box below to enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q13. In a Chord ring using m = 8, nodes with the following peer ids (or node ids) join the system: 45, 32, 132, 234, 99, 199. When all finger tables and successors have converged, what is the comma-separated list of nodes traversed by a query originating from node 45 intended for the key 12 (include both originating node and final node)?

Use the text box below to enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

enter your answer as a sequence of numeric values with each numeric value separated by a comma. Please ensure you enter the node ids in the order traversed, and include both starting and ending nodes in the sequence. ( )

Q14. In a Chord ring using m = 9, nodes with the following peer ids (or node ids) join 
the system: 1, 12, 123, 234, 345, 456, 501. The successor of node 501 is: ( )

Nothing – 501 does not have a successor since it is the end of the ring

• 12
• 1
• 123
• 456

---

---