Transcript ecs251_w2013_sample_final

ecs251 Winter 2013 sample final
Name:
Student ID:
Email:
Open book/laptop/Internet and totally 10 questions (choose at most 4 to answer, 10% each), 16 pages.
Please write precise and clean answers for AT MOST FOUR QUESTIONS. Only THREE questions (with
HIGHER SCORES) will be counted toward your grade. Please READ the questions VERY CAREFULLY
before putting down the final answer. And, also please mark your answer clearly. You can use the back of
the pages. Every page of this exam book needs to be returned back.
If we suspect any cheating behavior, we will pass the case to the academic committee immediately.
Score: ___/30
4/6/2016
ecs251 winter 2013, sample final
1
Q-01
With the “backward and serial validation” of OCC (Optimistic Concurrency Control), for the following
execution history, which transaction(s) will be aborted and WHY?
T1:
read
T2:
T3:
Z
read
W
read
read
read
read
read
validation
T4:
read
X
read
Y
X
read
read
Y
Z
read
W
write
write
Z
W
Y
W
X
Y
validation
write
write
validation
write
write
validation
4/6/2016
Y
X
X
Y
ecs251 winter 2013, sample final
2
Q-02
Under DOCC (Distributed/Decentralized OCC), when and how would a global transaction (i.e., a
transaction involving multiple local sub-transactions/servers) obtain its mvID (maximum validation ID)?
Coordinator
Server
4/6/2016
Server
Coordinator
Server
Server
Coordinator
…..
ecs251 winter 2013, sample final
Server
3
Q-03
(Two Phase Commit) Under exactly which condition, under the 2PC protocol, we have to wait
for a crash server to recover before we can continue the commitment protocol?
4/6/2016
ecs251 winter 2013, sample final
4
Q-04
(Transaction Support for GFS) Under this question, we will consider to build a transaction
system on top of GFS (instead of on top of a Database). When a transaction needs to access
an object (either read or write access), it needs to contact the Master (the Master under GFS
but with some extensions to support transaction) first. For supporting the ACID properties, we
can potentially use either 2PL (Two-Phase Locking) or OCC (Optimistic Concurrency Control)
to guarantee serilizability. Please decide which option (2PL or OCC) is better for GFS
transactions and WHY?
4/6/2016
ecs251 winter 2013, sample final
5
Q-05
(DHT/Chord) Here is a short description of Chord from Wikipedia:
The Chord protocol is one solution for connecting the peers of a P2P network. Chord consistently maps
a key onto a node. Both keys and nodes are assigned an m-bit identifier. For nodes, this identifier is a
hash of the node's IP address. For keys, this identifier is a hash of a keyword, such as a file name. It is
not uncommon to use the words "nodes" and "keys" to refer to these identifiers, rather than actual nodes
or keys. There are many other algorithms in use by P2P, but this is a simple and common approach.
A logical ring with positions numbered 0 to 2 m − 1 is formed among nodes. Key k is assigned to node
successor(k), which is the node whose identifier is equal to or follows the identifier of k. If there are N
nodes and K keys, then each node is responsible for roughly K / N keys.
When a new node joins or leaves the network, responsibility for O(K / N) keys changes hands.
If each node knows only the location of its successor, a linear search over the network could locate a
particular key. This is a naive method for searching the network, since any given message could
potentially have to be relayed through most of the network. Chord implements a faster search method.
Chord requires each node to keep a "finger table" containing up to m entries. The ith entry of node n will
contain the address of successor((n + 2i − 1) mod 2m).
With such a finger table, the number of nodes that must be contacted to find a successor in an N-node
network is O(logN).
QUESTION: Should the last part be O(logN) or O(m) (i.e., the size of the network versus the size of the
ring)? Please justify your answer!
4/6/2016
ecs251 winter 2013, sample final
6
Q-06
(Kleinberg’s Search Algorithm) Under the Kleinberg’s search algorithm, you must know the
coordinate of the target and you must have a way to measure/estimate the metric distances
between your friends and the target. Please describe an example application and argue that
why, under this application domain, it is practically or theoretically impossible to support this
model.
4/6/2016
ecs251 winter 2013, sample final
7
Q-07
(Map and Reduce) Please describe a parallel application (i.e., an application can naturally
leverage a parallel system to speed up its execution performance) which doesn’t fit well with
the Map and Reduce paradigm. Please explain why?
4/6/2016
ecs251 winter 2013, sample final
8