# Cloud Computing Concepts, Part 1 Coursera Quiz Answers

### Cloud Computing Concepts, Part 1 Week 1 Quiz Answers

#### Quiz 1: Orientation Quiz

Q1. This course includes ____ weekly modules.

• 5
• 6
• 7
• 8

Q2. I am required to purchase a textbook for this course.

• False
• True

Q3.  of the following activities are required to pass the course?

• Complete the weekly homework.
• Complete the programming assignment.
• Complete the Final Exam.
• All the above options

Q4. The following tool(s) will help me use the discussion forums:

• Upvoting posts
• Reporting inappropriate posts
• All of the other options are correct.

Q5. If I have a problem in the course I should:

• Email the instructor
• Call the instructor
• Drop the class
• Report it to the Learner Help Center (if the problem is technical) or to the Content Issues forum (if the problem is an error in the course materials).

#### Quiz 2: Prerequisite Quiz

Q1. The value of 5 + 3 + 77 is _____.

• 77
• 80
• 100
• 85

Q2. The value of 5*3*2 is _____.

• 8
• 15
• 30
• 50

Q3. The value of 5^252 + 3^232 + 77^2772 + 10^2102 is _____.

• 190
• None of these
• 7003
• 6063

Q4. The value of 1+2+3+4+5+6+7+8+9+10 is _____.

• 77
• 55
• Some very large number
• 11

Q5. The value of 21+22+23+24+25 is _____.

• 32
• 65
• 64
• 62

Q6. In a queue data structure, the following items are inserted in the following order: Bob, Alice, Charlie, Eve, Zebra. Then an item is removed from the queue. That item will be _____.

• Eve
• Bob
• None – this will be an error
• Charlie

Q7. In a queue data structure, the following items are inserted in the following order: Bob, Alice, Charlie, Eve, Zebra. Then three items are removed from the queue. Then two further items are inserted: Yelp, Pinion. Then two more items are removed from the queue. The next item removed will be _____.

• Alice
• Yelp
• Charlie
• Bob

Q8. In a stack data structure, the following items are inserted in the following order: Bob, Alice, Charlie, Eve, Zebra. Then an item is removed from the stack. That item will be _____.

• Zebra
• Eve
• Alice
• None – this will be an error

Q9. In a stack data structure, the following items are inserted in the following order: Bob, Alice, Charlie, Eve, Zebra. Then three items are removed from the stack. Then two further items are inserted: Yelp, Pinion. Then two more items are removed from the stack. The next item removed will be _____.

• Charlie
• Alice
• Zebra
• Bob

Q10. You write a C++ program and it’s in two files: myprogram.h, and myprogram.cpp. Then a “process” is _____.

• The compiled version (executable) of this program in action, with stack, heap, registers, code, program counter, etc.
• Any object (.o) files created when this program is compiled
• The executable file created when this program is compiled
• The two C++ files myprogram.h and myprogram.cpp

Q11. Which of the following in a process typically DOES NOT change its value or contents over the lifetime?

• Stack
• Heap
• Code
• Program counter

Q12. For an executing process, which of the following actually executes the instructions of the process?

• CPU
• Memory
• Disk
• Cache

Q13. The CPU can access data stored in different levels of the memory hierarchy. Which of these is the fastest to access?

• Cache
• SSD
• None of these
• Registers

Q14. In an executing process, the program counter points __________.

• To the currently-being-executed line number of low-level (e.g., machine-level) program derived by compiling the C++ program you wrote
• To the bottom of the stack
• To the beginning of the method/function that is currently being executed
• To the currently-being-executed line number of the C++ program you wrote

Q15. Searching for an element in an unsorted array (or vector) of N elements takes time _____.

• O(1)
• O(N/2)
• O(N2)
• O(N)

Q16. Insertion sorting of an unsorted array of size N takes time _____.

• O(N2)
• O(1)
• O(N3)
• O(N)

Q17. You are given an array (vector) of N integers that is sorted in increasing order. You are asked to create a sorted list of the same integers but in decreasing order. You can use any extra arrays, and creating extra arrays takes O(1) time. The most efficient algorithm to achieve this takes time _____.

• O(N)
• O(1)
• O(N2)
• O(N3)

Q18. An algorithm to process a set of N elements takes time (in microseconds) = f(N) = 0.03*N3+1000*N+3. This algorithm is _____.

• O(N3)
• O(N) because 1000 is the highest constant
• O(N2)
• None of these

Q19. You are given a bag with 10 balls, of which 3 are red, 3 are blue, 1 is yellow, 2 are black, and 1 is white. You pick one ball at random from the bag. The probability that this ball is black is _____.

• 0
• 2/5
• 1/5
• 3/10

Q20. You are given a bag with 10 balls, of which 3 are red, 3 are blue, 1 is yellow, 2 are black, and 1 is white. You pick one ball, note its color, put the ball back in the bag, and then pick another ball. The probability that it was the case that the first ball was black and the second ball was red is _____.

• 0.06
• None of these
• 0
• 0.111

Q21. Someone claims that the big O notation does not make sense at all, and they give the following example. An algorithm A that processes an input set of N elements takes time, in seconds, given by T(N) = 10000*N + 0.00001*N^3. They say that the large constant (10000) associated with the N will always dominate over the small constant (0.00001) associated with the N^3. You say that this algorithm A is _____.1

• O(N3)
• Confusing
• O(1)
• O(N)

Q22. Someone writes the following piece of code. What is its Big O complexity?

int k=0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
k++;
}
}

• None of these
• O(1)
• O(N)
• O(N2)

Q23. You are given the following graph. In this graph, each edge has a weight that denotes the time taken to move between those cities (in hours). A “path” is defined as a sequence of edges that can be joined together to create, well, a path from a source node to a destination node. For instance, one path from node E to node D goes like: E to B to C to D. The “path cost” is obtained by adding up the costs of all its constituent edges – for the above example, the path’s cost is 9 + 2 + 4 = 15. There might be multiple paths between a pair of source, destination nodes. Among all these paths, we say that “shortest path” between a source and destination node pair is that path which has the lowest path cost.

Answer the following  : the shortest path that goes from node A to node C passes via which sequence of nodes?

• A to D to C
• Direct edge from A to C
• A to E to B to C
• A to B to C

Q24. In the following graph, the shortest path that goes from node D to node E has what cost?

• 15
• 14
• None of these
• 17

Q25. In a graph containing N nodes, an edge can only join a pair of nodes. The maximum number of edges that can be present in this graph is best described as _____.

• O(N2)
• O(N4)
• O(N)
• O(N3)

### Cloud Computing Concepts, Part 1 Week 2 Quiz Answers

#### Quiz 1: Homework 2

Q1. Given that there are at most two failures at a time in the system, which of the following protocols does NOT satisfy completeness? ( )

• Ring-style heartbeating where each process heartbeats to both its clockwise neighbor and anticlockwise neighbor
• Gossip-style heartbeating
• All-to-all heartbeating
• Ring-style heartbeating where each process heartbeats to only its clockwise neighbor

Q2. Which of the following takes O(log(log(N)) time after a majority of the nodes have received the gossip? ( )

• Pull gossip
• Push gossip

Q3. Alice and Bob are employees in your company who have each been given the task of inventing a failure detection algorithm for an asynchronous system that tolerates 3 simultaneous process failures. You are called to judge whether their protocols satisfy the requirement. Alice’s protocol has each process p randomly pick 3 other processes to send its heartbeats to, and thereafter p periodically sends its heartbeats to these processes. Bob’s protocol has each process p randomly pick 3 other processes to receive heartbeats from, and thereafter each of these 3 picked processes periodically send its heartbeats to p. Note that in each of these protocols, the heartbeats are direct ones rather than gossip-style.

Then, which of the following statements is correct? ( )

• Both Alice’s and Bob’s protocols are complete, i.e., they do not miss any failures.
• Bob’s protocol is complete but Alice’s protocol is not.
• Alice’s protocol is accurate but Bob’s protocol is not.
• Alice’s protocol is complete but Bob’s protocol is not.

Q4. A startup in your home garage is designing a new gossip-style failure detection similar to that discussed in lecture. In this new protocol, at a node (process or server) A, at local time = 140, its local entry for a node C is (address, counter, time) = (C, 340, 133). Tfail = 40. A receives a gossip message from node B containing one heartbeat as (sender-id, heartbeat counter), as shown below. Select the choice below where in all (four) cases, the left entry (heartbeat) leads to the right entry (updated heartbeat at A for C after receiving this heartbeat). ( )

1. (C, 349). ____________
2. (C, 123). ____________
3. (C, 60). _____________
4. (C, 355). ____________
1. = (C, 349), A: (C, 349, 133)
2. = (C, 123), A: (C, 340,133)
3. = (C, 60), A: (C, 340, 133)
4. = (C, 355), A: (C, 355, 133)
1. = (C, 349), A: (C, 349, 140)
2. = (C, 123), A: (C, 340,140)
3. = (C, 60), A: (C, 340, 140)
4. = (C, 355), A: (C, 355, 140)
1. = (C, 349), A: (C, 349, 140)
2. = (C, 123), A: (C, 340,133)
3. = (C, 60), A: (C, 340, 133)
4. = (C, 355), A: (C, 340, 133)
1. = (C, 349), A: (C, 349, 140)
2. = (C, 123), A: (C, 340,133)
3. = (C, 60), A: (C, 340, 133)
4. = (C, 355), A: (C, 355, 140)

Q5. In a heartbeat protocol for failure detection, increasing the timeout (used for declaring a member as failed), without changing any other protocol parameter, results in which of the following? (Select multiple correct answers.) ( )

• Increases false positive rate
• Decreases false positive rate
• Increases detection time
• Decrease in bandwidth

Q6. In a datacenter with 10,000 machines, the MTTF (mean time to failure) of a single server is 36 months. You can assume each month has 30 days. The MTTF (mean time to failure) until the next server fails in the data center is approximately: ( )

• 2.5 minutes
• 0.1 hours
• 2.5 hours
• 2.5 days

### Cloud Computing Concepts, Part 3 Week 3 Quiz Answers

#### 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

Q3. In BitTorrent, a newly joined leecher X is trying to download a file with 6 blocks B1–B6. X has 3 neighbors: A, B, and C. These neighbors are storing the following blocks of the file: A: {B1, B2, B4, B5}; B:{B2, B3, B4, B5, B6}; C:{B1, B2, B6}. Then X will prefer downloading which block first? ( )

• 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

### Cloud Computing Concepts, Part 3 Week 4 Quiz Answers

#### Quiz 1: Homework 4

Q1. A Cassandra deployment with 6 (N1 through N6) nodes across three racks: N1 and N6 are in rack 1; N2 and N5 in rack 2; N3 and N4 in rack 3. The Cassandra ring has the nodes in the following clockwise order: N1, N2, N3, N4, N5, N6. The NetworkTopologyStrategy is attempting to place 2 replicas of a given key. The first replica is placed by the partitioner at N3. The second replica will be placed at node: ( )

• N4
• N5
• N1
• N3

Q2. A Cassandra deployment uses the RackInferringSnitch. Two addresses 1.2.3.4 and 1.2.4.5: ( )

• None of these options
• Are the same machine
• Belong to the same datacenter but different racks
• Belong to different datacenters

Q3. A Cassandra-like key-value store system uses write consistency level of size W and read level of size R. There are N replicas of each key, and N is an even integer that is large enough. You are told that to maintain the strong consistency needed by your application, all conflicting writes must be detected by at least one replica (i.e., any two sets of written replicas must overlap) and a read must return the value of the latest acknowledged write (i.e., a read replica set must overlap with every written replica set). Which of the following combinations does NOT maintain strong consistency? ( )

• W=N/2+1, R=N/2+1
• W=N/2+1, R=N/2-1
• W=N/2+2, R=N/2-1
• W=N-1; R=2

Q4. A BASE system implements implies: ( )

• Sequential consistency
• No consistency
• Meaningful consistency
• Eventual consistency

Q5. Eventual consistency does imply: ( )

• The set of replicas is always trying to catch up and converge to the latest writes
• All replicas of a key will reflect the same value within a time bound
• A read from a client will return the latest written value by that client

Q6. In HBase, in order to guarantee that updates are not lost due to a crash, which of the following needs to be written before an update is added to MemStore? ( )

• Store
• MemStore
• StoreFiles
• HLog

Q7. In Cassandra, when a write comes in at a replica, it is immediately: ( )

• Stored in memory into a Memtable
• Stored in memory into an SSTable
• Stored on disk into an SSTable
• Used to directly update the key-value pair, as expected

Q8. Someone gives you an arbitrary run (execution) trace from a system that implements BASE. It is possible that this run: ( )

• Satisfies sequential consistency
• Satisfies per-key sequential consistency
• All of these options are correct
• Returns a value/ack for every write and read operation issued during the run

Q9. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• In this run (execution), the total number of events summed across all processes is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q10. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

Answer the following question. (1 point)

• The Lamport timestamp of the only process instruction at P3 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q11. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• The Lamport timestamp of the only process instruction at P3 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q12. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• The ending Lamport timestamp at process P1 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q13. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• The process with the highest Lamport timestamp at the end of this run is:
• P1
• P0
• P3
• P2

Q14. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• The number of events with a Lamport timestamp of 9 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q15. A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction.

• The comma-separated list of Lamport timestamps to the last 3 events at P3 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q16. A system using vector timestamps executes the following run. Initially, all four processes start with vectors containing all zeros, i.e., each process starts at 0,0,0,0. An arrow shows a message, and each darkened circle shows a process instruction.

Answer the following question. Note: Please represent your vector timestamps as a comma-separated list (without the brackets).

• The ending vector timestamp at P1 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q17. A system using vector timestamps executes the following run. Initially, all four processes start with vectors containing all zeros, i.e., each process starts at 0,0,0,0. An arrow shows a message, and each darkened circle shows a process instruction.

Answer the following question. Note: Please represent your vector timestamps as a comma-separated list (without the brackets).

• The vector timestamp of the only process instruction at P3 is

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q18. A system using vector timestamps executes the following run. Initially, all four processes start with vectors containing all zeros, i.e., each process starts at 0,0,0,0. An arrow shows a message, and each darkened circle shows a process instruction.

Answer the following question. Note: Please represent your vector timestamps as a comma-separated list (without the brackets).

• The receipt vector timestamp of the last message received at P2 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q19. A system using vector timestamps executes the following run. Initially, all four processes start with vectors containing all zeros, i.e., each process starts at 0,0,0,0. An arrow shows a message, and each darkened circle shows a process instruction.

Answer the following question. Note: Please represent your vector timestamps as a comma-separated list (without the brackets).

• The receipt timestamp of the last message received at P1 is:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q20. A system using vector timestamps executes the following run. Initially, all four processes start with vectors containing all zeros, i.e., each process starts at 0,0,0,0. An arrow shows a message, and each darkened circle shows a process instruction.

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q21. Your boss loves Bloom filters. To impress her, you start implementing one. Your Bloom filter uses m=32 bits and 3 hash functions h1, h2, and h3, where hi(x) = ((x2 +x3)*i) mod m.

In this case, answer the following question.

• Starting from an empty Bloom filter, you’ve inserted the following three elements: 2013, 2010, 2007. Note the bits in the Bloom filter have positions numbered 0 through 31. At the end of these insertions, the positions of the bits that are set, in a comma-separated list are:

A system using Lamport timestamps executes the following run shown in below. Initially, all four processes start with sequence numbers containing all zeros. An arrow shows a message, and each darkened circle shows a process instruction

Q22. Your boss loves Bloom filters. To impress her, you start implementing one. Your Bloom filter uses m=32 bits and 3 hash functions h1, h2, and h3, where hi(x) = ((x2 +x3)*i) mod m.

In this case, answer the following  . ( )

• Starting from an empty Bloom filter, you’ve inserted the following three elements: 2010, 2013, 2007. Now some bits are set. Now, you insert the fourth element 2004. Note the bits in the Bloom filter have positions numbered 0 through 31. The bits whose values will change when the fourth element 2004 is inserted INCLUDE:
• 8
• 0
• 28
• 24

Q23. Your boss loves Bloom filters. To impress her, you start implementing one. Your Bloom filter uses m=32 bits and 3 hash functions h1, h2, and h3, where hi(x) = ((x2 +x3)*i) mod m.

In this case, answer the following  . ( )

• Starting from an empty Bloom filter, you’ve inserted the following elements: 2010, 2013, 2007, 2004. If someone checks for membership of the element 2004, it will be found to be:
• Indeterminate since it was never inserted into the Bloom filter
• In the Bloom filter and not a false positive
• A false negative
• In the Bloom filter and hence a false positive

Q24. Your boss loves Bloom filters. To impress her, you start implementing one. Your Bloom filter uses m=32 bits and 3 hash functions h1, h2, and h3, where hi(x) = ((x2 +x3)*i) mod m.

In this case, answer the following  . ( )

• Starting from an empty Bloom filter, you’ve inserted the following four elements: 2010, 2013, 2007, 2004. If someone checks for membership of the element 3200, it will be found to be:
• In the Bloom filter and hence a false positive
• Not in the Bloom filter
• In the Bloom filter and not a false positive
• Indeterminate since it was never inserted into the Bloom filter

Q25. Calibrations on a recent version of an operating system showed that on the client side, there is a delay of at least 0.5 ms for a packet to get from an application to the network interface and a delay of 1.4 ms for the opposite path (network interface to application buffer). The corresponding minimum delays for the server are 0.20 ms and 0.30 ms, respectively.

What would be the accuracy of a run of the Cristian’s algorithm between a client and server, both running this version of Linux, if the round trip time measured at the client is 6.6 ms?

• 2.1 ms
• 0.3 ms
• 4.2 ms
• 2.4 ms

### Cloud Computing Concepts, Part 3 Week 5 Quiz Answers

#### Quiz 1: Homework 5

Q1. In an asynchronous system, the Paxos protocol:

• Is always safe
• Shows that the Impossibility of Consensus (FLP) result is wrong
• Is always guaranteed to converge within a time bound
• Is always guaranteed to converge

Q2. Someone tells you the consensus protocol discussed in lecture for synchronous systems is wrong because we do not know f (i.e., the number of failures in a group of processes). Your response is:

• You can always set f=N, and the discussed algorithm would then be correct for synchronous systems.
• Yes, the algorithm discussed in lecture is incorrect if we don’t know f.
• f is irrelevant to the discussed consensus algorithm.
• You can always set f=1, and the discussed algorithm would then be correct for synchronous systems

Q3.

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

• The list of all messages (among a-f) captured by the snapshot as a part of channel states is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q4.

For the run of the Chandy-Lamport algorithm, answer the following question.

• Consider all messages such that both its send and receive events are present as part of the state of some process captured by the snapshot. The number of such messages is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q5.

For the run of the Chandy-Lamport algorithm, answer the following question.

• The number of messages such that both its send and receive happen causally after the snapshot is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q6.

For the run of the Chandy-Lamport algorithm, answer the following question.

• The number of messages such that its send happens causally after the snapshot but its receive is before the snapshot is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q7. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

The sequence vector at the end of the run at P0, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q8. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

• The sequence vector associated with the send event of the only multicast that P3 sends out, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q9. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

• The sequence vector at the end of the run at P2, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q10. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

• The total number of multicasts that are buffered across all processes in this entire run is

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q11. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

• The vector of sequence numbers for the only multicast that P0 sends out, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q12. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

• The sequence vector at the end of the run at P2, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q13. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

• The sequence vector associated with the send event of the last (i.e., second) multicast that P1 sends out, as a comma-separated list (without the brackets), is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q14. A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

• The total number of multicasts that are buffered across all processes in this entire run is:

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order.

Q15. A group of 3 processes, P1 through P3, is running virtual synchrony. In this run, initially all three processes have the view {P1,P2,P3}. In this view a single multicast M is sent by process P2. Following this, P2 crashes, and thereafter P1 and P3 deliver a new view containing only {P1,P3}. Which of the following scenarios DO NOT satisfy virtual synchrony? Please select all correct answers, as there are multiple correct answers. (1 point)

• M is delivered by P1 in the view {P1,P2,P3} and by P3 in the view {P1,P3}.
• M is delivered by both P1 and P3 in the view {P1,P2,P3}.
• M is never delivered by P1 or P3.
• M is delivered by both P1 and P3 in the view {P1,P3}.

#### Quiz 2: Final Exam

Q1. A datacenter run by a local company consumed about 1600 kWh in 2014 AD. If only 800 kWh of this 1600 kWh were used in running IT equipment (servers, routers, etc.), then the PUE of this datacenter is: ( )

• 1600
• 0.5
• 800
• 2.0

Q2. Hadoop uses speculative execution to ensure that slow tasks or machines do not lead to a longer job completion time. Speculative execution in Hadoop means: ( )

• Executing multiple copies of a task on different machines
• Guessing the results of the Hadoop job
• Early execution of a task

Q3. In Hadoop YARN, which entity is responsible for sending container requests of its job to the scheduler? ( )

• HDFS client
• Nimbus daemon
• Application Master

Q4. In an asynchronous system, the Paxos protocol: ( )

• Is always guaranteed to converge
• Is always guaranteed to converge within a time bound
• Is always safe
• Shows that the Impossibility of Consensus (FLP) result is wrong

Q5. In Cassandra, when a write comes in at a replica, it is immediately: ( )

• Added to a Bloom filter in memory
• Used to directly update the key-value pair, as expected
• Stored in memory into an SSTable
• Stored in memory into a Memtable

Q6. In Cassandra, a read: ( )

• Is guaranteed to return the value written by the latest write operation
• Reads from the key-value pair in place
• May touch multiple SSTables
• Only reads from one Memtable

Q7. Which of the following is a safety property? ( )

• The trees are green now, but they will turn color.
• A one-way street prevents cars going in both directions.
• A fire will be extinguished eventually.
• If you take a course a sufficient number of times, you will pass.

Q8. Which of the following is a liveness property? ( )

• A car must not drive backwards on the road.
• An airplane will reach its destination.
• The sky will not fall on our heads.
• Fires are dangerous.

Q9. Which of these consistency models is the “strongest” notion of consistency among the given choices? ( )

• Linearizability
• Causal consistency
• No consistency
• BASE consistency

Q10. The best definition of Eventual Consistency says that: ( )

• A write from a client will be answered eventually.
• If reads stop to a key, then all replicas of the key will eventually reflect the same value.
• If writes stop to a key, then all replicas of the key will eventually reflect the same value.

Q11. In a datacenter with 20,000 machines, the MTTF of a single server is 48 months. You can assume each month has 30 days. The MTTF until the next server fails in the datacenter is: ( )

Q12. Someone has designed a Cassandra-Hadoop (YARN)-HDFS hybrid system to run on a set of VMs in Amazon Web Services (AWS) EC2. The YARN scheduler and HDFS use the Cassandra RackInferring snitch (as discussed in lecture). A Mapreduce task (in Hadoop YARN) is running on a cluster with six machines, whose IP addresses are: 101.102.101.102, 101.102.101.103, 101.102.104.101, 101.102.104.102, 101.102.109.108, 101.102.109.109.

A given Map task needs to access as input a block which has replicas on machines 101.102.104.101, 101.102.104.102, 101.102.109.108. The only machines on which new containers can be started are 101.102.101.102 and 101.102.109.109 (the other machines are all full). Then the Map task will be scheduled at: ( )

• 101.102.104.101
• 101.102.101.103
• 101.102.109.109
• 101.102.104.102

Q13. In a gossip-style failure detection protocol, a process p whose local time is 123 has an entry for another process q that reads as (address, heartbeat counter, local time) = (q, 34, 101). At local time 123, p receives a gossip message from a process r that contains the entry (q, 35, 110). What should p do? ( )

• It should update its entry for q to (q, 34, 101).
• It should update its entry for q to (q, 35, 101).
• It should update its entry for q to (q, 35, 123).
• Nothing – the gossip message is from r, not from q.

Q14. You are debugging a key-value store that uses a Bloom filter in its SSTables. The Bloom filter uses two hash functions H1 and H2, where Hi(x) = (x*i) mod 64. In a particular SSTable using m = 64 bits, the following keys are inserted: 1975, 1985, 1995, 2005. Then, checking for membership of the key for 2015 will: ( )

• Make the Bloom filter crash
• Return an answer of “Not present” because the bit mapped by H1 is not set, but the bit mapped by H2 is set
• Return an answer of “Not present” because neither of the bits mapped by H1 and H2 are set
• Return an answer of “Not present” because the bit mapped by H2 is not set, but the bit mapped by H1 is set

Q15. In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period). Then the best value to set the failure detection timeout Tfail is: ( )

• O(Nlog(N))
• O(N)
• O(log(N) – log(log(N)))
• O(log(N))

Q16. In the following figure, four processes exchange unicast messages, and they use Lamport timestamps.

Given the system uses Lamport timestamps, the timestamp of the second message sent by P4 is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q17. the following figure, four processes exchange unicast messages, and they use Lamport timestamps.

Given the system uses Lamport timestamps, the number of events with a timestamp of 9 is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q18. In the following figure, four processes exchange unicast messages, and they use vector timestamps.

Given the system uses vector timestamps, then the timestamp after the last message is received at P2 is [2, x, 2, 2] where x is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q19. In the following figure, four processes exchange unicast messages, and they use vector timestamps.

Given the system uses vector timestamps, the number of events with a timestamp of [1,1,1,1] is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q20. In the following figure, four processes exchange unicast messages.

The number of events that are concurrent with the send event of the second message sent from P4 (M10) is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q21. In the following figure, four processes exchange multicast messages, and they use FIFO ordering.

For FIFO ordering, the vector (of counters) at P2 when it sends its second multicast is [1, x, 1, 1] where x is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q22. In the following figure, four processes exchange multicast messages, and they use FIFO ordering.

With FIFO ordering, the total number of multicasts that are buffered is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q23. In the following figure, four processes exchange multicast messages, and they use causal ordering.

If this run were using causal ordering, the vector of sequence numbers for the only multicast that P1 sends out is [1, x, 1, 1] where x is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q24. In the following figure, four processes exchange multicast messages, and they use causal ordering.

With causal ordering, the TOTAL number of multicasts that are buffered throughout this run is:

In a gossip-style failure detection protocol among N processes, the bandwidth allowed per process is limited to (k*N) bytes per second (or per gossip period).

Q25. In the Chandy-Lamport global snapshot algorithm, a process p sends out an application message AM to process r, and then receives its first marker M from process q, snapshots its local state, and sends out markers on all outgoing channels.

Under what condition might the receive event of message AM be included in this snapshot?

• Only if AM is received at r after r receives its first marker.
• Never – since AM’s send event is a part of the snapshot.
• Only if AM is received at r before r receives its first marker.
• None of these options.

Q26. A group of four processes, P1 through P4, is running virtual synchrony. In this run, initially all processes have the view {P1,P2,P3,P4}. In this view a single multicast M is sent by process P3. Following this, P1 crashes, and thereafter processes P2, P3, and P4 each deliver a new view containing only {P2,P3,P4}. Which of the following scenarios DO NOT satisfy virtual synchrony? Multiple answers may be correct. ( )

• M is delivered by P3 in the view {P1,P2,P3,P4} and by P2,P4 in the view {P2,P3,P4}.
• M is never delivered by P2 or P3 or P4.
• M is delivered by P2 in the view {P1,P2,P3,P4} and by P3,P4 in the view {P2,P3,P4}.
• M is delivered by each of P2, P3, and P4 in the view {P1,P2,P3,P4}.

Q27. Consider a Gnutella topology that looks like a ring, but where each peer has two successors and two predecessors. This means each peer has two clockwise neighbors (the next two in the ring) and two anticlockwise neighbors (the previous two in the ring). If the ring has 100 peers, and a Gnutella Query message with TTL=4 is sent out, the number of peers who receive the Query, excluding the originating peer is: ( )

• 100
• None of these options
• 16
• 32

Q28. In a Chord system, there are 256 points on the ring. Six machines join, with the following peer ids: 45, 95, 145, 195, 245, 254. There is no file replication, and each peer has exactly one successor and no predecessors. The peer with id 195 tries to insert the key with file id 100. The set of peers that the insert message passes through DOES NOT include: ( )

• 195
• 95
• 145
• 245

Q29. In BitTorrent, a new leecher is downloading a file with four blocks (B1 through B4). The leecher has four neighbors W, X, Y, and Z. These neighbor peers have the following blocks: W: (B3). X: (B1, B2, B3, B4). Y: (B1, B3, B4). Z: (B1). Which of the following blocks does the leecher prefer downloading first? ( )

• B2
• B1
• B4
• B3

Q30. A Cassandra-like key-value store system uses write consistency level of size W and read level of size R. There are N=2k+1 replicas of each key, and N is an odd integer. You are told that to maintain the strong consistency needed by your application, all conflicting writes must be detected by at least one replica (i.e., any two sets of written replicas must overlap), and a read must return the value of the latest acknowledged write (i.e., a read replica set must overlap with every written replica set). Further, the traffic is a write-heavy traffic (writes outnumber reads).

Which of the following combinations is the best option (correct and fast) to maintain strong consistency? ( )

• W=k+1, R=k+1
• W=k+2, R=k-1
• W=k+2, R=k
• W=2k; R=2
##### Get all Course Quiz Answers of Cloud Computing Specialization

Cloud Computing Concepts, Part 1 Coursera Quiz Answers

Cloud Computing Concepts, Part 2 Coursera Quiz Answers

Cloud Computing Applications, Part 1: Cloud Systems and Infrastructure Quiz Answers

Cloud Computing Applications, Part 2: Big Data and Applications in the Cloud Quiz Answers