Today we review the paper Queues are Databases by Jim Gray.
 He talks about message oriented middleware (MOM) and makes the following mentions:
Queued transaction processing is less general than direct transaction processing. Queued systems are built on top of direct systems. Direct, conversational or distributed transactions are not built on top of a queued system.
Queues are interesting databases with interesting concurrency control. He suggests building it into the database directly.
Queues systems need DBMS functionality. Queues need security, configuration, performance monitoring, recovery and reorganization utilities. Database systems already have these features.
Queue Managers are simple TP-monitors managing server pools driven by queues. Database systems are encompassing many server pool features as they evolve to TP-like system.
He mentions that there are three ACID units in queued transaction processing of a request, response : 1) Client places request in queue 2) Server dequeues request, performs task, enqueues response and 3) Requester dequeues response from output queue.
Due to these three units, a multistep dialog cannot be wrapped in a single ACID transaction unit. There is a lot of overhead in implementing distributed transactions on top of queues. By contrast, it is easier for a direct transaction processing systems to add a queue mechanism as a new transaction type.
 He recognizes that queues are important when he says that queue processing is increasingly important for workflow, disconnected operation and replication applications. He adds that it has always been the mainstay of batch and spool operations. With the acronyms MOM for queues and DADs for databa, ses, he says both MOM and DAD are needed.
When the queues become part of databases, the queue is a database class that gets create(), enqueue(), dequeue(), poll() and destroy() methods. By using a database, the queue manager becomes a native resource manager with no special code for startup, shutdown, checkpoint, commit, query, security or utilities.  The database does all the hard stuff such as locking, logging, access paths, recovery, utilities, security, performance monitoring and so on. Even the query manager gets query, backup, restore, reorganize and replicate data for free.
If the queues were outside database they would pose performance and concurrency control issues.
In  cloud computing with a distributed message queue cluster, we could perhaps do without transactions and instead use idempotent incremental operations with retries.
#codingexercise
Implement a Futures interface on top of queues
void Promise(new Function(resolve, reject))
{
 
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We were reviewing the performance of LRC in WAS. We now review related work. Erasure coding has been applied in many large scale distributed storage systems. Its better than simple replication because it provides higher reliability and it requires much lower storage for the same reliability. Even when the distributed systems apply erasure coding, they typically apply only Reed-Solomon. LRC has proved better than that both in terms of efficiency and performance tradeoff. We also read on related work and how LRC differs from those. Reed-Solomon codes are maximum distance separable (MDS) codes which require minimum storage overhead for given fault tolerance. LRC is not MDS and requires additional storage overhead for the same fault tolerance.This is exploited for efficient reconstruction. This tradeoff between storage overhead and reconstruction efficiency is also attempted by other systems such as Weaver codes, HoVer codes and Stepped Combination codes. LRC achieves better trade-offs than all of the above to meet WAS erasure coding design goals. One of the alternatives to reconstruction is to read from more fragments instead of fewer fragments but to reduce the amount read from each fragment.However, this does not have the same savings in terms of I/O and bandwidth as LRC does.
Thus we have seen that erasure coding reduces the cost of cloud storage, where our target storage overhead is 1.33x of the original data.The challenge in erasure coding is the fast reconstruction of offline data fragments such as due to disk, node, rack or switch failures as well as during upgrades. LRC reduces the number of fragments to read and perform the reconstruction. It has slightly more overhead but comparable latency for small I/Os and better latency for large I/Os  At the same time it  provide better durability than the traditional approach of keeping 3 copies. Lastly we reviewed some of the implementation and design considerations.
#codingexercise
Reed Solomon corrected errors theoretically by finding the most popular message polynomial. The potential polynomials are repeatedly produced using subsets. How many subsets are there
Solution : The number of subsets is the binomial coefficient n choose k.
int getSubsets (int n, int k)
{
   return Factorial(n) / (Factorial(n-k) * Factorial(k));
} 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We were reviewing the performance of LRC in WAS. We now review related work. Erasure coding has been applied in many large scale distributed storage systems. Its better than simple replication because it provides higher reliability and it requires much lower storage for the same reliability. Even when the distributed systems apply erasure coding, they typically apply only Reed-Solomon. LRC has proved better than that both in terms of efficiency and performance tradeoff. Moreover, LRC reduces costs. For example, node failures trigger reconstruction which is a significant cost. No data is lost on such transient errors and these account for nearly 90% of data center failures. During these periods as well as upgrades, even though there is no background data rebuilding, reads accessing these unavailable nodes are served through reconstruction. Some system techniques like load balancing and prioritization help but LRC explores whether the erasure coding scheme itself can be optimized to reduce repair traffic and improve user I/Os. In addition to these benefits, LRC exploits non-uniform parity degrees, where some parities connect to fewer data nodes than others. This facilitates efficient reconstruction and follows the new trend in the storage industry.  Previous work applied enumeration and heuristic methods to search for parity check erasure codes of small length, Due to exponential search space, the exploration was limited to 3,4 and 5 parities. These could not tolerate arbitrary three failures  where as LRC can.
#codingexercise
List<int> GetReedSolomon(Int[,] coefficients, List<String> message, int n)
{
var Cx = new List<int>();
for (int i = 0; i < n; i++)
{
Cx.Add(getPolynomial(coefficients, ref message));
}
return Cx;
}
String getPolynomial( Int[,] coefficients ref List<string> message)
{
int sum = 0;
for (int i = 0; i <message.count; i++)
sum += get_coefficient(coefficients, i-1)*message[i];
return sum;

}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We were reviewing the performance of LRC in WAS with small I/Os and large I/Os.  Finally we read up on the latency comparision for decoding fragments between LRC and Reed Solomon in this performance study. The latency is expected to be improved in LRC due to the reduced number of fragments. However this is much smaller by orders of magnitude than the overall latency to transfer the fragments to perform the reconstruction. This makes the latency comparable between LRC and Reed Solomon
#coding exercise
Implement Galois field polynomial  subtraction
Polynomial is represented as coefficient and power pairs in ascending order
They are grouped and operated.
List <Term> SubtractPolynomial ( List <Term> first, List <Term> Second)
{
int ret = new List <Term>();
first.sort();
second.sort();
int i = 0;
int j = 0;
while (i < first.Count && j < second.count)
{
if (first[i].power == second[j].power){
    ret.Add(new Term(first[i].coefficient - second[j].coefficient, first[i].power));
    i++;
    j++;
    }
else if (first[i].power < second[j].power)
{
    ret.Add(new Term(first[i].coefficient , first[i].power));
    i++;
}
else
{
    ret.Add(new Term(second[j].coefficient , second[j].power));
    j++;
}
}

while ( i < first.Count)
{
    ret.Add(new Term(first[i].coefficient , first[i].power));
    i++;
}
while (j < second.Count)
{
    ret.Add(new Term(second[j].coefficient , second[j].power));
    j++;
}
Return ret;
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We were discussing data consistency checks and the use of CRC. We now look at performance considerations in WAS. Storage is in the firm of blobs, tables, queues and drive. Application have different workloadstyles with smaller size  I/Os for tables and queues and larger I/Os for blobs and drives, typically greater than 4MB. A production cluster was used with significant load variations over time. The LRC was compared with ReedSolomon codes. The key metric for small I/Os was latency and the number of I/Os made by the requests. The key metric for large I/Os was latency and the bandwidth. In the small I/O case the experiments were run with a mixture of direct read  of a single fragment reconstruction reads. When the cluster load is light all the reconstruction cost is very low. The reconstruction reads performed poorly due to effect of the slowest fragments. LRC performed better than Reed Solomon due to the lower number of fragments used.
The results from the large I/O were very different  from the small I/O case. Even when the cluster load is light, the reconstruction with Erasure coding us much slower than direct read cost  due to the bandwidth consumed. When the cluster load was heavy, the latency came from  the network card. Even here the LRC performed better than Reed Solomon due to the reduced number of fragments.
#coding exercise
Implement Galois field polynomial addition or subtraction
Polynomial is represented as coefficient and power pairs in as ending order
They are all grouped and operated.
List <Term> AddPolynomial ( List <Term> first, List <Term> Second)
{
int ret = new List < Term>();
int max = first.last.power;
If ( max < second.last.power )
       max = second.last.power
For (int I = 0; I <= max; I++)
{
      var firstTerm = first.find( power = i); // returns empty if not found
       var secondTerm = second.find(power = i);
      Ret.add ( new Term (firstTerm.coefficient + secondTerm.coefficient,  i));
 }
Return ret;
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We saw how to distribute the fragments in LRC for WAS. We were also reviewing the designing for Erasure Coding where we saw how various I/O types required to be scheduled. We also saw the reconstruction read-ahead and caching. Now we read the consistency of coded data. This is largely done to mitigate data corruption which can occur when data is at rest, being read and written or in transit. Therefore it is essential to check the consistency of data in every step of the storage system and to periodically scrub the data at rest. This is done with checksum and parity which are two primary mechanisms to protect against data corruption.In Windows Azure Storage each append block contains a CRC of the data block which can help detect data and metadata corruptions. If the CRC check fails, then the data is reconstructed using other combinations of erasure coded fragments on the next available EN.
To ensure that the erasure coding operation does not itself introduce data inconsistency, each operation is validated by a few decoding operations. For LRC, these validations include randomly choosing one data fragment in each local group and reconstruct it using its local group, doing the same with one global parity and the remaining data fragments, doing it with the other global parity and the remaining data fragments, choosing two data fragments and reconstructing them, choosing three data fragments and reconstructing them and randomly choosing four data fragments. Finally the coordinator EN performs a CRC of all of the final data fragments. and checks this CRC against that of the original extent Together all these checks ensure data consistency.
Erasure  Coding involves Galois Field arithmetic but using it directly is quite expensive. Instead addition and multiplication tables are used. Reed Solomon codes are better implemented with  the use of XOR operations and more so by ordering the XOR operations based on the patterns in the coding and decoding matrices. This way some redundancies and repetitions are avoided.
#codingexercise
Implement a 3 bit CRC on a 14 bit message
List<Bit> GetCRC(List<bit> message, List<bit> polynomial, int n)
{
for (int i = 0; i < n; i ++) message.add(0); // pad right to n
int last = message.Length - polynomial.Length;
for (int start = 0; start < last; start++)
    if (message.Value() != 0)
        for (int i = start;  < polynomial.Length; i++) message[i] = message[i] ^ polynomial[i];
return message.GetRange(last. n);
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We saw how to distribute the fragments in LRC for WAS. We now review the design aspects such as scheduling of various I/O types. There are a variety of I/O types from clients including open/close, read/append, create or delete, replicate, scrub and move operations. If all these I/Os were to happen at their own pace, the system will tank. To make the system fair and responsive, operations are subject to throttling and scheduling at all levels of the storage system. I/O requests can be accepted, rejected or delayed on every extent node and stream manager. Similarly the SM keeps track of data replication load on individual ENs and the system as a whole to make decisions on when to initiate replication, erasure coding, deletion and various other system maintenance.  Coding and decoding both involve multiple ENs, scheduling and throttling of these information become important. It is also important to make sure erasure coding is keeping up with the incoming data rate from the customers as well as the internal system functions  such as garbage collection. If we look at the scale of the overhead in terms of the data size which can easily be petabytes in every few days, the importance of scheduling such operations becomes all the more important.
Reconstruction read ahead and caching is another design point for LRC in WAS. Reconstruction of unavailable fragments is done in unit sizes. These have to be greater than the individual append blocks to reduce the number of disk and network I/Os. Append blocks are 5MB in sizes. Read ahead data of upto 250 MB is cached in memory  (upto 256 MB) of the Extent Node that has done the reconstruction. When the reads are sequential, there is now no need to goto the disk because the cache works well in this regard.
#codingexercise
print all permutations of a string in ascending order
Void Permute (String a, StringBuilder b, bool[] used, ref List<string> permutations) 
{ 
  If ( b.Length == a.Length)  { permutations.Add(b.toString()); return;} 
  For (int I = 0; I < a.Length ; i++) 
  { 
    If (used[i]) continue; 
     used[i] = true; 
     B += A[i]; 
     Permute(a, b, used, ref permutations); 
     B [B.Length – 1] = ‘/0’; 
     used[i] = false; 
  } 
} 
permutations.Sort();
Another way could be to sort the input string beforehand so as to eliminate the last step sort above.

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities.  We were discussing Local Reconstruction codes in windows azure storage.  The placement of the fragments was based on two factors: load which favors the less occupied extent nodes and reliability which avoids placing fragments into the same correlated domain.  Correlated domains can be those from a fault such as on a rack that brings down a few nodes together or they can be on an upgrade domain which categorizes a group of nodes that are taken offline. Let us now see how to place a fragment in WAS.  A WAS stamp consists of twenty racks There are sixteen fragments possible for an extent and each is placed on a different rack for maximum reliability. If each fragment were similarly placed on a different upgrade domain, there would be one too many and resulting in slow down.  There are up to 10 upgrade domains used. In order to place the fragments across upgrade domains, the local group property of LRC is exploited and the group fragments belonging to the different local groups are placed into the same upgrade domains. The local data fragments are placed in the same upgrade domain. Similarly the local data parities are placed in the same upgrade domain.  The global parities are placed in separate upgrade domains.
#codingexercise
After detecting the overlaps from two strings, find if a new given string is a concatenation of two or more overlaps

Void Combine (List<List<char>> overlaps, List<List<char>> b, List<char> target,  int start, int level)

{

For (int I = start ; I < overlaps.Length; i++)

{

b[level] = overlap[i];
if (b.toString() == target.toString()) Console.WriteLine('True');

If (I < overlaps.Length)

Combine(overlaps,b, target, start+1,level+1)

B[level] = NULL;

}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We were discussing the components of the WAS architecture. We discussed the Erasure coding is in the stream layer. We now review LRC in windows Azure storage. The placement of data and parity fragments is based on two factors : load which favors the less occupied and sparse distribution and reliability which favors the separation of faults from correlated domains. There are two such correlated domains one is the rack which can fail altogether and the second is the upgrade which can fail as groups of fragments are taken offline together.
#coding exercise
Determine overlaps in linear time between two sequences
We need offsets and length
If we find a match  we remove it from the original string
We repeat until there are no more left.
Matches have same length and sequence.
We iterate from the end of the last match in one string.

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. There are three components to a WAS architecture - the front end, the object layer and the stream replication layer. All of these three components are present within any single storage cluster.  The Erasure coding is implemented within stream replication layer which is responsible for the robustness of data. The object partition is in a separate layer so it can scale out. The main components of a stream layer are the stream managers and extent nodes.  The nodes consist of blocks which is the unit for Crc which implies data is read or appended using blocks. When the extent reaches maximum size, a new extent is  created. When the extent is sealed it becomes immutable. During Erasure coding, the SM creates  fragments on a set of ENs which are responsible for . And then one of the EN is chosen as the coordinator which has the responsibility of making sure the Erasure coding completes.the coordinator EN decides which fragment boundaries for all of the fragments will be in the extent. Then this  is communicated to the target ENs. The Erasure coding can be paused and resumed anytime because it is offline.
#coding exercise
Find duplicate substrings in linear time between two strings. Matching substrings do not overlap on the same string. Their sequences also match.
List <List <char>> getoverlaps ( list<char> a, list <char> b )
{
var ret = new List <List<char>>();
for (int I = 0; I < a.count; i++)
 for ( int j = 0; j < b.count; j++)
{
  If (a [i] == b [j])
    {
      Int m =i;
      Int n = j;
      int k = 0;
      var word = new List <char>();
      while  (a [m] == b [n] && m < a.count  && N < b.count)
       {
          Word.add (a [m]);
           M++;
           N++;
           K++;
        }
        Ret.add (word);
        I = I + k;
        J = j + k;
     
    }
 
}
Return ret;
}

Differences between Additional Edges in a graph and a list of normalized paths

We have traditionally represented nodes and edges in a graph with vertices and adjacency matrix or list. We often use a graph to find shortest path between two vertices. Although we use well known graph algorithms to traverse the graph to find these paths dynamically, we could also capture and save this information with the graph itself. This is ideal when the graph does not have to be manipulated very often such as with addition or deletion of nodes and or edges. Data warehouses represented by graphs could benefit with additional representational aid because they don’t change very much

Some such aid to represent graphs in order to improve performance for traversal or to find paths between vertices include the following:

1)      Add additional edges to represent connectivity by skipping a number of nodes. There could be a set of edges colored differently for skipping say 2, 4, 8 … nodes in the graph.

2)      To have a normalized set of paths among all enumerable paths that could be iterated to construct path between two vertices.

The differences between these approaches are as follows:

The former is used this way: If we have a source and destination vertices, we change the source or destination to something closer between the two between which the destination is guaranteed to be present thus optimizing traversal between visiting each interim node one by one and skipping them. Additionally, we traverse the unknown segment from higher order edges to lower order edges where higher order are skip lists and lowest order is next vertex hop or single hop list.

The latter is used this way: If we have a source and destination vertices, we find all paths that contain source and destination and filter them progressively by replacing source and destination with interim nodes. The idea is that a set of normalized paths will be guaranteed to have interim nodes and also reduce the number of all possible paths that may be scanned otherwise.  By changing source or destination or both with as front most as possible or as end most as possible we can converge to a fully traversable path with fewer iterations. Each iteration skips a few nodes by knowing that there already exists a path to connect them.

The latter technique does not require touching the graph and the normalized list can be stored outside the graph. The former technique requires mode edges to be added to the same graph. Both techniques support algorithms to be modified to offload the shortest path discovery between two vertices with performance improvements.

#code question
Do linear deduplication between two integer arrays to merge them.

List<int> dedup( List <int> a, List <int> b)
{
a.sort ();
b.sort();
var ret = new List <int> ();
Int m = 0;
Int n = 0;
For (int I = 0; I < a.count + b.count;  I++)
{
int min = a[m];
If (a [m] == b [n])
{
M++;
n++;
}
If (a [m] < b [n])
{
M++;
}
Else
{
min = b[n];
N++;
}
if (ret.Count == 0 || ret.Last() != min)
     ret.Add(min);
}
Return ret;
} 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.  A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We now read the cost and performance trade-offs. Each (k,l,r) set yields one set of values of reliability, reconstruction cost and storage overhead. If we vary the parameters, we can get many set of values. Each fragment has to place on a different domain, the number of domains in a cluster limits the total number of fragments in the code. The authors use 20 as a limit since the storage stamps have upto 20 fault domains.Further they keep those set of parameters that yield equal or higher reliability than 3-replication. Then they plot storage and reconstruction cost of the remaining sets. Each individual point represent one set of coding parameters which in turn represents certain tradeoffs between storage cost and reconstruction performance. The authors found this to vary a lot so they only took the lower bound.

#coding exercise:
given a set of paths in a graph, normalize them to not contain repetitions.
We represent vertices and paths as string
then we apply regular expression between the two
void normalize(List<string>paths)
{
var ret = new List<string>();
for (int i = 0; i < paths.Count; i++)
   for (int j = 0; j < paths.Count; j++)
   {
      // don't compare me to myself
       if (i != j){
       var match = GenerateIntersections(paths[i], paths[j]); //List<string>.Intersect() may give non-contiguous paths
       ret.Add(path);
       }
    }
return ret;
}

The GenerateIntersections does not need to be O(n^2) where n is the length of the paths . It  can be linear because the finite automaton for both strings will have overlaps and those are what we are interested in. There are string matching algorithms that generate such automaton in linear time and it is smaller than the lengths of paths.
With the given automaton, we can find overlaps and use them to find the overlapping paths.
Assuming that we have automaton passed in as character lists as parameters to the function below, we get intersections of the automaton as follows:
List<List<Char>> GenerateIntersections(List<Char> a, List<Char> b)
{
var ret = new List<List<char>>();
for (int i = 0; i < a.Count; i++)
   for (int j = 0; j < b.Count; j++) // we can also make it linear by skipping ahead.
{
     int m  = i;
     int n = j;
     var match = new List<Char>();
     while (a[m] == b[n] && m < a.count && n < b.count)
     {
         match.Add(a[m]);
          m++;
          n++;
      }
     if (match.IsEmpty() == False && ret.Contains(match) == false)
         ret.Add(match);
}
return ret;
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.  A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities.Any single data fragment can decoded from k/l fragments within its local group. In addition, LRC achieves maximally recoverable property It tolerates upto r+1 arbitrary fragment failures. It also tolerates failures more than r+1 and upto l+r as long as they are information-theoretically decodeable.  Finally LRC provides low storage overhead. It requires the minimum number of parities as compared to other such codes.
The choice of the k,l and r parameters for LRC code is dependent on the reliability outcomes. At a minimum, three-replication is required. This is an industry standard. Higher reliability can be achieved by choosing the parameters with a Markov reliability model.  This model considers both independent and correlated failures. The model is extended by LRC to capture unique state transitions. Those transitions are introduced because the failure mode depends on not only the size of the failures, but also which subset of nodes fails.  Each state in the Markov process represents the number of available fragments (data and parity). Let lambda denote the failure rate of a single fragment. The transition rates from all fragments healthy state N to state N-1  is N times lambda.  Let pd denote the percentage of four decodeable failures. Then the transition state to decodeable failures is N lambda pd and that for non-decodeable failures is N lambda (1-pd) The reverse transition going from a lower state to a higher state is equal to the average repair rate of a single fragment.  Repair rates beyond a single failure are dominated by the time taken to detect failure and trigger repair.
#codingexercise
Normalize two strings with a common pattern into substrings that don't have any overlap.
List<char> normalize(List<char> a, List<char> b)
{
var ret = new List<char>();
// assume one pattern to match
var match = a.Intersect(b);
var fragmenta = a.Except(match);
ret.add(fragmenta);
ret.add(match);
var fragmentb  = b.Except(match);
ret.add(fragmentb);
// repeat the above for more matches based on regex groups or KMP
return ret;
}
In a graph, the branches of a minimum spanning tree are normalized paths 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing how to construct the coding equations. The coding coefficients for each group are assigned elements from a finite field and the elements are represented by four bits. The coding coefficient for one group are chosen with their lower order two bits as zero and that of the other is chosen with their highest order two bits as zero. This way they will never be equal and they satisfy the conditions that they are not individually zero and the groupwise sum of the coding coefficients are not equal.
This way all the three failure patterns can be decoded and about 86% of all the four failures. In short, the LRC achieves the maximally recoverable property.
A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities and r global parities. The key properties of a (k,l,r) LRC are as follows: i) single data fragment failure can be decoded from k/l fragments ii) arbitrary failures up to r+1 can be decoded. The paper proves that the number of parities of LRC meets the lower bound exactly, LRC achieves its properties with the minimum number of parities.
#coding exercise
Given  a set of Paths between nodes in a graph as a string of nodes with overlaps, normalize them by splitting. Overlaps have to include one of the ends of the string and cannot be size less than or equal to two.
We compare strings pairwise to detect overlap.  This is an O(N^2) comparisions
However each detection need not cost to the order of the square of the number of elements.
For each pair, we detect the overlap by applying Knuth Morris Pratt which yields O(N) running time. KMP informs the maximum amount of one string matched at the end of other.

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing how to construct the coding equations. The paper says there are four coding equations. The coding coefficients are determined by four different cases - when none of the four parities fails, only one of the px and py fails, and  both px and py fail.  The coefficients of the first set are chosen among the elements whose lower order 2 bits of coefficients and their sum are zero. The coefficients of the second set are chosen among the elements whose higher order 2 bits of coefficients and their sum are always zero.  Hence they will never be equal. The advantage is that this way of constructing coding equations requires a very small finite field and makes implementation practical. This makes LRC decode arbitrary three failures. To check whether a parity is information theoretically decode-able 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing the design decisions such as why Reed-Solomon code was not sufficient and why the paper introduced a new one. We also saw how the Local Reconstruction code introduces group fragment parity and improves reconstruction cost. This is with some storage overhead but provides more options with a new trade-off point. We discussed the coding equations and LRC's maximally recoverable property which is a way of saying LRC can decode any failure pattern which is possible to reconstruct.
The challenge was to find a set of coding equations that achieves the maximally recoverable property
These coding equations were found this way:
LRC can tolerate arbitrary 3 failures by choosing the following two sets of coding coefficients a and b for groups x and y.  For each group, each coefficient is linearly applicable for each of the three failures, or applicable as the squares or none at all.  The same goes for  the other coefficient for the other group.  This gives us six equations.
Then the LRC's coding equation are as follows: the sum of the linear coefficients of each group as p0, the sum of the square coefficients of each group as p1, the no coefficients case for one group as px, and the no coefficients case for the other group as py.
These coefficients can then be found by applying the following scenarios:
None of the four parities fails
Only one of the px and py fails
Both px and py fail
To ensure all the cases are decodable, all the matrices should be non-singular which leads to the following conditions.
None of the coefficients are zero.
None of the coefficients of group 1 are same as that of group 2
the sum of the coefficients of group 1 should not be the same as the sum of the coefficients of group 2.
#codejam problem
Determine sums of list of integers
public static List<int> Sums( this List<List<int>> numbers)
{
var ret = new List<int>();
numbers.ForEach (x => ret.Add(x.Sum()));
return ret;
}
Could we consider implementing extension methods in C++ ?
In C++ we have the ability to wrap classes and structs if we cannot inherit from them. Therefore we can add methods easily as function pointers or methods.

 We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing the design decisions such as why Reed-Solomon code was not sufficient and why the paper introduced a new one. We also saw how the Local Reconstruction code introduces group fragment parity and improves reconstruction cost. This is with some storage overhead but provides more options with a new trade-off point.
We now look at Fault Tolerance. We saw how data fragments are used to compute each parity in LRC. We now see how the parities are computed from the data fragments. These are called coding equations.They have maximally recoverable property. By this property, LRC can decode any failure pattern which is theoretically decodeable. For example a 6,2,2 LRC contains four parity fragments and can tolerate upto four failures but these failures cannot be arbitrary.  If the failures are on x1, x2, x3,  and px, then this failure pattern is non-decodeable. There are only two parities which are global and they can only help to decode three missing data fragments and py is not available. It is impossible to decode three data fragments from merely two parity fragments. Such failure patterns are called information-theoretically non-decodeable

#codejam problem
We were discussing sums generated from number sequences.
This has a dynamic programming approach as well
The range of sums that can be generated
In general, if the range of sums that can be generated using the first k numbers in the result is from 0 to r, and the next number has value x, then either:
• x <= r+1 and it is possible to generate any sum from 0 to r+x using the first k+1 numbers, or
• x > r + 1 and it is not possible to generate the sum r + 1, since x and all the following numbers have greater values.

MaxSumImpossible(Numbers, I, j)
If len(Numbers) == 1
   Return Numbers[0]
m[I,j] = 0
For k = 0 to j-I-1
     if (jth coin <= MaxSumImpossible(Numbers Choose K, I,j-1)
           q =   MaxSumImpossible(Numbers Choose K, I,j-1) + MaxSumImpossible(Numbers with jth Number only, j,j)
     If q > m[I,j]
             M[I,j] = q

  return m[I,j]

 We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing the design decisions such as why Reed-Solomon code was not sufficient and why the paper introduced a new one. Today we continue to read Local Reconstruction Codes.
The Reed-Solomon code explains the concept of a reconstruction cost. In this method, each parity is computed from all of the data fragments.Therefore a (k,n) code will require all k fragments for parity. When any fragment goes down, the number of fragments required to reconstruct is k.  This is the reconstruction cost.
In LRC, this is reduced by reducing the number of fragments used to compute a parity. A subset of data fragments is used to compute some of the parities. In a (6,3) code, LRC generates 4 instead of 3 parities where the first two parities are global parities and are computed from all the data fragments. The other two parities the LRC divides the data fragments into two equal size groups and computes one local parity for each group. Instead of reading a global parity and all of the remaining data fragments, it is now more efficient to read the parity from the group and any two data fragments in that group to reconstruct the missing parity. The reconstruction of any single data fragment requires only three fragments, half the number required by the Reed Solomon Code. This is true for any single data fragment. The addition of a data parity block could be called a storage overhead but this is an altogether different tradeoff point from earlier.
To generalize the subgroups and the extra parity needed, a (k,l,r) LRC divides k data fragments into l groups, with k/l data fragments in each group. It computes one local parity against each group.  In addition, it computes r global parities from all the data fragments. The reconstruction cost reduces from n = k to n = k/l with a storage overhead of (k+l+r)/k
#codingexercise
we discussed the codejam problem yesterday
we mentioned a solution as
List<int>GetOriginalSet(List<int> a)
{
var ret = new List<int>();
for(int i = 0; a.Count > 0 && i<a[a.Count-1]; i++)
{
if (ret.Combinations().Sums().Contains(i) == false && a.Contains(i)){
    ret.Add(i);
  }
}
return ret;
}

Today we continue reading the paper "Erasure coding in Windows Azure storage" by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We saw that there are huge cost savings with this method because it saves three copies and uses less storage overhead. The tradeoff for using erasure coding instead of keeping three full copies is performance. The performance hit comes when dealing with a lost or offline data fragment and with hot storage nodes. In Erasure encoding, data is broken into k fragments and a set of parity fragments. In WAS, a data fragment may be lost due to a disk, node or rack failure. In addition, cloudservices may frequently be upgraded. This may cause data fragments to become offline for seconds to a few minutes. An online read would then need to be served by dynamically reconstructing the data being asked for to return the data to the client. This reconstruction needs to be optimized to be as fast as possible and use as little networking bandwidth and I/Os as possible and to meet the SLAs required. If the read is for a fragment that is on a specific storage node, it can become hot that leads to latency.  One way to reduce this would be to age the fragments appropriately and tier the data between memory and external storage.Another way would be to load balance. But until the fragment becomes hot, read performance can suffer. Instead if the reconstruction could be done in parallel while the fragment was being fetched from storage node, then the one that returns earlier can be returned
The problem is that the reconstruction is only as fast as the slowest storage node to respond to reading. We also have to keep storage costs low as well. We could do this with Reed-Solomon codes that keeps 12 data fragments and 4 code fragments. However reconstruction would require all of those 12 data fragments and this will incur higher network costs and I/Os as well as the chances of hitting a hot node.
Therefore a new family of codes was required. This had the following design requirements: First, reduce the minimal number of fragments that need to be read from to reconstruct a data fragment.
Second provide significant reduction in storage overhead while maintaining higher durability than a system that keeps 3 copies of the data.
The authors call this the Local Reconstruction Codes.
#code jam problem
Given a set of integers, a powerset is a combination of all such elements including the null and the set itself
To generate the powerset of the elements we can use the combine method where we combine different numbers of elements. We just have to include the null set and the set itself.
Now we are given a powerset with the sums of each individual set in sorted order. We are also given the frequencies of the sum. Can we determine the original elements ?
For example if we have a powerset with sums
0,1,2,3,4,5,6,7, and frequencies
1,1,1,1,1,1,1,1,
will result in a set of 1,2,4
Solution:
The result set is also non-decreasing like the original power set sum
It has a few zeroes in the beginning both from null set as well as non empty set and this can be found from the first sum
And for each sum given, we can expand the sums as an element  for occurrences that we can determine from the frequency
   Next with the help of a running lists of sums computed so far and initialized by 1 at the position given by the current element, we add the value of the sum to a new list at the current location as well as the location offset element a. Since we are adding elements incrementally by 1 and including it in the result only when the sums tally, we get a final list of numbers found by incrementing 1s. 

Today we start reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.

Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS where customers can store unlimited data for any amounts of time. They only pay for what they use. Erasure codes help with the durability of the data and to keep the costs low. This paper introduces a new set of codes for Erasure coding called Local reconstruction codes (LRC). LRC reduces the number of Erasure coding needed to reconstruct the data fragments that are offline. It also reduces the storage overhead involved. LRC reduces the bandwidth and io required for repair reads over prior codes. This together with the low overhead is the main benefit of LRC  LRC also demonstrates consistently low read latencies.
WAS uses LRC. WAS stores all of its data in an append only distributed file systemcalled the stream layer. Data is appended on to the end of active extents which are replicated three times by the underlying stream layer. These three copies remain till the extent gets filled. Once the extents are full, they are sealed and are never modified again. A background process lazily generates Erasure codes for the sealed extents and deletes the three copies which are no longer needed.
Erasure codes can reduce the cost of storage by 50% and given the size of cloud storage is in the order of exabyte, this is a significant saving.
#code jam question
Given two ominous find the minimum number of rearrangement needed to transform one omino into another.
Ignore rotations and translations of both oninoes. Oninoes are groups of unit squares joined together on one or more edges.

Solution since the two ominoes are properly oriented and centered for comparision.
We proceed row wise parity from bottom to top. If the number of unit squares in the bottom row are short for being equal, then more is borrowed from the row above or returned otherwise. When the numbers are equal, the sequence has to be the same.

Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs that don't fit on a single server. The paper introduces Horton a graph query execution engine. We were reviewing its architecture.
It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager.We saw that the implementation was in C# using Codebook graphs. This is a social network application that represents software engineers, software components and their interactions in large software projects.  Codebook manages information about source code with its revisions, documentation and the organizational structure of developers. It can answer queries such as "Who wrote this function?" "what libraries depend on this library", "Whom should I contact to fix this bug"
We review the query processing phases. For example,
"Who wrote the specification for the MethodSquare code ?" translates to query such as
C:\ Horton -query *(Code MethodSquare) MentionedBy WordDocument AuthoredBy Person*
and "Who is the manager of the person who closed or created work item bug #673 ?" translates to
C:\Horton -query "Person Manages Person (Closed | Created) (WorkItemRevision #673)"
The finite state machine for the latter query makes the following changes:
Node_Type = person
Edge_Type = Manages
Node_Type = person
Edge_Type = closed                                         Edge_Type = created
Node_Type =                                                   Node_Type =
WorkItemRevision Node_ID = #673                 WorkItemRevision Node_ID = #673
The above finite state machine has a disjunction for closed and created cases.
If the query were to be optimized a '-query' will be added.
The system reports the execution time of each query. The query result is in the form of graph paths ( a sequence of graph nodes).
#codejam
Given two orientations of the same ominoes as in the earlier posts, determine whether the clockwise or the anticlockwise is the shorter transition from one to the other.
int countl = 0;
for (int i = 0; i < 360; i+=90)
   var temp = rotate_matrix(matrix, i);
   countl += 1;
   if (compareTo(matrix, temp) == 0)
     return count;
countr = 0;
for (int i = 0; i < 360; i+=90)
   var temp = rotate_matrix(matrix, 0-i);
   countr += 1;
   if (compareTo(matrix, temp) == 0)
     return count;
if (countl < countr) return -1;
if (countl > countr) return +1;
if (countl == countr && countl == 0) return -1;
return 0;

Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs that don't fit on a single server. The paper introduces Horton a graph query execution engine. We were reviewing its architecture.
It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager. We discussed the first three components. We now look at the Graph Manager. This provides an administrative interface to manage the graph such as loading a partitioned graph or adding and removing servers. It also assigns partitions to the servers by taking the output of  partitioning algorithm and placing nodes in the right partitions. Partitioning algorithms are external because they are not online. Any algorithm can be used such as a simple hashing that's based on node and edge attributes. If the partitions don't suffice in keeping graph access local, then the partitioning algorithm can be changed.
Horton is written in C# using the .Net framework and the asynchronous communication is implemented using sockets and task parallel library.Horton is built on top of Orleans which is a distributed runtime for cloud applications.
Some sample queries on the graph for Codebook using Horton include the following:
Who wrote this function ?
What libraries depend on this library ?
Whom should I contact to fix this bug ?
Adhoc queries can also be executed showing the flexibility of the query language and the effectiveness of the execution engine.
#codejam problem
We discussed compareTo between ominoes in the previous post that takes different orientations and then compares. Tanslations and different positions in the matrix can also make the ominoes look different. Implement compare for ominoes with same orientation

int compare(int[,] matrix1, int[,] matrix2, int rows, int columns)
{
int k = find_top_left_corner(matrix1);
int tr1 = k /columns;
int tc1 = k % columns;
int h = find_bottom_right_corner(matrix1);
int br1 = h/columns;
int bc1 = h%columns;

k = find_top_left_corner(matrix1);
int tr2 = k /columns;
int tc2 = k % columns;
h = find_bottom_right_corner(matrix1);
int br2 = h/columns;
int bc2 = h%columns;

for (int i = 0; i <= br1-tr1; i++)
  for (int j = 0; j <= bc1-tc1; j++)
       if (matrix1[br1+i,bc1+j] != matrix [br2+i, bc2+j])
           return matrix1[br1+i,bc1+j] - matrix [br2+i, bc2+j];

return 0;
}

In comparing the sequences of 1 and 0 for the portion containing the arrangementsame in the two matrices, we pick the diagonal corners of the bounding rectangle. To determine this we pick the
Min pair (r, c) and max pair  (r,c) from all those having value 1
Int r = k;
Int c = k;
For  (int I = 0; I < k; i++)
For (int j =0; j < k; j++)
If ( matrix1[i, j] == 1 ){
   If (I < r) r = i;
   If (j < c) c = j;
}

Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs that don't fit on a single server. The paper introduces Horton a graph query execution engine. We were reviewing its architecture.
It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager. The graph client library sends queries to the graph coordinator which prepares an execution plan for the query. The graph partition manages a set of graph nodes and edges. Horton is able to scale out mainly because of graph partitions. The graph manager provides an administrative interface to manage the graph with chores like loading and adding and removing servers.
We review these in detail.
The graph coordinator receives the query from the client library, validates it and parses it, optimizes a query plan and translates it into a finite state machine which is sent to the partitions for parallel execution.  The validation involves checks against the nodes and edge predicates. The optimization involves taking a query in a parsed regular expression form, enumerating the different execution plans and choosing the one with the lowest cost. It uses a dynamic programming framework to enumerate the execution plans and to choose the one with the lowest cost. One example of optimization is to order the predicates.  A good choice of predicate order can save costs that are orders of magnitude different from each other. If n is the number of predicates in the query, this method finds  a suitable choice in O(n^3). After the query is optimized, the query plan is translated into a finite state machine The state machine not only expresses the execution efficiently but also packages it in a way that can be easily sent to local graph partitions for execution by their local engines. The communication to send state machine and get results is done in an asynchronous manner which allows for the results to be directly streamed from a graph partition machine to the client without involving the graph co-ordinator.
#codingquestion
In the previous examples we used NChooseK as a recursive function to find K from N. If we were to partition the data, we could rewrite this

void NChooseKPartitioned(int N, int K, ref List<int> array, int start, int count)
{
m = N/2;
n = K/2;
return NChooseK(m,  n, ref List<int> array, start,  count) + NChooseK(N-m,  K-n, ref List<int> array, start,  count);
}

To compare if two ominous are the same by change of orientation or position
Int compareTo (int [,] matrix1, int [,] matrix2)
{
For (int i=0; I < 360; I += 90)
{
    var rotated = rotate (matrix1, i);
    If (compare (matrix2, rotated) == 0)
         Return 0;
}
Return count-of-1 (matrix1) - count-of-1 (matrix2);
}

Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs. These graphs don't fit on a single server. Map-Reduce and Pregel are not good enough for processing interactive adhoc queries against large graphs. Horton is different. Let us take a look at its architecture. It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager. The graph client library sends queries to the graph coordinator. It uses an asynchronous messaging system to receive results. The graph coordinator prepares an execution plan for the query. converts it to an automata and decides which partition to run. Each partition runs the executor and returns the results back to the client. The partitions are managed by the graph manager. The relevant partition is transfered to main memory and back to persistent storage.
The graph client library - sends queries to the graph coordinator in the form of regular expressions, and receives the query results directly from the graph partitions.
The graph coordinator provides the query interface for Horton. It receives the query from the client library, validates and parses the query. The coordinator optimizes the query plan and translates the query into a finite state machine. This is then sent for parallel processing over the partitions.
Every graph partition manages a set of graph nodes and edges.Horton is able to scale out only because of partitions. The automata received from the coordinator is executed on the local partition using a local query execution engine.
#codejam continued
Yesterday we were filling a linear array of size n with k elements of value 1. We called it NChooseK. Today we would like those arrangements of NChooseK where K are contiguous.

void NChooseKContiguous(int N, int K, ref List<List<int>> arrays)
{
debug.assert(N>K && N > 0 && K > 0 && arrays!= NULL);
for (int i = 0; i < N-K+1; i++)
{
var array = new List<int>(N);
array.AddRange(Enumerable.Repeat(0,N));
for (int j = i; j < K; j++)
    array[i] = 1;
arrays.add(array);
}
}

Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs. These graphs don't fit on a single server. Map-Reduce and Pregel are not good enough for processing interactive adhoc queries against large graphs.Horton is a distributed interactive query execution engine for large graphs. We were reviewing that large graphs pose a different challenge from a number of small graphs. The latter has examples in bioinfomatics and chemoinformatics. Moreover, the conventional solution for querying large graphs based on offline batch processing is different from the corresponding online interactive query requirements. To manage large graphs online while supporting querying with small latency, a new system was required to be built. Horton provides a graph query execution engine and a graph query optimizer that is able to efficiently process online queries on large graphs. Further it uses a design decision to partition the graph among several servers in order to facilitate online processing. Horton stores the graph partitions in main memory to offer fast query response time.
We now review Horton data model and query language. A graph database stores not only the nodes or entities but also the relationships or connections and these connections can have rich attributes.
Horton too supports rich graph data. Nodes represent entities and have types as well as a set of key value pairs representing the data associated with this entity. Edges have type and data as well. There is no restriction on the kind or amount of data associated with nodes and edges. Horton manages both directed and undirected graph.If the graph is directed, each node stores both inbound and outbound edges
Queries are in the form of regular language expressions. A query is a sequence of node predicates and edge predicates. Each predicates can contain conjunctions and disjunctions on node and edge attributes as well as closures. For example, a query to retrieve a list of all the photos in which John is tagged is expressed as Photos-tagged-John. In this case all paths in the graph that satisfy the query expression are returned. To get a specific part of the path such as a node, a SELECT statement is used.
Select photo from Photo-Tagged-John. Here the node photo is the only one but there could have been other nodes and edges in the query
The syntax is helpfully closer to SQL unlike Cypher. This was also a design decision  In general, graph databases perform better than relational in highly interconnected data where a nearly online data warehouse is required.
#codejam continued
Fill a linear array of size n with k elements of value 1

void NChooseK(int N, int K, ref List<int> array, int start, int count)
{
if (count ==k) { // print array  and return; }
if (start == N) return;
for (int i=0; i < 2; i++)
{
if (i == 0) NChooseK(N,K, ref array, start+1, count);
else{
array[i] = 1;
NChooseK(N,K, ref array, start+1, count+1);
array[i] = 0;
}
}
}

Today we start reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs. These graphs don't fit on a single server. Map-Reduce and Pregel are not good enough for processing interactive adhoc queries against large graphs.Horton is a distributed interactive query execution engine for large graphs. It includes a query execution engine and a query optimizer that allows interactive execution of queries on large distributed graphs in parallel. In this paper the graph for study came from a social networking application called Codebook which uses a graph to model data on software components, developers, development artifacts and their interactions in large software projects. This kind of information about  software engineers, software components, and their interactions in large software projects such as the Windows or Linux Operating Systems results in large graphs. Online querying of large graphs is very different from conventional database querying. Conventional databases store highly structured data and there is never a join performed without a join table that holds the foreign keys of both participating tables. Moreover in relational databases, references to other rows are indicated by referring to their primary key attributes via foreign columns. This is enforceable with constraints but only when the reference is never optional. Joins are computed at query time that is both compute and memory intensive. Graph databases are an improvement where the relationships are the first class citizens of the graph data model. Nodes and relationships are assembled into connected structures. Each node in the graph database model directly and physically contains a list of relationship-records that represents its relationship to other nodes.Although a graph database stores connections as first class citizens readily available thereby avoiding relationship computations at query times, it explores the larger neighborhood around the initial starting point leaving billions outside the search perimeter. Neo4j implements such a NoSQL graph database. The Map-Reduce framework can help with such queries but they are meant for batch processing not online queries. Even though their throughput can be increased to be at par with a low latency online query, they are fundamentally not the same.  The paper describing Pregel states that graph algorithms often exhibit poor locality of memory access, very little work per access, and a changing degree of parallelism over the course of execution. Distribution over many machines and their faults makes the locality issue even worse. Arguably such data can be stored as distributed database clusters but even then there is no easy way to state reachability queries in the relational world. Besides large graphs pose a different challenge than hundreds of smaller graphs. Horton partitions the graph in among several servers and stores the graph partitions in main memory to offer fast query response time. The partitioning is horizontal to scale with the machines in the data centers.

#codejam problems
We have seen what ominoes are in the exercise described earlier. K-ominoes are some arrangement of K unit squares so that the unit squares remain joined on one or more edges. Determine how many different ominoes there are for a size k.
int GetOminoes (int k)
{
Int count = 0;
Var matrix = new int [k,k];
var ominoes = new List<int[,]>();
GetCombinations ( k, ref matrix, 0, ref count, ref  ominoes);
Return count;
}

Void GetCombinations ( int k, int [,] matrix, int level, int ref count, List<int[,]> ominoes){
if (k==0) {
   if (ominoes.Any(x => x.compareTo(matrix) == 0) == False)
   {
      count += 1;
      ominoes.Add(matrix);
   }
   return;
}
for (int base = k; base  >  0; base--)
{
if ( level == 0) { // contiguous occupancy k choose base  }
else{ k choose base }
if (any-islands) continue;
GetCombinations(k - base, matrix, level + 1, count);
// reset occupancy
}
}

One way would be to
// fill the matrix with k 1s
// Eliminate those that are disjoint
// Ignore duplicates from rotations and translations or comparing two distributions rowcounts and columncounts sequences with all of four orientations

Another way would be to sequentially reduce the base from k to 1.
At each chosen base m  increase levels with recursion for the remaining by choosing base from k to 1. For each chosen base and level, find different positions or arrangements linearly

A graph is a convenient data structure to represent such things as social networks, word relations etc.
Operations on directed graphs are easy to perform if there are no cycles.
To determine if a directed graph is acyclic, we discussed a method but didn’t review the proof.
Let’s take a look at it now:
DFS ( V, E)
For each vertex v in V
       V.color=white
       V.d = nil
  Time = 0
 For each vertex v in V:
       If v.color == white:
              DFS-Visit (V, E)
     
 DFS-VISIT (V,E, u)
  time = time + 1
   u.d = time
   u.color = gray
   foreach  vertex v adjacent to u
        If v.color == white
           DFS-VISIT(V,E,v)
         Else
               If v.d  <= u.d < u.f <= v.f  throw back edge exception.
 u.color = black
time = time + 1
 u.f = time

This method is called topological sorting. Essentially this method says that
 there exists an order in which the
vertices can be listed such that if u is before v in the
list then there is no edge from u to v.This is called
"topological order". It’s easy to prove this. Consider the vertices listed in the order v1, v2, v3 … vk, … vn
This means that each successive call is to the next neighbor.
Let us traversed vk. Let w be the one adjacent to vk. Then there are two cases
W.f != nil  in this case DFS-VISIT (w) has already completed do w must have already been listed.
W.f == nil  in this case the last thing that happens is vk is printed. Therefore w would be printed before then.
Therefore when an element is printed, each element adjacent to the original element has already been printed. This is topological sorting.
We now discuss connected components . This is a way to test the bipartiteness of a graph. A bipartite graph is one that does not have an odd cycle. Here we label each vertex with a component number such that two vertices are connected if and only if they have the same component number.

The DFS for this looks like this :
for all v in V do visited(v) = 0
   c = 0
   for all v in V do {
       if (visited(v)==0) {
           DFS_VISIT(v)
           c = c+1
       }
   }

   DFS_VISIT (v) {
      visited(v) = 1
      comp(v) = c
      for all w in adj(v) do if (visited(w)==0) DFS_VISIT (w)
   }


Now we determine the bipartiteness this way
for all v in V do visited(v) = 0
   for all v in V do if (visited(v)==0) DFS_VISIT (v,0)

   DFS_VISIT (v,p) {
      visited(v) = 1
      part(v) = p
      for all w in adj(v) do {
          if (visited(w)==0) {
              DFS_VISIT (w,1-p)
          } else {
              if (part(v) == part(w)) print "graph not bipartite"
          }
      }
   }

Courtesy: Sleator notes CMU

Gradle versus Jenkins

Gradle is a build automation system that enables a continuous  pipeline for software as and when it is written. It has become a favorite for open source projects and comes with the following advantages
1) Applicable to nontrivial projects
2) Enables complex build to be portable
3) Seen as a just right balance between ant and maven
4) Allows for convention over configuration
It helps take the software from a developers machine to the production system after eliminating the delays and errors that plagued this process.

Jenkins  attempts to build and push code to staging systems.attempts it comes with a few features such as
1) integration with source control systems
2) polling mechanism for changes
3) cron for scheduling
4) integration with cloudfoundry for pushing code
The advantages of Gradle are :
1) It can handle build dependencies as a directed acyclic graph
2) It can exclude certain tasks
3) It has powerful language constructs to determine build order
4) When tasks are excluded, their dependencies are also excluded.
5) Tasks can be used to finalize another task
6) Builds are easier to maintain and more robust because tasks and their output are known
7) Gradle enables multiple tasks to be executed
8) It can continue execution after failure
9) It can permit dry run
10) It creates meaningful output while allowing rerouting to external tools

Gradle essentially guarantees that the dependency graph is acyclic and it performs a lazy evaluation.
To determine if a directed graph is acyclic:
DFS ( V, E)
For each vertex v in V
       V.color=white
       V.d = nil
  Time = 0
 For each vertex v in V:
       If v.color == white:
              DFS-Visit (V, E)
     
 DFS-VISIT (V,E, u)
  time = time + 1
   u.d = time
   u.color = gray
   foreach  vertex v adjacent to u
        If v.color == white
           DFS-VISIT(V,E,v)
        If v.d  <= u.d < u.f <= v.f  throw back edge exception.
 u.color = black
time = time + 1
 u.f = time

In the ominoes problem described in the previous post, we observe the following:
if (X  > 6) then Richard wins
if (X  < 3) then Gabrielle wins
if (min(R,C) < (X+1)/2) then Richard wins
if (X==3) then Gabrielle wins
if (X == 4) then Gabrielle wins if min(R,C) > 2 else Richard
if (X == 5) then there must be at least three pieces to place for Gabrielle to win.

Another way to look at this problem is to a pick out the conditions based on Board size. This simplifies the problem.
If the board cannot be occupied all by x square units then Richard wins.
If the board is linear  and it has size more than two square units then Richard wins.
If the board is square and there is only one piece possible then Richard wins. Everything else Gabrielle wins.