Cloud Computing History

T(his Story) of Cloud

World is evolving and the story of cloud computing is no different. Let me take you to the history and this story of cloud computing evolution..
Earlier the mankind was restricted to PC (Personal Computer), had very low memory, CPU power and storage. As it was personal, so people could barely manage to organize their work (with very light weight applications) and still would call themselves ‘sophisticated’. Then came in the need for sharing data with people around them, hence floppy drives came to their rescue, but eventually it increased their greed for sharing data with friends across geographically location. However, with the existing technologies at that time, this was just not possible unless they burn magnetic disks and send them via post but was frustrating. This again raised need for physical long distance connectivity.
This was one of the paradigm shift in the world of computer infrastructure and applications when LAN network came along and connected personal computers via Ethernet in relatively large area but restricted to offices only, this was further enhanced to WAN network to connect PC(s) form geographically apart locations. Such network was created by connecting tons of routers(for WAN network) and switches(LAN network) and formed a humongous network of networks for PC(s) all around the world. World wide web (WWW) concept was created to exploit this network of networks and made one largest application ever by mankind called ‘internet’, where people can communicate with each other irrespective of geographical and technical boundaries but again had restricted access. 
At this time everything was in perfect harmony until we realized “Need For Speed”, in terms of communication bandwidth, computing speed and large storage. This is when hardware companies realized and enhanced their devices power multiple folds (it be CPU, memory, faster Integrated circuits, etc). Software companies too developed powerful applications with complex logic and mathematical operations, which was not possible with low speed devices. A new dimension was added to this race of speed when wireless technologies joined. Wireless and Wireline technologies then evolved to such a high degree that cost per bit came down and computing power increased multiple folds. 
With High Computing power, fast and large memory banks, unlimited storage, and super fast connectivity, what could have happened? Yes, a new need has arisen which we call Cloud and brought endless opportunities too.   
To give you some perspective about the SIZE OF INTERNET:
1. The Indexed Web contains at least 4.4 billion pages (Friday, 09 January, 2015).  Source 
2. Total number of websites. Source
3. How Big is the internet. Source 
This is when cloud concept started where all the required basic ingredients were ready and recipe to be prepared. Cloud is where all the user data get stored, processed, computed and analyzed using cloud applications rather then native applications. Data has become system agnostic and can be seamlessly accessed across applications from almost any device and Operating system. 
Cloud is where there are no logical boundaries in terms of dimensioning, and you can make/break a computing system on the fly and pay just for your usage. In fact cloud is so much configurable that it is categories into following based on customer needs:
  1. Infrastructure as a Service (IaaS) 
  2. Platform as a Service (PaaS)
  3. Software as a Service (SaaS)
  4. Network as a Service, etc. 
Need to move to cloud
  • Why to keep user data locally on PC/laptop/tablet/hard-drives/etc, after all there is a limit, 
  • Today every person has multiple IP devices, that can connect to network from anywhere wirelessly and hence can access the same data,
  • Why to compute locally specially for large applications, 
  • Why to purchase native licensed,
How cloud can solve the problem
  • User can store infinite amount of data, there is no limit to it. Single storage multiple devices can access. 
  • Infinite amount of compute engines and on-demand memory. 
  • Load Balancing: User can dynamically scale/shrink their application on the fly.
  • Geographical Redundancy/High Availability: absolutely zero down time. 
  • Caching: Much better performance and user experience. 
  • Zero resource crunch, be it hardware or software.
Economical – Value for Money
  1. Cloud resource are economical and cost effective compared to native resources.
  2. Pay as you Go: Pay for only what you use. 
  3. Companies/Group can buy limited number of cloud license and share it among themselves. 
  4. Flexibility to change if software/hardware/service is no longer a need. 
Concerns:
  1. Security with respect to data protection or valuable user credentials. 

Another example to give you larger perspective about the radical changes happening in the cloud and over all working of an individual are:
Google as we know, believes in radical changes and this time the changes in revolving around cloud. Google is investing heavily to make cloud accessible and affordable for every individual for storage, computation, services and collaboration. To address this need Google has started many initiatives in multiple areas with single goal in mind i.e. Evolve Cloud
  1. Cloud Storage: Google Drive, Drop Box, oneDrive, iDrive, etc. There are many player in this domain who wants user to store data on their storage servers rather then locally. Reasonably big amount of storage is free of cost with backup and lot of software services based in data type: Example you can edit photos or create gallery on google photo
  2. Google Fiber: This is 100 times faster then today’s broadband connection and most importantly, directly to your home. This means high quality and on-demand streaming data/audio/video is completely possible. 
  3. HTML5: This is very promising technology and the vision is very long sited. Next generation browsers will be powered with web-sockets and webRTC that means browser can collaborate much faster. Google is targeting user to use ‘browser’ as the only and de-facto application for all their purposes, which essentially means computer can be thin-client with latest browser on it (Chrome 29 Beta, Mozilla Aurora are the latest browsers with HTML5 support. These are again in beta version and features may be available in the nightly builds), Google ChormeBook, ChromeBox and ChromeBase are such applications. Hangout is one of the examples what a browser can do, it can create browser-to-browser video connection with QoS, image processing on the fly, giving access to hardware like (camera, mic) from browser within without any plugins, far better rendering engine with support for video tags, CCS3, etc. Lot of dynamic part is done in the HTML which was earlier possible via javascript. 
  4. For programmer/developers cloud IDE (Integrated Development Environment) can solve all the development related issues and GITHUB is code repository. For creative/artists/etc cloud license is available for almost all the softwares. 
  5. Web Apps: For all other general purpose applications WebApps can be very handy and effective and runs inside browser. 
Now, let us take deep dive and understand all of these cloud sub-systems one after another, stay tuned … 

Suffix Array

Suffix Arrays

What are Suffix arrays and why are they useful ?

Before learning suffix arrays I would recommend you to read about “tries” here http://algorithmsandme.blogspot.in/2014/03/tries-basics.html.
Question:You have a word for example:”blogger”,you want to print all the suffixes in sorted order or want to find the kth suffix in lexicographical order.
Naive Solution:
In naive solution you just need to find  all suffixes ,save them in an array of string (this will take around O(n2) operation) and sort them in lexicographical order(this will be taking O(n2 log2(n)) so total complexity will be around O(n2(1 + log2(n))) which is quite large.Then finding the kth suffix in it.
All suffixes of word “blogger”:
blogger
logger
ogger
gger
ger
er
Solution using Tries:
In this method we can create the trie for all the suffixes of the word and for finding kth suffix in  lexicographical order, we can pre-process and find lexicographical kth suffix in O(n) (You just figure it out how you can do it).
Even if the idea of suffix trie would be very pleasing,but it’s simplest implementation in which at every step one of the strings suffixes is inserted into structure leads to O(n2) complexity algorithm.There is a “suffix tree” which can be built in O(n) complexity algorithm but creating a suffix tree is quite a long code to write,I will talk about suffix trees in future blogs.Here I will talk about another data structure suffix arrays whose code is quite short to write and it gives around O(n log2(n)) and memory used in implementing suffix array with O(n) memory is 3 to 5 times less than the amount needed by a suffix tree.

Suffix Arrays

Suffix Array is the data structure which stores the sorted form of suffixes of a given strings.It will be more clear after seeing the diagram given below:-

SUFFIX ARRAY


How to build suffix array:

As it is clear from the diagram above, We have to sort the suffixes of the String in lexicographic order for creating suffix arrays. So the big question is How to do it?

We will first sort according to the first character of the suffixes of the string and store it in suffix array, for example:

                                               b  l  o  g  g  e  r
 Suffix array –                             0  3 4  2  2  1 5
Now,we will be gradually increasing the sorting criteria i.e from sorting according to single character to two characters, then four characters and so on in the increasing power of two. Until we have reached a length such that we can be sure all the suffixes of the string are themselves sorted.(it will be more clear from the diagram below). 
So we have “m = ceil(log2(n))” steps to create the suffix array where ‘n’ is the length of the string. Let us denote each step by ‘y’, where 0<=y<=m .At step y we will sort the suffixes according to the first 2y characters of each suffix, For example at step 2, we will sort the suffixes according to first 4 (22) characters of each suffix.

How to optimally implement the above stated condition?
I’ll explain it in step by step manner.

At Step 0(y = 0) :You just sort according to the first character of each suffixes and give sort index(sort index:position of the suffix in the sorted array) to each suffix according to it,if the first character is same for two or more suffixes, give same sort index to  them.See the example below.

Step 0:               Sort-index                        
           b                 0                                              
           l                  3                                            
           o                 4                                             
           g                 2                                            
           g                 2                                              
           e                 1                                             
           r                 5                                             
  

At Step 1(y = 1):We want to sort the suffixes according to the first two characters. For creating the sort-index at step 1 ,take the help of sort-index created at step 0.Create a pair of indexes in which first value is the sort-index of the respective suffix got in step 0 and second value will be the sort-index of the suffix that starts 1 positions later that we obtain in step 0.If the length of the suffix is less than 2 characters, then we can keep the second value  as -1. Now sort according to this pair to get new a sort-index.It will be more helpful if you relate it to diagram given below:   
Step 1(0 – 1)(concatenating at i  with  i + 21):                                 
                                                    Sort-index
           bl                  (0,3)                    0      
           lo                  (3,4)                    4
           og                 (4,2)                    5 
           gg                 (2,2)                    3
           ge                 (2,1)                     2 
           er                 (1,5)                     1
           r$                 (5,-1)                    6

Here ‘i’ denotes index of the suffix starting at position ‘i’ in the string.

At Step 2(y = 2):Same work has to be done at step 2.Here we want to sort according to the first four characters.Create a pair of indexes in which first will be the sort-index of the respective suffix and second will be the sort-index that starts 2 positions later like concatenate bl(1st position) with og(3rd position) to get first four characters of the respective suffix.Do this with all other suffixes and get the sort-index of each position.
Step 2(1 – 2)(concatenating at i  with  i + 21):
                                                  Sort-index
blog           (0,5)                             0
logg           (4,3)                             4        
ogge          (5,2)                             5
gger          (3,1)                             3
ger$          (2,6)                             2
er$$          (1,-1)                            1
r$$$          (6,-1)                            6

Same will happen for step 3.

So to generalize this,if we go from step y to step y + 1 , we will concatenate the sort-index of suffix array starting at position ‘i’ with sort-index at ‘i + 2y‘ to obtain the length of 2y + 1 for creating the sort-index at step ‘y + 1’.

Code for building Suffix Arrays:

Time Complexity:Complexity for building suffix array is O(n*log22n).
Now you can find kth suffix in lexicographical order using suffix array in O(n) complexity.Suffix arrays are quite helpful in competitive programming because they are fast to code.

Application:
1) Compute the longest common prefix(LCP) using suffix arrays.
2) Suffix Arrays are helpful in various string searching and string matching problems.

Questions to practice:
Easy:
http://www.spoj.com/problems/SARRAY/
http://www.codechef.com/problems/TASTR
Medium:
http://www.codechef.com/problems/SSTORY
http://www.spoj.com/problems/DISUBSTR/

Range Sum Using Segment Tree

What is and why Segment Tree?

Take an example of an array = {1 , 4 , 8 , 11, 15, 22} , and task is to find the sum of range say (2,6) , naive approach will be to run the loop from two to six giving us an O(n) time complexity,so if we have q queries it will make it O(n*q), but we can modify it to O(q) complexity if we can pre-compute the sum such that at index “i”, In the pre-computed array we have sum from 0 to index i which make new array as sum[] = {0,1, 5, 13, 24, 39, 61} so now when we are having range sum query like (3,5) we can just compute it by sum[5] – sum[2] which gives O(q) time complexity.

Now a slight modification in question , if we can change any particular number in an array at index i then we have to modify whole sum array from that index ”i” to “n” ,so if we have an alternate query of changing and finding range sum it will be giving us O(n*q) time complexity.Now the Segment tree comes to rescue , by using segment tree we can reduce the complexity from O(n*q) to O(q*log(n)) which is a big difference when n is large. Now we get the answer why Segment Tree?

Segment Tree(Divide and Conquer Solution)

Problem: We have an array arr{0……….n – 1} and we have to perform two types of queries:
                 1)Find sum of elements from index l to r where 0 <= l <= r <= n
                 2)Change value at specified index arr[i] = arr[n]. 
I’ll take about segment in three levels:

Structure
Solution for segment tree will be:
1)If the range contains a single element,the element itself will be in that node.
2)Otherwise divide the range into two smaller ranges,each will be half the size of original.
Recursive function will be written as:
             
Representation:

Level 1: Construction

             In construction of segment tree I’ll give the recursive approach(top down approach), start with root node which leads to a recursive call to it’s two children(see recursive function) which are storing the sum of the range which is half the size of parent node until we reach leaf node which will be storing the original element of an array. And now this recursion will revert back storing sum of it’s child in it’s parent.So,in the parent node we will be having the sum of it’s two child.See the diagram below for more clearity .We will be using an array named as sum[] which will be storing this tree where index “i” stores the sum of parent,it’s child’s sum will be stored at 2*i and 2*i + 1.It will be a full binary tree because we are dividing segment into two parts,so we will be requiring a size of around 2*2^(ceil(log(n))) – 1 to store the binary tree. It is a binary it’s height will be log(n).

I added the code for creating the segment tree:  

Level 2: Query
Now we have created the tree .Since query operation is quite complex  I’ll explain it by example: Suppose we have to query for f(0,4) ,since we can see that there is no such node which is having this range but we can notice that f(0,4) = f(0,2) + f(3,4) and there are nodes in segment tree containing those two ranges so we can conclude that we have a general expression such that f(x,y) = f(x,z) + f(z + 1,y) .

When querying a segment tree, we select a subset of the nodes with the property that the union of their sets is exactly the interval whose sum we seek. To do so, we start at the root and recurse over nodes whose corresponding intervals have at least one element in common with the query interval. Hence, in our example of f(0,4), we notice that both the left and right subtrees contain elements in the query interval; hence, we recurse on both.The left child of the root serves as a base case(See the figure), since its interval is contained entirely within the query interval; hence it is chosen. At the right child of the root, we notice that its left child has descendants in the query interval(figure), but its right does not; hence we recurse on the former and not the latter. The former is now another base case, and it is chosen and then we return the sum of given range.
Time Complexity:Since it is a binary tree so for query it will be taking O(log n).You can check by yourself.

Level 3:Update
Now in update you just have to check the index of the number in which interval it exist then choosing that interval recursively till we reach the leaf of the tree and updating that leaf,now while you are recursing back you just have to update the node in which the index is such that l <= index <=r (l and r is the range of the node,index is the value to be updated).Below is the code for updating the tree.
Time Complexity:Since the height of the tree is (log n),so for worst case time complexity for update will be O(log n).

Questions for practice:
Easy:
http://www.spoj.com/problems/GSS1/
http://www.spoj.com/problems/KGSS/
http://www.spoj.com/problems/HORRIBLE/

Medium:
http://www.codechef.com/problems/QSET
http://www.codechef.com/problems/FLIPCOIN

Knuth Morris Pratt algorithm for string searching

Knuth Morris Pratt (KMP) algorithm for string searching

Problem

You are given two strings – a Text and a Pattern. Determine whether the Pattern exists in the Text or not.
E.g. – Consider a Text ABCDGBCDLM and a Pattern BCD. Final output should be all the indexes where the Pattern exists, here it is 1 and 5 (0 based index).

Naive Method

The naive method is very basic and straightforward. For every position in the Text, consider it as the starting position and see if a match with the pattern is found.

Considering a text and a pattern of small length, this method would work properly giving O (N*M) complexity, where N and M are the lengths of text and pattern respectively.

The C++ implementation of the naive method is given below…

The Knuth-Morris-Prat Algorithm

If we are able to identify all the positions where an existing match of the pattern ends, in a single iteration over the text. This would solve our problem, since we know the length of the pattern it is easy to identify the starting position of the match. Knuth-Morris-Prat algorithm works on this principle.

In this algorithm, we apply the concept of automaton. An automaton is a kind of an abstract object. At each step of this automaton, some information is presented to it. Using this information the automaton goes to a new state from its current state. whenever the automaton reaches its final state, we have found an end position of a match. The general idea behind the automaton is very simple, consider this Pattern – BBABBB.  Let us list all the prefixes of the pattern.

1. Empty string
2. B
3. BB
4. BBA
5. BBAB
6. BBABB
7. BBABBB

Now for every prefix listed above, consider the longest suffix that is also a prefix of it. The suffix should be different from the string itself.

1. Empty string (No suffix for an empty string)
2. Empty string (The suffix is B but it is same as the string itself)
3. B     (BB) (Here B is the suffix that is also the prefix of string BB)
4. Empty string (No suffix is present which is also the prefix)
5. B     (BBAB(Here B is the suffix that is also the prefix of string BBAB)
6. BB   (BBABB)(Here BB is the suffix that is also the prefix of string BBABB)
7. BB (BBABBB)(Here BB is the suffix that is also the prefix of string BBABBB)

Let us call a suffix that is also a prefix of a string a “Partial match” of that string.We can see that if at some point, the pattern matches till BBABB (which is the prefix of the pattern), then there is also a match till AA which is Partial match of BBABB. 
For example : 
Let us consider text : BBBABBABBBA, pattern matches till BBABB (If we check from the 2nd character of the text), since BB is partial match of BBABB, the text also matches BB (BB is the largest suffix of BBABB which is also prefix of it), so if we cannot extend our match of BBABB to full pattern with the text, we can start matching the pattern again starting from the suffix BB(BB is the largest suffix of BBABB which is also prefix of it
         
          0 1 2 3 4 5 6 7 8 9 10   (Indexes)
Text : BBBABBABBBA
             BBABBB
Here we wanted the next character of the text to be A to complete our match but it is B so we can start check for next match from 4th index of text because BB is also a partial match now. 

So here two cases arise, 
Consider  pattern :  BBABBB and some text, and till now we have found a match till BBABB, as shown in the figure below.

           BBBABB…………..(Text continues)
              BBABB    (Match found till BBABB)

Case 1:  If the next character of the text is ‘B’, that means a match is found, we can start checking in  similar manner starting from the next character  of the text to find another match if there is any.
Case 2: If the next character of the text is anything other than ‘B’ that means the match is not found, so we return to the largest partial match of the string we have found match till now (which is BB for string BBABB), now if the next character of the text matches, our match extends, but if it does not match we will find the next partial match of BB and so on until the partial match becomes empty, then we will skip the next character of the text and start  a fresh check.

Let us see the above operations of Knuth Morris Pratt algorithm with an example.
Text – BBBABBABBBA
Pattern – BBABBB
The automaton for the pattern will look like this…


 Step 1: we will start by matching pattern from the first character of the text. Here we found a mismatch at 3rd character. so we will find partial match of BB, which is B and start match from 2nd character of the text. 


Step 2: we when checking from 2nd character, mismatch is found at 6th character of the text, so we start again from the partial match of BBABBB which is BB.


Step 3: we found a match this time at the 5th character of the text.


Now, to find partial matches of prefixes (till we have found a match) of the pattern, we will make an array of length equal to the length of the pattern, let us call it F[pattern_length]. F[i]   
(0 <= i <= pattern_length)  contains the length of longest partial match of a prefix (till we have found a match) of pattern till ‘i’.
So here : F[0] = 0
               F[1] = 0
               F[2] = 1
               F[3] = 0
               F[4] = 1
               F[5] = 2
                  F[6] = 2
The array F not only contains the largest partial match till index i, but also all the partial matches of it, so F[i] is the largest partial match till index i, F[F[i]] is second largest partial match, F[F[F[i]]] is third largest and so on.
let us call it failure function of the pattern.Below is the function to build the array

Now we have to use failure function to find match. whenever we cannot expand the current partial match, we go to next best partial match of the current partial match and so on. If we are unable to expand even the empty string we just skip this character from the text and go to the next one in the text.
Below is the code to do that.


Removing duplicates from an array of integers

Removing duplicates from array

Given an unsorted array of integers, remove all duplicates from it. For example if input array is A = [2,3,4,4,1,2,3,3]
Final output should be A = [2,3,4,1] where duplicates of 2,4 and 1 are removed. Notice that it is not necessary that duplicates are clubbed together in array.

Analysis
First option which comes to mind is to sort given array using quick sort or merge sort with O(nlogn) complexity and then in linear time remove all duplicates as all duplicates will then be together.
Detailed explanation how duplicates from a sorted array can be removed is given in this post :

How about if the constraint is not to sort array first, other way to put this constraint is to say that elements in output array should preserve the order they were in input array.

Some basic algorithm to remove duplicate elements will be to start from first element till the last element repeat following
Check from the next element to last element, if element matches the current element of step 1,
move all the elements on right side of this element by one left. Let’s code it

Complexity of this algorithm to remove duplicates from array will be O(N^3)

Other method of solving this problem is to use binary search tree. Construct a binary search tree using elements of array and discard all elements which are duplicates. Tree will contain only non duplicate values,however, order in original array is not maintained in this solution.

Complexity of above code is O(nlogn) for each node insertion will take O(logn) and there are n nodes to be added.

Last but most efficient solution is to use merge sort and remove duplicates in merge step. This solution requires extra book keeping while merge step of merge sort. I have written the merge sort, book keeping I still need to figure that out, if you have some hints, please comment or drop me a mail.

Virtualizaton and it’s role in cloud computing

Virtualizaton : What is it?

Essentially virtualization means to hide the physical object from user and present to him a copy of underlying object. This object can be anything like hardware, servers, or network. In between real object and the end user, they resides a intermediate layer which provides view of real object to user as per his/her requirement. For example, same hardware is allocated to many users and they install operating systems of their choice on that hardware to use it. Even though there is only one consistent copy of hardware, every user will see it as his copy when accessing through his operating system. Intermediate layer which makes it possible is called as Hypervisor.
There are two kind of hypervisors : Type 1 and Type 2.
Type 1 hypervisor directly runs on hardware while type 2 hypervisors runs on operating system which in turn runs on hardware directly. We will learn more on this as we move forward.Each simulated machine is called as Virtual machine which is complete and sustainable in itself with copy of operating system in and OS believe that it has all the available resources like physical memory, CPU and storage allocated to it. Below picture explains the concept aptly.

NO virtualization

No virtualization

Why virtualization?

Take this example, there is an organization, which has many legacy software to run, however, these software don’t take much of processing power or memory for that matter, So running them on different servers will be too expensive and it might be possible that they may not be able to run new hardware. Here virtualization is best use, Hardware layer is abstracted from legacy software using a layer and all software can run on same server where virtualization layer provides the view of hardware as required by the software.
Other problem can be that there software are developed and run on different operating systems. Here also different operating systems can be installed on same server using same hardware and these software can run on appropriate OS.
Other place when virtualization is used is when user wants to run non trusted application in an sandbox environment and does not want to affect his real environment. 
Resource sharing is the best use case of virtualization. If there is a server which is not used more than 15% of its power by a single user, this can easily be virtulized and many users can use it. Usually servers are designed for peak load with huge storage and memory but on average usage of these resource is well below the peak usage, that leads to wastage of resources.

Server virtualization
Server virtualization

Virtualization brings in efficiency in less cost, where time is spend on innovation rather than deployment hurdles.

Kinds of virtualization

1. Server virtualization

It is mechanism to hide server physical resources like number of processors, memory etc from users.
Server virtualization can be achieved using three models:
Virtual machine based model : In this different virtual machines run on imitation of hardware layer. Different users can use different operating systems without anything to modify in guest OS.
A special hyper-visor software is required to coordinate  between various guest OS and provide hardware abstraction.

Second is called paravirtualization which require modification in guest operating system and guest systems are aware of each other rest all runs as same as virtual machine model.

Third model is operating systems based virtualization, in this model only single operating system runs on hardware and provides services to guest editions, No multiple operating systems are allowed.

2. Network virtualization
In this model, one divides available resource like bandwidth and channels either on time sharing basis or frequency division. In simple words, it is technique to make one physical network appear as multiple  logical networks.
Virtual LAN is example of network virtualization. In virtual LAN, machine can be virtually be in same LAN even though they are physically separated by thousands of miles.

Cloud computing basics

What is cloud computing?

Cloud computing is a paradigm which emphasizes on shared resources rather than local copy of resources on individual machines, these shared resources can be more efficient and powerful than local ones. For example, to make a software developer do his work, one needs a laptop with storage (hardware) and various applications like office, IDES, operating systems etc. (software). Instead of having these resources allocated to each software developer, why can’t we have an arrangement where resources (hardware as well software) are shared and users can log in and use them? That’s where cloud comes into picture.

NIST definition of cloud computing

Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. This cloud model promotes availability and is composed of five essential characteristics, three service models, and four deployment models.

Cloud computing saves organization’s money. Moreover, keeping data at central place makes replication easier and hence enhances reliability. Since resources are shared across all users, these resources can do a much bigger task then individually, hence bringing in scalability. Also, multiple resources can be put on to solve a particular problem for one user as and when they are available, completing that task efficiently.
Cloud Computing paradigm
Cloud Computing paradigm

Advantages of cloud computing or cloud

These are the four terms which come naturally with cloud computing: cheap, reliable, scalable and efficient. Since, I am a programmer, I will explain you how these things are achieved using cloud computing and cannot be achieved using individual host machines.
We will solve a very well-known problem using cloud computing.  Problem is to find longest palindrome substring in a given string. Brute force and dynamic programming solution is give at this post: Dynamic Programming : Find the longest palindrome string
This is third method of solving longest palindrome substring problem.
Create a matrix of N * N where N is length of string.
For forward = 1 to N
For backward N to 1
If str[forward] = = str[backward] => matrix[forward][backward] = TRUE;
Now find a diagonal with maximum number of contiguous 1s in above matrix and that will give you longest palindrome substring.  
For example  : BBABCBACD Longest palindrome substring is ABCBA with length 5
B B A B C B A C D
D 0 0 0 0 0 0 0 0 1
C 0 0 0 0 1 0 0 1 0
A 0 0 1 0 0 0 1 0 0
B 1 1 0 1 0 1 0 1 1
C 0 0 0 0 1 0 0 1 0
B 1 1 0 1 0 1 0 0 1
A 0 0 1 0 0 0 1 0 0
B 1 1 0 1 0 1 0 0 1
B 1 1 0 1 0 1 0 0 0
What is complexity of algorithm? Yes, it’s O (N^2).
Given more resources can this complexity be reduced?  How does cloud computing or parallelism comes into picture here?
We are dealing with matrix here and each column of matrix can be filled independently.
Parallelism opportunity 1: When columns are filled for each character, each column can be filled by a different machine. Pass the character and string and machine will return column filled with 0 or 1 based on the condition.
Parallelism opportunity 2: There are 2 *N forward diagonals in any matrix with N * N matrix. We can pass these 2 * N diagonals (actually we can rely on first N diagonals only) and find length of continuous 1 in those diagonals. The diagonal which gives maximum value, will be the length of longest palindrome string.
Using N machines to solve same problem, complexity is reduced to O (N). That’s where cloud computing adds it value. Consider a case where string length is million character and longest palindrome substring is to be found. If matrix of million * million is created at one machine, surely we will we run into memory issues. Instead, we chose a farm of machines with enough memory and these machines can work on million character at a time for generating columns.  Once columns are generated, same machines can be used to find maximum number of 1 in diagonals and hence longest palindrome string.
There is no data storage involved here, reliability is not a concern although even though one or two machines go down, progress of algorithm will not be affected. From above problem, it is clear that how cloud computing helps in increasing efficiency, reliability as well as making solution scalable.

Cloud computing services providers and companies

I will follow up with more articles on various techniques, tools and concepts which are prevalent in world of cloud computing like virtualization, Software as a Service (SaaS), Infrastructure as a Service (IaaS) etc.

Cloud service models

Infrastructure as a service (IaaS) model

Infrastructure as service model is also called as hardware as a service where physical hardware, network, disk storage etc. is provided as cloud service and managed through virtual machines, Cloud service providers usually charge customers on usage of this hardware. End user does not have to worry about augmenting and upgrades to new hardware which is abstracted.

Platform as a Service (PaaS) model

In Platform as a service model, usually computing environment is provided like operating systems, IDEs, web servers and databases etc. This model works on top of IaaS and user at this layer does not have to worry about complexity of software and hardware layer and he can concentrate on application development. Typical example of PaaS model are Microsoft Azure and Google App Engine,

Software as a Service.

In Software as a Service model, software applications are stored and installed at cloud environment of service provided and user subscribes to it for subscription fee. Good reliability is ensured with very low down time of application, while cloud service provider can employ more resources if application requires them, making it scalable, Software upgrades and installations are not user’s problem.

Types of clouds

Private cloud 
This cloud is most restricted and accessible to a particular group or organization. This clouds are created on request by cloud service providers like salesforce.com or rackspace.

Public cloud
This cloud can be accessed through internet by any user.

Community cloud
This cloud is shared by more than one group or organizations which have similar kind of requirements.

There is one more type which is called as Hybrid cloud which is combination of two or more type of above clouds.