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.

Suppose you start with a simple case class, with concrete domain-specific operations.

But you want to add more behaviors to your type, espeically those less related to domain operations, more on the functional relationships.

You need the implementation for the new behavior. A traditional way would be to include it in the type definition, often, this means including mixin the trait which has the behavior you want.

One way to decouple it the mixined trait is to

1. Define a general type class that has the behavior you want
2. Define a instance of that type class, with that concrete type as type parameter. This instance will have implementation of that behavior in that concrete type
3. this instance of the type class will be defined in the companion object of the type class
4. To use this implementation, pass in the type class as type parameter, and use implicitly to get the type class (NOTE: note type instance) 5.Basically, treat type parameters as normal parameters pass into the function. According to Curry-Howard Isomorphism, each porposition int he logic there is a coresponding type int he programing language and vice versa. And each proff of a given proposition there is a program of the correspoidng type and vice versa

I failed to solve it because:

1. Tried reducing to partition optimization problem, realize it has no easy/efficient solution

2. Saw the simple greedy insight for small case, and yet, I was not able to prove it.

The excercise proof from contest analysis

Given there exists an optimal solution where all but 0 or 1 of each problem solutions belong to advancers. We claim F(C,n) = sum(S)/C

Proof: Induction on the value of F(C,n) = k

notice there we can not have more than C problems whose solutions has 1 unused by advancers. Otherwise, we can advance 1 more instead. By this fact, we also know at least N-C + 1 problems whose solutions are used by all advancers.

If we take out 1 solve from C problems, while ensuring we take out ones from ones with solutions unused by advancers. We know that we will end up with a state where

1. the problems with unused solutions now all become fully used

2. some of the problems without unused solutions become with 1, unused solution, but this number <= C, because we make C changes in total

i.e., we reach the inductive state for k - 1. Adding these C solves back gives the result we need.

Proof of correctness for the divide and cap solution

Sort S, when k = sum(S)/C, and s[N] <= k, then F(C,n) = k

Proof: The general idea is similar to the one above

Induction on k,

Base case k = 0. Trivial

k case: Take 1 entries off from s[N-C +1] to S[N], kNew = k-1 = sum(SNew)/C

Because sum(S) = C * K, there are less than C entries with s[i] = k, otherwise, sum(S[i[) > sum(S) i.e., our operation ensures all S[i] <= k - 1, k-1 = sum(SNew)/C, by induction, at this time, F(C, n) = k - 1. Now we add the 1 entries back, allows one more to advance, i.e., F(C,n) = k.

Rotate

Code up rotate routine, and then detect win conditions for horionzal, vertical, and diagonal

Pseudo code for rotate

  for col from 0 to n - 1
    oldCol = n - 1
    oldRow = n - col - 1
    for row from n -1 to 0
      while(oldCol >= 0 && old[oldRow][oldCol] == '.')
        oldCol--;

      if (oldCol >= 0)
        new[row][col] = old[oldRow][oldCol]

Pseudo code for check

  for row from 0 to n -1
    for col from 0 to n - 4 
      color = new[row][col];
      if (color == '.')
        continue;
      for i from 1 to 3
        if '.' or color, go to next col

Make it smooth

My approach, which is WRONG. Put here just for the record

1. If an array is smooth, all subarrays must be smooth

2. However, reverse can not be said to be true, because the ends of two smooth subarries may have too huge difference => we need to include the actual number as well!

3. You will never delete and then insert, or vice versa, never insert and update, never update and delete, never update and update, because compress them into 1 step can only save cost. i.e., if we have a list of final ops, the order of applying them does not matter, because there is no dependency between steps

4. Suppose we have a smooth subarray from 1 to n, with end value v. to make i+1 smooth with end value v1. change the value of a[i+1] to match smoothness range of subarray a[i]

5. Note we do not attempt to change a[i], because a different end value for position i would cover this case already.

6. To change a[i+1] to a specific value v, we can either delete and then insert, or do a plain update. We will pick the min choice.

Pseudo code

  Speical case i = 1, only deletion and insertion vs update case

  for i = 2 to N
    for tailVal = 0 to 255
      for newTailVal = 0 to 255
        cost[i][newTailVal] = convertCost(a[i], newTailVal, tailVal) + cost[i - 1][tailVal]

Now we need to design convertCost(fromV, toV, tailVal)

1. If toV is within the M range of tailVal we either delete fromV and then insert toV, or update fromV, which ever is cheaper

2. Otherwise, toV is outside M range of tailVal. if toV > tailVal, total cost = convertCost(fromV, toV - M, tailVal) + insertion cost else if toV < tailV total cost = convertCost(fromV, toV + M, tailVal) + insertion cost

The key insight here is that in induction, we limit our steps as much as we can to help discover insight, so long as our # of states will not cause stack overflow problem. But we can compress the +/- into a multiple of Ms to reduce # of states

Number Game

Note that Each step is similar to gcd calculation

Consider the special case: where A,B are co-prime => turns out useless

Consider the simple case, and try to reduce to that case, and w.l.g, assume A > B. Note that state is symmetric along the diagonal

1. B< A <= 2 * B, and the next step must be (A -B, B), i.e., state(A, B) = !state(A-B, B) when B < A <= 2 * B.

2. A > 2 * B, state(A,B) is winning if any of (A-B ….A-KB, B) is losing while A-KB > 0, and it is losing if ALL of (A-B…A-KB, B) are winning if A-KB > 0. But there must exist j s.t. B <= A-j * B <= 2 * B, i.e., we can try both state(A -j B, B) and state(A - j B -B, B). But by 1), one of them is losing, and one of them is winning, i.e., A can not lose!

3. Consider A = B, it is a losing state, since we have to reach 0 ourselves

4. A < B is same as case 1 and 2

I failed to solve the large case, which involves Fibonacci number and golden ratio

Claim: (A, B) is winnning iff A > phi * B, note because A, B are integers, impossible to have A = phi * B

Proof: Induction on A, w.l.g., assume A >= B A > 2 * B, reuse the preivous solution, A is winning for sure

2B >= A > phi *B, only choice left is go (B, A -B), i.e. B >= A -B > (phi - 1) B i.e., B < phi * (A - B), with B > A - B, by induction, B is losing, i.e., A is winning

If phi * B > A >= B, only choice is (B, A-B) with B > phi * (A-B), by induction, B must be winning and A must be losing!