673D: Bear and the two paths

Construction a graph. No solution exists if n = 4 or k <= n !!!

675C: Money Transfers

We know answer <= n, more specifically, answer = n - # of bands whose sum is 0, i.e., transfer happens only within the band.

How to find the max # of bands?!!!

675D: Tree Construction

Consider the final result, should the newly inserted be a left child or a right child?

  Claim: if it is a left child, then its parent is the tightest upper bound

  Proof: if there exists v < p1 < p, consider the common ancestor of p and p1. 

  If it is p1, then v should go left

  If it is p, then v should go p1

  If it is some other node, which means value between p1 and p, then v should go to left at that ancestor.

Similarly, if it is a right child, then its parent is the tightest lower bound

But we have 2 choices, left or right, which one to take?

  Claim: we have exactly one choice

  Proof: consider the LCA a of l and r, if l has right child and r has no left child, we know a is not l or r, i.e. a will be a tighter
bound for v then l and r. 
  
  This contradicts our previous lemmas. So we just need to check which one has no left/right child

High level

1. What is the failure model assumed?
2. Critique the CAP of ZK system
3. What is the liveness and durability guarantee?
4. Why wait-free is not enough for coordination?

Implementation details

1. Why use full path instead of handle to access znodes?
2. Why zk can process read locally at each replica? How about stale local copy problem?
3. Consier the case of new leader changing configs, we need to ensure that no partial config is read ever, even if new leader failed in the middle. Why the lock approach in Chubby can not handle this? How to construct a solution with zk to solve this?
4. ZK uses WAL and fuzzy snapshot to ensure exactly-once processing? Why the fuzzy snapshot works, even if it may not cache actual state at ANY givne time?
5. Why the transaction to be broadcasted need to be idempotent? Why in ARIES the operation inside the WAL does not need to be idempotent?
6. How does client use heatbeat to maintain connection with server?

Implementaion patterns

1. Configuration
2. Group membership
3. Leader election
4. Leader information

Role of Zookeeper in Kafka

1. Map from partition to replica list
   • As a comparison, in GFS, it is the chunker server that keeps track of truck info. The master known which chuck is on which server through heartbeats
   • As common in most master/replication problems, this metadata has a version/epoch to handle the stale master/fail-recover problem
2. For each partition, which replica is the leader and which replicas are in sync
3. leader epoch is to handle stale leader
4. version effctively handles membership view version
5. What the role of controller? Similar to the master server in GFS
6. Broker information. This is the membership managment storage, along with view number, in active-passive replication
7. Controller id and epoch
8. Compare this with the master lease technique
9. Controller will force alive memebers to elect a new primary/leader, i.e., like the master in GFS

SRM 690: GerrymanderEasy

I actually failed system test, because my check is k < N instead of k <= N ! I should not move onto the 3rd question so quickly.

My approach uses a sliding window, which requires my to search all k <= N.

One easier way to code is just to iterate on all i and j >= i, and sum up, and we try upddating max only when (j-i +1) >= K

SRM 686: SegmentsAndPoints

I could not prove my alternative greedy approach, which failed system test, i.e., I got punished by not following proper problem solving approach.

An alternative strategy is to reduce this into a bipartite matching problem, which turns out to be a massive overkill.

Since we are just looking for the existence of an answer, we can just force an order of discovery, if there is ever one, it will be covered by forced order. This forced order insight is what I missed during contest!!!

One natural guess is go from left to right. Now it becomes obvious that to match the leftmost point, we should take the segment ends leftmost and yet covers the point.

Proof #1

claim: If there exists a solution, then our greedy solution can discover at least one of them, i.e., in a feasible solution, if point p can be matched to s, then our algorithm never returns p never matches

proof: if q is matched to s instead of p, then we know q must be to the left of p, due to our forced order of discovery,i.e., s covers both p and q.

Now consider the segment t that would have covered q, by our algorithm, t must end to the right of s, and start to the left of q => i.e., it covers p as well, i.e., our algorithm at least can reutrn p-t matching, if no other is available!

Proof #2

By contradiction, suppose our algorithm returns n matches, and we have a matching p1, p2, …..pn, pn+1, ordered by p, with minimum sum(p) and the minium sum(end of segments)

case 1: consider the first p(i) such that p(i) < our(j), this can happen because the s(i) is being used by some other matching of our algorithm already. Otherwise we hae s(i), p(i) not used by anything and our algo doesn’t return it => clearly contradiciton, if we can prove that for p1…p(i-1), our solution IS same as the optimal solution we suppose. Easily provable by induction!

case 2: p1….pn are same, we just happen to have a p(n+1), proof is similar to case 1

Most papers assume non-byzantine failure. This one shows that how (hard) to defend against it

  1. Suppose we want to tolerate f failures in the total of n nodes,  Why n > 3f?

  2. Why not feasible to offer fault-tolerant privacy in the general case?

  3. Why we have to use synchrony to provide liveness?

  4. Since failure is byzantine, how do we protect against spoofing, replaying, and corruption?

  5. From the client perspective, what does the protocol look like?

  6. What are the steps of the multicast? What are their roles?

  7. What the condition for a back to accept a pre-prepare message?

  8. When will prepare(m,v,n, i) become true? Why this guarantees that non-faulty replicas agree on a total order?

  9. How are watermarks progressed?

  10. What is a stable checkpoint? How to prove a checkpoint is stable?

Classic paper on WAL. The review focuses the use of logs and snapshot/checkpoints, because you can see a lot of similar ideas in the design and use of Kafka

LSN

  1. Why do we need LSN on the page?

  2. Why do we need PrevLSN on the record?

  3. How do we decide if we want to redo a record update?

  4. Why LSN is not compared during undo?*

  5. What does RecLSN represent? 

  6. Do we need to reason if data/op inside a record itself is idempotent? why or why not?

CLR

The major mechanism to support transaction rollback is Compensation log records (CLR)

  1. Why do we need CLR?

  2. Why is CLR undo-only?

  3. How do we ensure CLR does not grow unbound in the case of repeated rollback failure?

Checkpointing

Checkpointing is used to reduce number of logs and non-volatile page reads during recovery

  1. What is in the checkpoint?

  2. How to determine the value of UndoNxtLSN?

  3. Checkpoints are taken asynchronously, that means, before checkpointing is complete, more pages may become dirty, or persisted into
non-volatile storage. Why is this not problem?

Misc

  1. How does ARIES maintain disk stability

  2. Logical logging: incr/dec type operations, derivable changes

  3. disadvantages of shadow page technique

There is a relationship between square and points. This means we can explore the relations from sqaure to points, or to squre from points. For the completeness of our arguments, we have to try both.

From square to points

  1. notice that we have only 3 * 3 * 3 * 3 different choices of borders, we just generate them all. Note what we generate is rectangle, so
need to transform it back to square at the final step

  2. for each generated rectangle, we pass through the list of points, see how many are inside it

  3. For each rectangle that includes at least n-2 points, we need to enlarge it to a sqaure,i.e., the max of 2 border lengths

From points to square

  1.notice we have only 50 points, so we can pick the 2 points that will not be included in the square. Know that this complete search
covers all possible solutions already,i.e., our final solution must be within one of these cases

  2. after taking out the 2 points, calculate the max sqaure that covers ALL remaining points, i.e., it will be max(maxX - minX + 2,
maxY-minY + 2)

  3. repeat 2 for all choices we pick in 1), and update optimal value along the way

In my expreicne, the points to square approach is easier to code

“Paxos Made Simple” mentions that a common optimization is to have a distinguished proposer. This single-master raises a few problems

1. How can a replica become a coordinator?
2. If coordinator instance does not change between paxos instances. There is an optimization we can use, and why does it work?
3. Why we can not serve read request directly out of master copy/db?
4. In response to 3, Why Chubby introduces master leases? How would read request served without master leases?
5. How is master lease renewed? Why the lease timeout in the master is shorter than that in the replicas?
6. During a network partition, a new master is elected, but the old master may still exist in the other partition. When network reconciles, what is the bad case that may happen between the 2 masters? How does Chubby defend against this case?
7. How do they detect master turnover? What is its semantics?

To help reduce the log size, we need to take snapshots, which introduces a few classic problems related to log + snapshot

1. Why it is application that takes snapshot?
2. What is in the snapshot handle? why is it there?
3. Steps of taking a snapshot

Other problems

1. One of the premises of “Paxos Made Simple” is the non-Byzantine failure. However, disk may be emptied, or the file may be corrupted. How does Chubby mitigate these 2 threats?
2. Paxos asks for replicas generate ever-increasing number from disjoint sets. Given some example schemes
3. What kind of system Paxos is in terms of CAP?
4. What is the purpose of safety mode and liveness mode testing?

Note I find Robin-Karp rolling hash is way more likely to use than KMP since it is easier to code

Partial Match Table Example

W = "ABCDABD"

T[0] Special case => -1

T[1] no proper suffix exists, so match length = 0 => 0

T[2] B != A, since we are at i = 0 already, we can not relax further => 0

T[3] C != A, argument similar to T[2] => 0

T[4] D != A, arugment similar to T[2] => 0

T[5] A = A, so T[5] = 1, next we need to try match i = 1

T[6] B = B, so T[6] = T[5] + 1 = 2, next we need to try match i = 2

T[7] => no, we have reached the end! But let us try it out regardless, i.e., assume there is more letters after index 6

So D != C, i.e., not possible to form prefix ABC! so we need to try to form a shorter prefix. However, notice that we miss only the last char C, and AB already matches.

What the longest proper suffix of AB that is also a prefix of AB? We already have that prefix matched, so we have to try it out, since it could be a potential match/

length longest proper suffix of AB that is also a prefix of AB = T[2] = 0 = next i try to match against D.

Note that it D = A and we are at i =0 already, D[7] will be 0

After trying out sample cases by hand, it seems the order of operations doesnt matter much => always same result!

Try to prove that the order of op does not matter by inductions => does not seem to work

So instead of focusing on the sequence of actions, we will focus on the results of these actions, and we noticed that the end result has a closed form

sum of

i * S - i, for all i in S

Instead, we prove this closed form by inductions => should we focus on first step (bottom-up), or last step (top-down) ?

base case: 2

on n + 1 case,

the last step of merge will give score (sum of set A) * (sum of set S - A)

for each element in A, a

by induction, the previous steps leading to form A means we have accumulated all a * A - a

By carrying out the formula, we will accumulate new scores in the form of a * S - A

Combine the above 2 lines, we know all a * S - a are in the final score, and cost(A) + cost(S -A) + (sum of set A) * (sum of set S - A) =
cost(S)

Look at the Unknown: min(W1 * W2)

  1. After some trials, there appears no patterns between values of W1 * W2, i.e, I could not find the pattern that I can travel from the
min(W1 * W2) to a different point

  2. However, to build a path, we almost want to add edge one at a time, and 1) shows that no obvious pattern in W1* W2 after I add an edge
to an exisiting/partial path

  3. This suggests that W1 and W2 should be tracked independently, and combined only during the last step, i.e., we should not compute W1 *
W2 when we are building a path, one edge at a time.

By tracking W1 and W2 independently, we can swap part of the unknown with knowns and invent a new related subproblem:

What is the min value of W1, if we know the value of W2? Note W1 and W2 are from the same path.

Also note that each edge weight is between 1-9, # of nodes < 20, i.e., we can complete search on all possible W2 (< 200), and the min value problem can be solved using a modified standard graph algorithm. In this case we will use Bellman-Ford, as we care paths from only 1 source node.

So here is the pattern/steps

Step: visiting from node nA to nB via one edge

State change:  minFirst(nA, W2) + First(nA, nB) = minFirst(nB, W2 + Second(nA, nB)) if it is less than current value

Inline with Bellman-Ford, we apply relaxation for each node in each round, and repeat such round for n times, since the path can not be longer than n

less on analystics, more on apps and services that process data streams

most valuable streaming apps is closer to async microservice => implement core functions rather than computing analytics

goal: use mainstream application programming model for asynch services

no cluster manager, just a library

load balancing: same protocol that Kafka provides for normal consumers

KStream and KTable can be converted back and forth

How to do windowed operations on streams if events can arrive out of order => represnet count so far for the window. continously update as new data arrives and allow downstream receiver to decide when it is complete

assigns ts to every data record=> event time or processing time possible

“How many ways….” suggests a combinatorical counting, i.e., mostly a recursive/DP problem.

Now we need to find generation step and states between generation steps

Insight

1. Since we want to generate numbers < K, then the prefix matters more than suffix, i.e., the steps should go from left to right

2. Consider A and B independently, i.e., consider the case with only A and K

3. Each step is moving 1 bit at a time. If we fit the prefix of A, then we have constraints on which bit A can offer, otherwise, we know the
new bit from A can be either 0 or 1, because the prefix is < A already, prefix + 1s will be less than A regardless

4. similar to 3), we can apply similar argument to K, if we know we match the prefix of K,
we have to consider the value of K, to decide if we can generate 0 or 1, if prefix < K already, prefix +1s will be less than K regardlesso

5. generate 0 bit is the safe case, it is the use of 1 that requires special attention

Therefore, the states we need to know are

1. which bit we are at

2. Is the partial-number generated by A matching prefix of A

3. Is the partial-number generated by B matching prefix of B

4. Is the partial-number generted by 2) and 3) matching prefix of K

Implementation details

1. initial state is ways(31, true, true, true)

2. base state is ways(0, bool, bool, bool)

3. Note that if we follow the if conditions and if the current bit is 1 or 0, the # of branch clauses grow very quickly. Instead, let us
think: in what condition can we use the (A, B, K) combo (0,0,0), (1, 0, 0), (0, 1, 0), (1,1,1). Note that because ABit & BBit = KBit, we
need to check only 4 possible cases, and add the result if they could be applicable

Since it is a tree problem, we will need to know its root, and part of the problem is to determine the root. Therefore, we will assume root exists (swap known with unknown), and try to find the best answer

Also, when we are traversing, due to the indirect nature of the graph, we need to know where we are from to avoid going back to visited nodes.

The interesting case is when root has more than 2 children. Let us swap unknown with known again, assume we picked 2 children, when can we do to improve solution? => we try to use exchange proof here.

i.e, if we keep n2 instead of n1, the overall cost change is

 -costK(n1) + costD(n1) - costD(n2) + costK(n2)

costK: cost to keep node and form a full binary tree rooted at that node costD: cost to delete that node, i.e.,size of the tree rooted at that node

Note that the “score” we have is in a delta form, and we want to get extreme value of it, then we should try another direction! max the # of surviors all the way, so we can avoid calculating costD, since it is boxed at N at the root level, and the recusive relation becomes straightforward

Consider the first value v1 unable to form with exisitng denos, because we can deal with only 1 new demos, instead of potential multiple ones if we think about largest first.

Reductio ad absurdum + variation: we know that the deno we need to introduce <= v1, so let us introduce new denom with value v1, and see by how much we can reduce v1, and the relationship BETWEEN possible answers

now if new deno d < v1 =>

 c1 * (v1 - delta) + v2 (v2 < v1) = c1 * v1 + v2 - c1 * delta

Since v2 < v1, if we introduce d, we might as well introduce v1, because it is more powerful,i.e., we will always be greedy and introduce the first gap value as denom!

Catches:

1.we know we need 1 as base value
2.need to cast int durng multiply into unsigned long long to handle overflow

1. To calculate max possible #s, we need to know the longest suffix that is also prefix, and the pattern will be this repeating pattern of prefix * middle * suffix. Note that prefix and suffix may overlap!

2. DP approach: E(i, typed) = expected # of words to form, where typed letters are typed, and we are matching word[i]

3. when i is a match, go to E(i+1, typed++) if i < length. Otherwise, it becomes 1 + E(0, typed++)

The final result the sum of all states, since each of them is a distince state

When it doesnt match it goes to E(fallback(i), typed++), where fallback is the longest suffix that ends at i - 1, which is also a prefix => i.e., KMP insight

1. One important insight is the to use the linearily of expectations.

E (total number of words) = 

E(number of word start at 0+ number of prefix start at 1+...) = 

E(# of word start at 0) + E(# of word start at 1) + ... = 

w * E(# of word start at 0) =  

w * 1 * Pr(a word start at 1)

1. Obviously that we will have to exclude all rows until only 1 left. To exclude one row, we will have to try C/W times to ensure that is the case, and it is not possible to hide it in that row.

2. Now that we have only 1 row left, where to put the first guess? No obvious answer from here

3. Now think the complimentary case, if the first guess is hit, we should try its immediate neighbors, because

1. If it is a hit, we did not waste the turn, i.e., we are still on the path to the optimal solution

2. If it is a miss, we immediately hit the boundary, and because we know W, we immedately know the remaining cells

3. i.e., once the first hit is announced, we will waste only 1 turn, which is optimal (Otherwise, it would be we are always correct,
contracting the fact opponent can move ship)

1. From discussion on 3, we know we have to delay the first hit as much as possible, since min # of misses on a row is C/W before we know the ship doesnt exist, we must try all C/W hits,one of them will be a hit, which leads us to insight 3)

My solution is uses a game theory-ish solution, passed sample but failed even the small case, because I missed insight 3. What I should have done is the walk through the test case by hand first to gain additional insight

Small case is 10k: n^2 is not enough

consider if an answer exists, then we can break down the whole string into product of

1 * i * 1 * j * 1  * k * 1

Reductio ad absurdum: consider the shortest prefix s.t. product is i, i.e, the “padding”, then the product must be of form

prefix * 1 * j * 1 * k * 1

i.e., when a solution exists, we can break it down in a way that the shortest prefix that forms i is part of the solution

by similar argument, we can find the shortest prefix that forms j, after the shortest prefix that forms i.

Since the group has 4 elements, the cycle length has max 4,i.e.,

(word repeating 1 to 4 times, depending on the product of word) * prefix = prefix

This means if a prefix is a repitition of words more than 4 tims, it can not be the shorteset prefix

i.e., we can find prefix for i and j within first 8 words => we reduced it to smaller case!

Note that with i, j , we can infer if k exists by “dividing” the product of word* by i*j, since divide/product is one-to-one mapping, we can infer the suffix

Because the whole word is repeated, we can calc the product in log(n)

Insight A: need to bring the number to the same # of digits,and then work on individual digitso

So the sequence would be 9 -> 10 -> 11 -> 19 -> 91 -> 99 -> 101 -> 109 -> 199 -> 991….

Insight B: after we reach the length we need, we need no more than 1 reverse op

If there exists more than 1 reverse, the op would be:

adds -> reverse -> adds -> reverse -> adds ->....

We can combine first and third adds for the same effect and remove 1 reverse, i.e., the solution wont be optimal

The general sequence of actions:

1. generate to 10*1 with enough digits
2. use adds to form the right half as the mirror of targeted left half
3. reverse, note we dont need to reverse if the left half is of form 10* already
4. use adds to form the right hafl as the targed right half
5. speical case is the # ends in 0, in that case step(N) = step(N-1) + 1

My previous approach of trying to associate x[i] directly with x[i-1] has problem, mainly the handling of multiple insertion/deletions. This approach violates one pricinple of inductions => it was attacking too many steps at a time.

But previous discussion still yields valuable insights, but this time, we will do it 1 step at a time.

so consider position x[i], which ONE step can we do here?

1. Delete x[i] for tail from 0 to 255 Cost(i, tail) = min(cost, D + cost(i -1, tail))

2. Insert a value to the right. Note we dont consider insertion to the left, because that is covered in the previous step

3. Update current value to a new value

Note that after2, we can keep inserting, thus we actually have 2 states

1. a smooth array with last element drived from i, delete or update

2. a smooth array ending with a value, this array is created with 1, and a number of inserting

So at each step, we first apply 1), and then apply 2)

action(i) populateTailed populateInsertion cost(i, v) = min(costTail(i, v), costInsert(i, v))

populateTailed for v from 0 to 255 costTail(i, v) = min(costTail(i,v), D + cost(i -1, v)) //deletion case

for tailV from 0 to 255 for prevV from (tailV - M, tailV + M) costTail(i, tailV) = min(costTail(i, v), abs(tailV - x[i]) + cost(i-1, tailV))

populateInsertion for v from 0 to 255 for tailV from 0 to 255 costInsert(i, v) = min(costInsert(i,v), InsertionCost(tailV, v) + costTail(i, tailV))

Note you can reverse the direction of your sub problem as well, i.e., the subproblem becomes cost(i, v)

Active system. No costly storage op in processing

System must perform message processing w/o costly storage operation in the critical processing path.

Passive systems require applicaitons to poll for conditions of interest, but half the polling interval is added to the processing delay=> expected time of next arriabal. So the system should be event-driven, active system

High-level, extensible processing language

StreamSQL should extend the sematics of standard SQL by adding to it rich windowing constructs and stream-specific operators. window serves the purpose by defining the scope of a mult-message operator,i.e., support a high-level language with built-in extensible stream-oriented primitives and operators

infrastructure must handle data that is late or delayed, missing, or out-of-sequence. Every calculation that can block must be allowed to time out

must guarantee predicatble and repeatable outcomes

Efficiently store, access, and modify state information

seamless switching,i.e., without code change, “catch up”-> switch automatcially from historical to live data, without the maunal intervention of a human

state must be stored in the same OS address space as the application using an embedded DB system. For seamless integrateion, the system should use a uniform language when dealing live stearming data and state information

Tandem-style hot backup and real-time failover scheme=> HA

Application should automatically and transparently load-balance over the avaialble machines

highly-optimized, minimal-overhead execution engine that minimized ration of overhead to useful work, and limit “boundray crossing” by integrating all intoa single system process.