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.
Answer the following question.
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.
Answer the following question.
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.
Answer the following question.
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.
Answer the following question.
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.
Answer the following question.
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.
Answer the following question.
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
Knowing the results of a task ahead of time
Q3. In Hadoop YARN, which entity is responsible for sending container requests of its job to the scheduler? ( )
HDFS client
Nimbus daemon
Application Master
Reduce task
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
These answers are for Cloud Computing Concepts Part 1 | Week 5
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 read from a client will be answered eventually.
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: ( )
About 1.7 hours
About 2.4 hours
About 0.07 hours
About 2.4 minutes
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
These answers are for Cloud Computing Concepts Part 1 | Week 5
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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).
These answers are for Cloud Computing Concepts Part 1 | Week 5
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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:
Note: Please enter the numeric value of your answer.
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}.
These answers are for Cloud Computing Concepts Part 1 | Week 5
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
These answers are for Cloud Computing Concepts Part 1 | Week 5
