Cloud Computing Concepts: Part 2 Quiz Answers

Cloud Computing Concepts: Part 2 Week 1 Quiz Answers

Quiz 1: Orientation Quiz

Q1. This course includes ____ weekly modules.

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

False
True

Q3. Which 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
Following a thread
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: Homework 1

Q1. A ring of processes with the following node ids in clockwise order is running the Ring Election protocol discussed in lecture: 10, 3, 2, 4, 7, 6, 8, 9, 5 (this list does not include the failed leader). The process with id 2 initiates a new leader election run, in order to elect the highest-id process as leader. Assuming no further failures, the total number of messages incurred until the protocol terminates is: ( )

Q2. Your colleague proposes a Modified version of the Ring Election algorithm discussed in lecture. The only design decision that is different in this modified version is that the initiator node (instead of the would-be coordinator node) is the one who keeps track of Election messages; the initiator also waits for an unmodified “Election” message to circulate once around the ring – when it receives this, the initiator then forwards the “Elected” message, and subsequently stops the Elected message when it circulates once around the ring. This modified algorithm: ( )

Just does not work.
Is not live when the initiator process fails
Is not live even when there are no failures.
Is safe even under failures.

Q3. In a Google Chubby system of 6 servers, what is the minimum size of quorum sets? ( )

Q4. Someone designs a Maekawa-style mutual exclusion system for 6 processes with the following voting sets. P1: {P1,P2,P4,P6}; P2: {P1,P2,P3,P4}; P3: {P1,P2,P3,P5}; P4: {P1,P2,P4,P5}; P5:{P3,P4,P5,P6}; P6:{P1,P3,P5,P6}. The resulting algorithm: ( )

Is Live but not Safe
Is both Live and Safe
Is neither Safe nor Live
Is Safe but not Live

Q5. In a synchronous system of N=12 processes running the Bully algorithm (with attribute = id) for leader election, the coordinator as well as the next (N/3-1), or 3, processes with the next highest ids after the coordinator fail simultaneously (at the same instant of time). Thereafter, no more processes fail. In this version of the Bully algorithm, the old (failed) coordinator is also sent Election messages. Then the exact worst-case (maximum) number of messages that are sent by the Bully algorithm until the leader election algorithm has run completely is: ( )

processes with the next highest ids after the coordinator fail simultaneously (at the same instant of time). Thereafter, no more processes fail. In this version of the Bully algorithm, the old (failed) coordinator is also sent Election messages. Then the exact worst-case (maximum)

Q6. A new open-source system (intended for asynchronous systems) uses a leader election protocol in a group of N processes that is akin to the following (you can assume that no additional processes join, fail from, or leave the group during the election). When a process discovers the leader has failed, it initiates an election. It sends out an “ElectMe!” message to all N-1 processes including itself. Every process has a unique priority (e.g., its id), and the ElectMe! message contains this priority. When a process receives an ElectMe! Message (notice that a process has to receive its own ElectMe! too and vote on it), immediately it does the following: it compares its own priority with that in the message. If its own priority is higher, it multicasts out an ElectMe! message to everyone; otherwise it responds back with a unicast “Vote” message. However, once a process has sent out a Vote message, it cannot send out any more Vote or ElectMe! Messages (i.e., a process can vote at most once). A process also can send out at most one ElectMe! message. Finally, when a process receives at least 2N/3 (i.e., a super-majority of N) Vote messages, it declares itself as a leader.

There may be multiple correct answers below. Given that safety requires only the highest-priority process to be elected and everyone to know about this new leader, this protocol is (MULTIPLE answers): ( )

Not enough information to reason about safety
Safe
Not safe
Not live

Q7. A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4, and P5 initiate requests for the critical section. If the Lamport timestamps of the requests from P2, P4, P5 are respectively 32, 10, 21, then the process that gets access to the critical section first is: ( )

P2
P4
P5
P3
None – the situation is deadlocked.
P1

Q8. A group of 4 processes P1 through P4 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, two processes P1 and P3 initiate requests for the critical section.If the Lamport timestamps of the requests from P1 and P3 are respectively 110 and 110, then the process that gets access to the critical section first is: ( )

P1
None – the situation is deadlocked.
P2
P3

Q9. A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4 and P5 initiate requests for the critical section. Assuming all messages are unicast messages, the total number of messages exchanged until all of P2, P4, P5 release their critical section is: ( )

Q10. A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4, and P5 initiate requests for the critical section. If the Lamport timestamps of the requests from P2, P4, P5 are respectively 21, 21, 21, then the process that gets access to the critical section first is:

Cloud Computing Concepts: Part 2 Week 2 Quiz Answers

Quiz 1: Homework 2

Q1. In an object-based system, object C1 has a method C1.M1 that calls object C2’s method C2.M2. In which of the following cases is this call NOT a Remote Method Invocation? There may be MULTIPLE ANSWERS. ( )

Marshaling and unmarshaling are used when C1.M1’s arguments are communicated to C2.M2.
C1 and C2 reside in the same process.
C1 and C2 reside in different processes, and the two processes are running on different hosts.
Marshaling and unmarshaling are used when C2.M2’s results are communicated to C1.M1.

Q2. A program stores the integer 456789 in memory. You are told that this translates to, in hexadecimal format, 0x6F855. In a little endian architecture, this integer 456789 will be stored in memory as: ( )

(lowest address byte) 00-55-F8-06 (highest address byte)
None of these options
(lowest address byte) 45-67-89 (highest address byte)
(lowest address byte) 55-F8-06-00 (highest address byte)

Q3. Some operations are called idempotent operations because they can be repeated multiple times without any side effects. RPCs that implement idempotent operations are a good fit for at-least-once call semantics. Which of the following functions is NOT idempotent? In the following, y is a local variable held at the server executing the called function, while x is an argument passed by the calling function. ( )

void f(int x) { y = 3; }
int f(int x) { y = x; return (x+1); }
int f(int x) { y = 1; return y; }
int f(int x) { y = y+x; return 1;}

Q4. The C in ACID stands for: ( )

Commission
Coldness
Consistency
Causality

Q5. Someone proposes a new transaction management system that assigns unique integer ids to objects. It uses exclusive locking of objects for concurrency control. The system restricts transactions to acquire locks only in increasing order of object id. This system will: ( )

Deadlock
Either deadlock or not, depending on other details of the system.
Never deadlock

Q6. Which of the following is NOT an optimistic concurrency control technique? ( )

Never check for consistency violations until commit time; if inconsistency is detected abort transaction
Timestamp Ordering technique
Multi version concurrency control
Two-phase locking with read-write locks

Q7. In a system supporting read-write locks, which of the following is FALSE? ( )

A transaction T can acquire a read lock on object O only if no other transaction is currently holding a write lock on object O.
A read lock on object O held by transaction T cannot be promoted if another transaction U holds a write lock on any other object O2.
A read lock on object O held by transaction T can be promoted only if no other transaction is currently holding a read lock on object O.
A write lock on object O held by transaction T can be shared concurrently with a read lock held by another transaction U on a different object O2.

Q8. With a per-replica availability of 1 Nine, what is the minimum number of replicas you need in order to get at least 5 Nines availability for an object? Please enter your answer in numeric value. ( )

With a per-replica availability of 1 Nine, what is the minimum number of replicas you need in order to get at least 5 Nines availability for an object? Please enter your answer in numeric value. ( )

Q9. In a two-phase commit run for transaction T involving 13 servers S1 through S13, all servers other than S8 respond back with a Yes message in the first phase (after receiving the Prepare message from the transaction coordinator), but the coordinator has not yet timed out for the replies. In which of the following cases will the two-phase commit run decide to commit the transaction? There may be MULTIPLE answers.( )

S8 receives the Prepare message but realizes that updates done by transaction T in S8’s memory are corrupted, so it responds back with a “No” to the coordinator.
S8 crashes during the first phase just before it receives the Prepare message, and it does not recover for a long time.
S8 crashes after it sends back a Yes message in response to the coordinator’s Prepare message, and the coordinator receives the Yes message before the timeout. S8 does not recover for a long time.
S8 crashes before the first phase and does not recover for a long time.

Q10. The version of Cassandra discussed in C3 Part 1, considering the group of replicas but excluding the coordinator, implements per key-value pair: ( )

Active replication
None of these options
Passive replication

Q11. Below you are shown a set of transactions and their operations in the order they are executed in real time.

Transaction T	Transaction U
openTransaction
	openTransaction
Read(x)
	Write(x,22)
	Write(y,77)
Read(x)
Write(y,11)
commit
	commit

Not serially equivalent
Serially equivalent
None of these options

Q12. Two transactions T1 and T2 have instructions as follows (a and b are variables at the server):

T1: write(a, foo, T1); read(b, T1); read(a, T1);
T2: read(b, T2); write(b, bar, T2); write(a, baz, T2);

Above, write parameters are the variable name, variable’s new value to be written, and the transaction executing the write. Read parameters are the variable name and the transaction executing the read. Consider the following interleaving: read(b, T2); write(b, bar, T2); write(a, foo, T1); read(b, T1); write(a, baz, T2); read(a, T1). This execution is: ( )

Not serially equivalent
None of these options
Serially equivalent

Q13. Two transactions T1 and T2 have instructions as follows (a and b are variables at the server):

T1: write(a, foo, T1); read(b, T1); read(a, T1);
T2: read(b, T2); write(b, bar, T2); write(a, baz, T2);

Above, write parameters are the variable name, variable’s new value to be written, and the transaction executing the write. Read parameters are the variable name and the transaction executing the read. Consider the following interleaving: write(a, foo, T1); read(b, T2); write(b, bar, T2); read(b, T1); write(a, baz, T2); read(a, T1). This execution is: ( )

None of these options
Not serially equivalent
Serially equivalent

Q14. Below, you are shown a set of transactions and their operations in the order they are executed in real time.

Transaction T	Transaction U	Transaction V
openTransaction
		openTransaction
		Read(x)
		Read(y)
	openTransaction
	Write(x,22)
	Read(y)
		Read(x)
	Read(y)
		Read(y)
	commit
		Read(x)
		Read(y)
Read(x)
Write(y,11)
commit
		commit

This execution is:

Serially equivalent
None of these options
Not serially equivalent

Q15. Two transactions T1 and T2 have instructions as follows (a and b are variables at the server):

T1: write(a, foo, T1); read(b, T1); read(a, T1);
T2: read(b, T2); write(b, bar, T2); write(a, baz, T2);

Above, write parameters are the variable name, variable’s new value to be written, and the transaction executing the write. Read parameters are the variable name and the transaction executing the read. Consider the following interleaving: read(b, T2); write(a, foo, T1); read(b, T1); read(a, T1); write(b, bar, T2); write(a, baz, T2). This execution is: ( )

Serially equivalent
Not serially equivalent
None of these options

Cloud Computing Concepts: Part 2 Week 3 Quiz Answers

Quiz 1: Homework 3

Q1. In Storm, which of the following entities processes data? ( )

Stream
None of these options
Bolt
Tuple

Q2. Small world networks have: ( )

Low clustering coefficients and long path lengths
High clustering coefficients and short path lengths
None of these options
High clustering coefficients and long path lengths

Q3. Which of the following represents a power-law graph, when one plots the degree on the x (horizontal) axis and the number of vertices with degree x on the y (vertical) axis? ( )

Both x and y axes are logarithmic, and the plot is a straight downward sloping line.
The x axis is linear and the y axis is logarithmic, and the plot is a straight downward sloping line.
Both x and y axes are linear, and the plot is a straight downward sloping line.
None of these options

Q4. Which of the following is FALSE? (Choose “None of these options” if you think none of the other 3 options are FALSE.) ( )

None of these options
A graph with exponential degree distribution is heavy-tailed.
Heavy-tailed degree distributions have some vertices with very high degree.

Q5. In a single processor system, switching from one task to another incurs an extra time overhead, called a context switch. Typical context switch overheads in some recent Intel processors are a few 10s of nanoseconds. Which of the following scheduling algorithms will have the highest total context switch overhead for a given workload (consider the case where all jobs have arrived at time 0)? ( )

Priority, with no preemption
Round robin
Shortest task first
Last in first out

Q6. Which of the following is FALSE about Hadoop Capacity Scheduler, as discussed in lecture? ( )

It uses FIFO scheduling, e.g., within each queue.
It uses shortest job first scheduling and is thus optimal.
Normally it does not allow task preemption.
It can use a hard limit and a soft limit.

Q7. You are implementing a variant of Storm where you have a few types of grouping available (some of them similar to Storm). Now at a given bolt B you’re trying to do a join (cross-product) of two incoming streams S1 and S2. S1 is the stream of incoming tweets on Twitter, while S2 is the stream of new accounts being created on Twitter.

Now, among the tasks of B (which is parallelized), which of the following grouping combinations would you use? ( )

Shuffle grouping for S1, and All grouping for S2
Shuffle grouping for both S1 and S2
Shuffle grouping for S2, and All grouping for S1
All grouping for both S1 and S2

Q8. You are implementing a variant of Storm where you have a few types of grouping available (some of them similar to Storm, some of them new). Now you write a topology (for this Storm variant) that calculates Wordcount on a given dataset. The topology consists of a spout B1, which sends sentence tuples to a bolt B2 that generates <word, 1> tuples, which in turn sends data to a bolt B3 that sums up all <word, i> tuples.

For bolt B3, which of the following groupings would be the most preferable, in order to be correct, efficient, and also balance load: ( )

Fields grouping which uses consistent hashing underneath among tasks of B3, by hashing the first element (word) of the tuple
Round-robin among tasks of B3
All grouping among tasks of B3, like in Storm
Fields grouping which uses consistent hashing among tasks of B3, by hashing the entire tuple

Q9. Your colleague has built a new distributed graph processing system that uses the Gather-Apply-Scatter philosophy and where vertex programs are run. She has a large Web graph on which she wants to run PageRank. In this graph in which each vertex is a page, while links between pages are directed edges denoting if a page links to another, someone has written the following gather, apply, and scatter programs.

Gather: each page P gathers all other page’s PageRanks

Apply:

To compute PageRank of vertex P

acc = 0;
for each page Q that is an in-neighbor of P do:
acc = acc – Q.PageRank/Q.degree;
end for
P.PageRank = 0.85 * acc + 0.15;

Scatter: Send page P’s PageRanks to all other pages.

Which of the following are errors (with respect to both correctness and efficiency) in the above pseudocode (MULTIPLE answers):

In the for loop, the value of acc should be increased (+ instead of -) by “Q.PageRank/Q.degree”
Gather should only gather the PageRanks of P’s neighbors in the graph, not all other pages in the graph
There are no errors in this pseudocode.
Scatter should only send PageRank of P to P’s neighbors, and not all other pages

Q10. In order to make a graph processing engine faster, your colleague wants servers to be able to execute the Apply phase before the Gather phase is completed. This can be done (MULTIPLE answers): ( )

Never
If the Scatter phase is not started for vertices whose Gather phases’ output (i.e., their respective neighbor information) has not been completely received
Always
If the Apply phase is applied only for vertices whose neighbors’ values have been completely received (i.e., their respective Gather phases are completed)

Q11. In lecture we converted an extended ring graph into a random graph. If one does the reverse, what would happen? That is, if one takes a random graph and slowly starts to convert edges one by one into extended-ring edges (the ring is a virtual ring with vertices consistently hashed on to it) so that each changed edge goes from a vertex to a nearby node in the ring, then (MULTIPLE ANSWERS): ( )

Average path length increases
Neither clustering coefficient nor average path length change
Clustering coefficient increases
Clustering coefficient decreases

Q12. In a single processor system, five tasks arrive simultaneously, with the following known run-times: 10 s, 15, s, 4 s, 15 s, 23 s. What is the lowest average completion time for this task set? ( )

35.5 s
30.0 s
32.5 s
31.6 s

Q13. a single processor system, seven tasks arrive simultaneously, with the following known run-times: 5 s, 4 s, 4 s, 3 s, 2 s, 1 s, 1 s. What is the lowest average completion time for this task set? ( )

8.5 s
10.2 s
20 s
9.5 s

Q14. A system using the Dominant Resource Fairness scheduling strategy receives the following two jobs. Job 1 requires for each task <1 CPU, 4 GB RAM>, while Job 2 requires for each task <3 CPUs, 1 GB RAM>. The system has a total of 36 CPUs and 72 GB of RAM. Which of the following allocations satisfies Dominant Resource Fairness? ( )

8 tasks to Job 1, 8 tasks to Job 2
12 tasks to Job 1, 8 tasks to Job 2
12 tasks to Job 1, 12 tasks to Job 2
8 tasks to Job 1, 12 tasks to Job 2

Q15. A system using the Dominant Resource Fairness scheduling strategy receives the following two jobs. Job 1 requires for each task <1 CPU, 3 GB RAM>, while Job 2 requires for each task <3 CPUs, 2 GB RAM>. The system has a total of 20 CPUs and 40 GB of RAM. Which of the following is TRUE? ( )

Dominant Resources Fairness does not apply here.
Both Job 1’s and Job 2’s dominant resource is RAM.
Job 1’s dominant resource is CPU, while Job 2’s dominant resource is RAM.
Job 1’s dominant resource is RAM, while Job 2’s dominant resource is CPU.

Cloud Computing Concepts: Part 2 Week 4 Quiz Answers

Quiz 1: Homework 4

Q1. A Unix-style file system read does not specify which offset in the file to start reading from. This is because this file system uses: ( )

One read-write pointer for each file descriptor, which can be advanced only via the lseek call
One read-write pointer for each file descriptor, which is automatically advanced upon a read
A read-write pointer for the system, which is automatically advanced upon a read
One read-write pointer for each file, which is automatically advanced upon a read

Q2. A distributed file system does not typically use read-write pointers. The reasons for this DO NOT include: ( )

Stateless servers
Read-write pointers are buggy
Repeatability of operations by clients without any side effects
Idempotence of operations

Q3. “Locality of access” (or “locality of reference” or even “locality of interest”) refers to the fact that: ( )

File pages that were accessed recently will be accessed soon in the future.
There are many more read operations on a file than a write.
File pages are accessed with uniform frequency.
None of these options

Q4. Which of the following principles is AFS NOT based on? ( )

Most files are accessed simultaneously by multiple clients.
Most file accesses are sequential.
Most files are small.
There are more file reads than file writes.

Q5. In a distributed shared memory system, the best value to set a page size to should be: ( )

Very small
Very large
Much larger than locality of interest
At or slightly larger than locality of interest

Q6. In a wireless sensor network, in-network aggregation is important because (select the best option): ( )

Transmitting raw values to the base station via a spanning tree consumes a lot of power.
Communicating directly with the base station may overload the base station if there are many sensors.
All of these options are correct.
Transmitting raw values to the base station directly consumes a lot of power.

Q7. In an NFS system, the freshness interval is set to 30 s. At time 10am:12min:25s, a client process with pid 356 accesses a locally cached copy of a file block, for which the client stores a last-modified timestamp of 10am:11min:35s, and the file block was last validated by the client at 10am:12min:3s. At the server, the last-modified timestamp of the file block is 10am:12min:4s. Then, the NFS client will: ( )

Serve the file block from the locally cached copy at the client
This situation cannot arise.
Fetch the server’s last-modified timestamp but not fetch the file block from the server
Fetch the file block from the server

Q8. In an NFS system, the freshness interval is set to 3 s. At time 10am:12min:25s, a client process with pid 356 accesses a locally cached copy of a file block, for which the client stores a last-modified timestamp of 10am:11min:35s, and the file block was last validated by the client at 10am:12min:3s. At the server, the last-modified timestamp of the file block is 10am:12min:4s. Then, the NFS client will: ( )

This situation cannot arise.
Serve the file block from the locally cached copy at the client
Fetch the server’s last-modified timestamp but not fetch the file block from the server
Fetch the file block from the server

Q9. A distributed shared memory system, using the invalidate approach, contains 4 processes P1 through P4. Currently, a page P is stored in read mode at processes P2 and P4, and P4 is the owner. A read from P1 will result in: ( )

P1 fetching a copy of the page from either P2 or P4, and P4 remains the owner
P1 reading the page P from its local cache
None of these options
P2 and P4’s copies both are invalidated

Q10. A distributed shared memory system, using the invalidate approach, contains 4 processes P1 through P4. Currently, a page P is stored in read mode at processes P2 and P4, and P4 is the owner. A write from P3 will result in: ( )

P3 fetching a copy of the page from either P2 or P4, and then P3 can write P while P2 and P4 are reading P
P3 invalidating the copies of P at P2 and P4, P3 fetching page P from P2 or P4, and then P3 becoming owner of P in write mode
P3 will be given access only in read mode until P2 and P4 are done with their reads
None of these options

Cloud Computing Concepts: Part 2 Week 5 Quiz Answers

Quiz 1: Homework 5

Q1. A file system design maintains per-user lists of files and directories they are allowed to access along with permissions for each. This approach is called: ( )

Access Control Lists
Access Control Matrix
None of these options
Capabilities

Q2. A file system design maintains, for each file or directory, the list of all users who are allowed to access it, along with permissions for each. This approach is called: ( )

Access Control Matrix
Capabilities
None of these options
Access Control Lists

Q3. Which of the following is true of public-private key (asymmetric) cryptography (select the best option)? ( )

Anything encrypted with a private key can be decrypted only with the matching public key.
All these options are true.
In a public-private key pair, the public key and private key should be different.
Anything encrypted with a public key can be decrypted only with the matching private key.

Q4. Alice needs to send a message to Bob. She creates the message and then encrypts it with Alice’s private key. She then sends this to Bob, knowing that Bob is the only one who will be able to decrypt it. Then: ( )

This does not work, as Alice should have instead used Bob’s private key to encrypt the message.
This does not work as the message is open to violation of confidentiality since anyone with Alice’s public key can decrypt the message.
This does not work, as Bob cannot decrypt the message since he does not have Alice’s private key.
This works, as Bob is the only principal who can decrypt this message.

Q5. In authentication systems, a “ticket”: ( )

Can be issued by one client to another but cannot be issued by a third party server
Is a signature
Is a way of direct authentication between two clients
Contains encrypted information, such as a shared key, for a pair of clients to communicate with each other over an insecure channel

Q6. While creating a digital signature, one should hash the message first and then encrypt it because: ( )

Hash is fast and its output is small, thus the encryption needs to work on only a small piece of data.
One cannot encrypt a raw message – it needs to be hashed first.
Otherwise decryption would not work
That’s how it’s done, people!

Q7. In a digital certificate given by a credit card company to your phone (e.g., Apple Pay or Google Wallet), the following fields are present: name, credit card number, CVV number (3 digits on back of card), issuing bank (MasterCard, Visa, etc.), certificate type (credit or debit card). The signature is constructed by adding (or mixing) the following fields together and then encrypting the result with the private key of the issuing authority: name, credit card number, CVV number. The entire certificate is sent in plain text.

In this approach, an attacker: ( )

Can modify the certificate type without invalidating the certificate
Can modify any part of the entire certificate without invalidating the certificate
Can modify the hash without invalidating the certificate
Can modify the CVV number without invalidating the certificate

Q8. Alice would like Charlie to be able to access Alice’s file, and any other principal should be able to verify this certificate. Alice creates a digital certificate and includes a digital signature therein. The digital signature should use encryption using: ( )

Charlie’s private key
Alice’s public key
Alice’s private key
Charlie’s public key

Q9. When a datacenter outage starts, which of the following factors typically contributes to the outage being prolonged (select the best option)? ( )

All of these options
Existing and undiscovered bugs
Incoming traffic does not stop
Aggressive behavior among processes, e.g., re-mirroring of data without backoff

Q10. Which of the following approaches will likely NOT directly reduce the downtime suffered by customers or applications due to a datacenter outage? ( )

Better documentation by the provider, especially of steps to take in case of an outage
Better and more comprehensive testing
Replication of data and services across providers
Providing frequent updates and post-mortems to customers

Quiz 2: Final Exam

Q1. Election in Google’s Chubby system uses a concept known as a “Master lease”. A master lease is best explained as:

Once a leader is elected, it is elected forever.
Once a leader is elected, other processes promise to consider it leader for a minimum time, after which, if the leader remains alive, it can renew the master lease and thus remain leader.
Once a leader is elected, other processes promise to consider it leader for a minimum time, after which it is forced to give up its leadership role.
The master lease is a token that is passed around a virtual ring – whoever has the token currently is the leader.

Q2. The I in ACID stands for the fact that: ( )

A transaction must commit all its updates or none of them.
A transaction must make consistent changes to the server side objects.
Some transactions will eventually be inconsistent and thus need to abort.
Transactions must not read or write each other’s non-committed updates.

Q3. In Storm, a bolt (MULTIPLE ANSWERS): ( )

May output tuples
None of these options
Is a stream of data
Can be parallelized into multiple tasks

Q4. Distributed graph processing systems (like Pregel) use the Gather-Apply-Scatter paradigm. Scatter refers to: ( )

Calculating the new value of the vertex from its old value and the values of its neighbors
Fetching the value of the vertex from other servers
Fetching values of a vertex’s neighbors from other servers
Sending the new value of the vertex to the vertex’s neighbors at other servers

Q5. A user creates a file F and then hard links it twice from two other directories. Then, the user deletes F from one of these directories. The file F: ( )

Will not be deleted as its reference count now is 2
Will have a reference count of 0 but not be deleted right away
Will not be deleted as its reference count now is 1
Will not be deleted as its reference count now is 3

Q6. As one takes an extended-ring graph and progressively turns edges into random edges (without changing the number of edges), the following happens (MULTIPLE ANSWERS): ( )

Clustering coefficient and average path length remain unchanged
None of these options
Average path length decreases quickly when only a few edges have been randomized, while clustering coefficient decrease needs more edges to be randomized
Clustering coefficient and average path length decrease

Q7. The security policy of integrity combats the security threat of: ( )

Leakage
Tampering
DDOS attacks
None of these options

Q8. Your colleague claims that the following are all security policies and challenges you to find the mechanism among them. Identify it. ( )

Availability
Encryption
Integrity
Confidentiality

Q9. To efficiently create a digital signature of message M, Alice should: ( )

Create a separate encrypted version of M for each other principal in the system using their respective public keys.
Encrypt M first with Alice’s public key and then hash it.
Hash M first and then encrypt the hash with Alice’s private key.
Hash M first and then encrypt the hash with Alice’s public key.

Q10. Which of the following is NOT true about Zookeeper? ( )

It is used by HBase.
It is organized hierarchically like a file system.
It can be used to run leader election.
It uses Paxos to solve consensus in asynchronous distributed systems.

Q11. In a system of 10 processes, P1 through P10, leaders are elected by lowest process identifier using the Bully algorithm. The old leader P1 fails, and the only process to detect this failure is P2. The number of messages incurred by the Bully algorithm to elect the new leader (not counting messages sent to the failed leader) is: ( )

The process with id 1776 initiates a new leader election run in order to elect the highest-id process as leader.

Q12. A ring of processes with the following node ids in clockwise order is running the Ring Election protocol discussed in lecture: 1776, 1898, 1867, 1810, 1821, 1823, 1804. The process with id 1776 initiates a new leader election run in order to elect the highest-id process as leader. Assuming no further failures, the total number of messages incurred until the protocol terminates is: ( )

The process with id 1776 initiates a new leader election run in order to elect the highest-id process as leader.

Q13. Someone designs a Maekawa-style mutual exclusion system for 5 processes with the following voting sets. P1: {P1,P2,P3}; P2: {P2,P3,P4}; P3: {P3,P4,P5}; P4: {P4,P5,P1}; P5:{P5,P1,P2}. The resulting algorithm: ( )

Is both live and safe
Is neither safe nor live
Is live but not safe
Is safe but not live

Q14. Ricart-Agrawala’s algorithm is running in a group of 30 processes P1–P30. No one is in the critical section. Now P4, P5, P10, and P27 simultaneously want to enter the critical section. Their requests have timestamps 15, 10, 5, 1, respectively. Who enters the critical section first? ( )

P27
There is not enough information to answer this .
A process other than P4, P5, P10, and P27
P4

Q15. Below, you are shown a set of transactions and their operations in the order they are executed in real time.

Transaction T1	Transaction T2	Transaction T3
openTransaction
		openTransaction
Read(x)		Read(x)
		Read(y)
	openTransaction
	Read(x)
	Read(y)
		Read(x)
	Read(x)
		Read(y)
	commit
		Read(x)
		Read(y)

Write(y,11)
commit
		commit

This execution is: ( )

Serially equivalent
Serially equivalent because T3 is a read-only transaction
Not serially equivalent because there are conflicting operations
Not serially equivalent because T3 (a transaction with a higher id) cannot commit before T1 or T2

Q16. Below, you are shown a set of transactions and their operations in the order they are executed in real time.

Transaction T98	Transaction T99
openTransaction
	openTransaction
Read(x)
	Write(x, 22)
	Write(y, 55)
	Read(y)
Write(x, 0)
	Write(y, 77)
Write(y, 33)
commit
	Commit

This execution is: ( )

Serially equivalent
Not serially equivalent because there are conflicting operations
Not serially equivalent because T99 (a transaction with a higher id) cannot commit before T98

Q17. With a per-replica availability of 0.95, what is the minimum number of replicas you need in order to get a 5 Nines availability for an object? ( )

Q18. A system like Riak discovers two updates, U1 and U2, to the same key with the following respective vector clocks: U1: (Server 1: 33, Server 2: 44, Server 3: 55) and U2: (Server 1: 42, Server 2: 45, Server 3: 32). Then the system will: ( )

Not know what to do
Retain both U1 and U2 as sibling updates
Overwrite U2 and retain only U1
Overwrite U1 and retain only U2

Q19. A system like Dynamo or Cassandra receives three concurrent updates U1, U2, U3 to the same key. No further updates arrive. U1 has a timestamp 40 s, U2 has timestamp 42 s, and U3 has timestamp 11 s. Then: ( )

The key will reflect U2 eventually.
The key will store all three updates and resolve them later at a client.
The key will reflect U1 eventually.
The key will reflect U3 eventually.

Q20. In a system using two-phase commit with timeouts set in seconds, one of the servers S, which was updated by transaction T, crashes right after it responds with a Yes in the two-phase commit for T. All messages are delivered quickly and reliably. S’s failure is detected by a sysadmin who then reboots it hours later. Then: ( )

T will definitely commit, and then S can commit its updates after it recovers because it saved these updates before it responded with a Yes.
T may be able to commit (after it recovers) if all servers respond with a Yes in the first phase, in which case S can commit its updates after it recovers because it saved these updates before it responded with a Yes.
T will not commit because the first phase of the two-phase commit times out waiting for S and asks all servers (that T touched) to abort T.
This will result in an error in the system and all transactions will need to be aborted.

Q21. Someone proposes a new transaction management system that assigns unique alphanumeric names to objects. It uses exclusive locking of objects for concurrency control. The system restricts transactions to acquire locks only in lexicographically increasing (i.e., dictionary) order of object names. This system will: ( )

Deadlock

Not deadlock because it violates the necessary condition that says that some objects are accessed in exclusive lock modes

Not deadlock because it violates the necessary condition that says that there is a circular wait (cycle) in the Wait-for graph

Not deadlock because it violates the necessary condition that says that transactions holding locks cannot be preempted

Q22. A system uses read-write locks. In this system, a transaction T53 currently holds a read lock on object O32. Another transaction T54 comes along and wants to obtain a write lock on object O32. Then: ( )

T54 will be granted the lock right away because its transaction id (54) is higher than T53’s transaction id.
T54 will not be granted the lock right away because its transaction id (54) is higher than T53’s transaction id.
T54 will be granted the lock right away because read locks can be shared across processes.
T54 will not be granted the lock right away because a read lock cannot be shared with a write lock

Q23. A particular RPC system chooses little-endian representation for its integers. Now consider a big-endian IBM machine (using this RPC system) that needs to send an RPC reply with an integer result value represented in memory as four bytes, with each byte represented in a hexadecimal format. The actual integer is represented as, in hexadecimal format: BA-98-76-54 (i.e., BA is the most significant byte of the integer). Then: ( )

The IBM machine will store the integer with BA in its lowest addressed byte, while the marshalled RPC message will store 54 in its lowest addressed byte.
Both the IBM machine and the marshalled RPC message will store the integer with BA in its lowest addressed byte.
The IBM machine will store the integer with BA in its highest addressed byte, while the marshalled RPC message will store 98 in its lowest addressed byte.
The IBM machine will store the integer with 54 in its lowest addressed byte, while the marshalled RPC message will store BA in its lowest addressed byte.

Q24. In an NFS setup with freshness interval=10 s, a client finds that a data block it is storing has two timestamps: last validated timestamp=12345 s, and last modified timestamp=12340 s. At the same time, the server’s last modified timestamp=12346 s. If the client clock currently reads 12350 s, what would the client do when this block is accessed right now? ( )

Its behavior is unspecified.
Use the client’s cached copy of the block.
Fetch the last modified timestamp from the server, but not fetch the block itself.
Fetch the block from the server, since the server has the latest timestamped copy.

Q25. A distributed shared memory system, using the invalidate approach, contains 5 processes P1 through P5. Currently, page P is stored in read mode at processes P1, P2, and P3. Process P2 is the owner. A read request from P4 will result in: ( )

None of these options
P4 fetching a copy of the page from either P1, P2, or P3, and then P4 can read and write P, while P1, P2, P3 are reading P
P4 invalidating the copies of P at P1, P2, P3, and P4 fetching page P from P1, P2, or P3, and P4 becoming owner of P in write mode
P4 fetching a copy of P from either P1, P2, or P3, and then P4 can read P concurrently while P1, P2, P3 are reading P

Q26. A distributed shared memory system might prefer to use an update approach instead of an invalidate approach when (MULTIPLE ANSWERS): ( )

None of these options
Pages are small.
Pages are large.
Lots of processes write the same pages concurrently.

Q27. A sensor network uses a spanning tree among the sensors to aggregate temperature data up to the base station (which is at the root of the tree). The base station is interested in the average of all sensor temperature readings. So, each sensor collects some “values” from each of its immediate children in the tree, and communicates some values to its parent in the tree. To minimize energy consumption, we desire these values be as small as possible. Which of the following options is the best for what these values should be? ( )

Count of the temperature readings
Average of the temperature readings
Sum of the temperature readings
Sum of the temperature readings and count of the temperature readings

Q28. A small-world graph (MULTIPLE ANSWERS): ( )

Is a graph that is built among humans in a small world, e.g., a city
Is characterized by a high clustering coefficient
Is characterized by a small average path length
None of these options

Q29. Under what circumstances is it preferable to serve and cache the entire file rather than split fixed-size blocks of the file (MULTIPLE ANSWERS)? ( )