Test driving Push notification in Bluemix

This post is a continuation of my earlier post 'Getting started with mobile cloud in Bluemix'. Here I take a test drive of the push service that Bluemix offers based on the article "Extend an Android app using the Push cloud service" from developerWorks.

This post assumes that you have already completed the changes from my earlier post for the mobile cloud. If you haven't,  you could clone the code from "mobile data" which is the official IBM version of this app and includes all the changes needed for persisting data in the cloud through their Android.

The Mobile Cloud App I created on Bluemix is "mobtvg". The main steps to have Push notification service using Bluemix are

1. GCM services : Get Google API Project number  & GCM API Key
2. Include the Google Play services library project
3. Add the jar files to enable Push service
4. Modify the server side Node.js file to send push notifications to all registered devices
5. Make necessary code changes
6. Run the application and test for notification

Here are more details on the above steps

a) GCM services : Google Cloud Messaging for Android (GCM) is a service that allows you to send data from your server to your users' Android-powered device, and also to receive messages from devices on the same connection. The 1st thing to do is get the Google API Project number & GCM API key.

- Click on Google Developer Console

- Click Create Project. Enter Project name & click Create.

- Note the Project Number on top of the page.

- Click API & Auth on left panel. Click API.

- Scroll down and turn-on Google Messaging for Android

-  Click credentials and click "Create new key". Click server key. Click create

-Copy API key in the Public API access

Now go the Bluemix dashboard and click your application. Click the Push module. In the Configuration tab, scroll down to Google Cloud Messaging and  click 'Edit'

Enter the Google API Project Number & GCM API key for both the Sandbox & Production configuration and click Save.

b) In Eclipse click Windows->Android SDK manager. Scroll down to the bottom and under Extras select Google Play services. Click install. Once the installation is successful import the project as follows File-Import->Android->Existing Android  code into Workspace. Click Next. In the next screen Browse to the path where your ADT bundle is installed and choose the folder

\ sdk\extras\google\google_play_services

and Click Ok. Also  check 'Copy project into workspace'. This will copy.

Now build the Google Play Services Project. To do this the project. Click Project->Properties->Android and make sure that you select 'Is library project' and then click build.

Add a reference to the Google Play services in the Androidmanifest.xml

android:name="com.google.android.gms.version"

android:value="@integer/google_play_services_version" />

c) Make all the code changes given in Step 4 of "Extend an Android app using the Push cloud service.

d) In MainActivity.java make sure you change the app_name to the name of your app for e.g

public static final String CLASS_NAME = "MainActivity";

public static final String APP_NAME = "mobtvg";

Also ensure that under assets folder you have populated the Application ID in the bluemix.properties file

applicationID=<Application ID from Bluemix>

d) Add ibmcloudcode.jar, ibmpush.jar, android-support-v4.jar (from /extras/android/support/v4)

e) Now the Mobile Push project need to include this library project. To do this select your Mobile App project. Click Project->Properties->Android. Click Add and select google-play-services-lib. Note: Make sure "Is library project" is unchecked otherwise you are in for a lot of grief.

f) Now you need to make changes to the Node.js application to push any changes from the server to all registered devices.  The code for this is in bluelist-push-node. Note; Making changes through the GUI results in an error that "manifest.yml is not in root node". So I suggest that you take the 'cf' route as follows.

- Clone the code using Git

git clone https://hub.jazz.net/git/mobilecloud/bluelist-push

Go to bluelist-push-node folder

i) Open the app.js with your favorite editor and enter the Application ID of your Bluemix application

//Data Values

var values = {

version:"0.3.1",

//change this to the actual application id of your mobile backend starter

appID : "",

host : "https://mobile.ng.bluemix.net"

}

ii) Open manifest.yml and change host name & name to the name of your application for e.g.

host: mobtvg

disk: 1024M

name: mobtvg

command: node app.js

path: .

domain: ng.bluemix.net

mem: 128M

instances: 1

iii) Once the changes are complete, open a command propmpt and  login into Bluemix using 'cf' as follows

- cd to the directory in which Node.js & manifest.yml exist, Do

cf login - a http://api.ng.bluemix.net

cf push mobtvg -p . -m 512M

(Note the changes are pushed to the mobile cloud app on Bluemix)

This will run through and finally give the status that the app is running successfully.

f) Now that all changes are complete the Mobile Cloud with Push can be tested..

g) Click Window->Android Virtual Device Manager. Click the Device definitions. You choose Google Nexus, Nexus 7. Click Create AVD.

Note: Make sure you choose Google API Level Y and not Android x.x.x API Y.

Let the AVD come up and display the current items in the grocery list.

h) Login to Bluemix. Click Push and select the Notifications tab and enter a test message for e.g. "This is a notification from Bluemix" and click send.

This will result in a Push Notification to be sent to the AVD. You should see this popup on you AVD as shown below

i) Add another AVD through Windows-Android Virtual Device manager. While one AVD is running go to Run->Run Configurations->Target Device and choose the newly created AVD.

j) This will start a second AVD which will refresh with the contents of the grocery list. Now adda new item in one of AVD devices. This will result in a Push notification to the other device that the Bluelist has been updated.

There you have it.

1) A mobile cloud applications in which changes persist in the cloud and are refreshed each time the Android device is restarted.

2) A Push notification that is sent to all registered devices whenever there is a change to the list.

Disclaimer: This article represents the author’s viewpoint only and doesn’t necessarily represent IBM’s positions, strategies or opinions
[polldaddy rating="7295683"]

Find me on Google+

Getting started with a Mobile Cloud app with Bluemix

This post gives the key steps to get going in building a Mobile Cloud application on IBM's Bluemix. This post focuses on using the Android Platform for building the application. IBM Bluemix'es mobile cloud application includes under its hood mobile services like mobile application security, push and mobile data. A Node.js is also thrown in to provide server-side functions.

The Bluemix Mobile architecture is shown below

 

As in the previous post an existing Mobile cloud application IBM's bluelist -base is cloned to get familiarity with the steps involved. The IBM's bluelist-base app enables the user to maintain a grocery list that persists as mobile data in the cloud instance. To get started perform the following

1) Install ADT + Eclipse bundle from the aforementioned link

2) Unzip and install Eclipse and the ADT bundle

3) Make sure you have the Java JDK for Eclipse. If not install from the following site Java SE Development Kit 8 Downloads

4) Since we will be cloning an existing application and using Eclipse to make the changes we need to install EGit.

5) To do this open Eclipse and select Help-> Install New Software and type in http://download.eclipse.org/egit/updates in the Work with text field and hit enter. You should see the following

6) Once EGit is installed the IBM's bluelist-base App can be cloned as follows

7) In Eclipse click File->Import->Git->Import from Git and click Next

8) Choose Clone URI and Click Next

9) Enter the URI for IBM's bluelist-base. This shown below

10) This will download all the necessary source files and other Android related files and directories into the workspace.

11) After this perform the Steps 2 to Step 6 from the link given Build an Android app using the MobileData cloud service

12) After you make the necessary code changes you are good to go

13) Make sure you right-click and add all the necessary imports required (also Ctrl+Shift + O)

14) Build the Project and make sure that there are no errors

15) You are now ready to run the mobile cloud application. We need to run the mobile app on a Virtual simulator. This can be done as

a) In Eclipse click Window->Android Virtual Device Manager. Click the Device Definitions tab.

b) Choose Nexus 7 (Google) and Click Create AVD.
c) This will open a New Window. Set the following Skin->QVGA and Enter 100 MiB in SD Card size and click OK. This will add this as a AVD.

16) Now run the application.

17) This will bring up the AVD. This takes some time You should see the IBM bluelist showing up as one of the apps.

18) Click on IBM Bluelist. You can add grocery items. These items will persist even if you have to restart your application

19) The data is persisted in the IBM's cloud. This can be checked by logging into BlueMix'es dashboard

20) Click the Mobile Data and the data entered in the AVD device will show up in Data Classes drop down.

21) The Analytics tab will give a graphical output of the API calls

So not the mobile app that is cloud enabled is ready.

Clearly the ability to build Android Apps with the data stored at a cloud opens up numerous possibilities for apps like Evernote, Pocket across several devices.

There you have your first Mobile Cloud App.

Watch this space!

Disclaimer: This article represents the author's viewpoint only and doesn't necessarily represent IBM's positions, strategies or opinions

[polldaddy rating="7295683"]

Find me on Google+

Natural selection of database technology through the years

Charles Darwin in his landmark book “The Origin of Species' discusses how flora and fauna evolved through the centuries. The different features of each individual species would undergo a process of natural selection by which modification of attributes would naturally occur that would enable the species to adapt and propagate through time. Those modifications that failed to adapt would naturally become extinct.

In this post I discuss how database (DB) technology has evolved over the years. As new requirements arose database technology has had to adapt and newer paradigms have evolved. However, unlike species which became extinct the older versions still exist as they continue o address the earlier problems that remain today.

Here is a short & brief history of evolution of databases

Relational databases: Relational databases had their genesis when E.F Codd of IBM came up with a relational model of organizing data. In this model all data is organized as tables with several rows. In a relational model each row has several columns and one of the columns contains a unique value for each row called primary key. Relational databases have ruled the enterprise domain for more than 3 decades. An enterprise's data is organized as a set of related tables. Users can query the database using Structured Query Language or SQL.

I remember in the late 1980's when I started to work in the industry, programming jobs were much sought after by all of us engineering graduates. In those days database jobs were 'uncool' and system programming jobs dealing with writing assemblers, compilers were the really cool jobs. I was also susceptible to this prevailing opinion and stayed away from databases. As fate would have it I eventually moved into telecom and telecom protocol work in which I worked for more than 2 decades and have largely maintained my distance from DB.

However it recent times I did want to look brush up whatever little I knew of DB. Recently I was listening to the Coursera course “Introduction to Data Science' by Bill Howe. In one of the lectures the professor uttered something that really caught my fancy. He mentions that SQL is probably the closest to natural language. How true! Once the DB schema and tables have been set up, querying the DB for all sorts of data can be done in SQL which is close to natural language. For e.g.

SELECT a,b,c from TABLE S,T where condition X1 AND/OR condition X2

The power of DBs comes from the fact that all the data is organized as tables and enables one to retrieve any sort of data from it. Trying to accomplish this with any other high level programming language would take several hundreds of lines of code and we would have to write functions for each in individual query.

NoSQL databases: However the utility of relational databases decreases as we scale to hundreds of Gbs of data. In this age of the internet and the worldwide web data is easily of the order of several terabytes to a few petabytes. For e.g. Weather modelling, Social networks like FB,Twitter or LinkedIn all need to operate on millions of status updates or tweets per day. Traditional relational databases cannot handle such large sets of data. This is where the concept of NoSQL DB came into existence. NoSQL databases typically store data as key, value pairs. The singular advantage of NoSQL is that the database can scale horizontally or in other words the performance does not degrade with large increases in data size. In NoSQL databases data is hashed and uniformly distributed across commodity servers through a technique known as 'consistent hashing'. Also data in NoSQL databases is replicated across servers. This architecture of NoSQL databases is based on common, commodity servers which are expected to crash. However this would not affect the NoSQL DB to function correctly. The strength of NoSQL databases comes from the fact that servers can join or leave the NoSQL DB without affecting the functioning of the DB. Some of the more popular examples of NoSQL DB are CouchDB, MongoDB, Riak, Voldemort, Dynamo etc.Do take a look at my post "When NoSQL makes better sense that MySQL"

NewSQL: This variation of DB came into existence as there was a need for extremely fast performance for computing tasks like analytics etc. These DBs exist completely in memory and so the access is blazingly fast. The most famous of DBs of this paradigm is SAP's HANA.

Graph Databases: Graph databases are the recent entrants into database technology. This strain of databases came into existence to handle associative data more efficiently. In a graph database data is represented as a graph. Nodes in the graph can be entities and edges can be relationships. A search on a graph database will result in a traversal from a specified start node to a specified terminating node. “Friends' in Facebook, 'followers/following' in Twitter and 'connections' in LinkedIn all use Graph Database to map association and enable easy search. Graph Databases is what allows these databases to make recommendations like 'You may know'. E.g. of Graph Database Google's Graph DB, Neo4j

As we move ahead database technology will continue to evolve into newer architectures to handle

[polldaddy rating="7295683"]

Find me on Google+

Get your feet wet with IBM Bluemix

This post provides the initial steps to get started on IBM’s Bluemix (currently in beta). Bluemix is open-standard, cloud based Platform-as-a-Service (PaaS) from IBM. Bluemix allows one to quickly put together mobile, web, Big Data, IoT applications. Bluemix is an implementation of IBM’s Open Cloud Architecture, Cloud Foundry which enables developers to rapidly build, deploy, and manage their cloud applications. The developers can tap into a growing ecosystem of available services and runtime frameworks.

Bluemix uses the Softlayer infrastructure to host the user applications. Clients/developers interact with Bluemix either with HTTP or REST as shown below

Here are the steps to get going on Bluemix

First things first

I would suggest that you get all the registrations and installations right away.

Bluemix dashboard- Get started by creating an account on Bluemix. This will provide you access to the Bluemix’s dashboard from which you can quickly create applications (mobile, Web, IoT, BigData) etc

Devops: Register for an account with Devops. Devops allows you to easily develop, deploy and track your code online. Devops also allows you to collaborate with others by forking code from their Git repositories

Cf Interface : Install the Command line interface ‘cf” to Bluemix. The ‘cf’ command interface is built with Google’s Go programming language. With ‘cf ‘you can login to Bluemix, create an application, add services and manage your application. You can also do this from the Bluemix’es dashboard.

Install Git: There are multiple ways to develop code for Bluemix. Git command line happens to be one of them, So it makes sense to have this installed. You can install this from this link https://hub.jazz.net/tutorials/clients#installing_git

Install Node.js:The application that this post discusses is based on a Node.js based application so it will help to have it installed. Node.js is a platform that enables building of fast, scalable network applications and created by Ryan Dahl.

Kicking off Bluemix : A good first application to get moving on in Bluemix is the already available Sentiment Analysis of Twitter. This application uses the Node.js ‘sentiment’ module to perform some basic sentiment analysis.

The quickest and most painless way to get started on Bluemix is to ‘fork’ the code for Sentiment Analysis from Devops.

1) Login to your Devops account. Click the following Sentiments link from Devops, in which I have created a slight modification to the sentiment analysis application

2) Click the Edit Code button at the top. This will open the files and directories in this project (see picture below)

3) Next click the “Fork’ button on the panel on the left side. This will create a copy of the above code in your own repository (see picture below )

4) The Twitter sentiment analysis code is in app.js written in Node.js. You can make changes to the code as needed. I have made a few modifications to the code that I had forked. I added changes which adds a textual output of the Twitter sentiment

;

How to make code changes with Web IDE

5) To make code changes double click the app.js file. This will open up the code window. You can use the GUI based IDE to make the code changes and merge with the master branch, The steps are
a) Make the necessary changes and click the symbol shown

3. This will open a new window as shown below

4) Click the ‘Stage to change’ button.

5) This will move the changes to Staged. Click the ‘Commit’ button and enter the reason for the change and click the “Submit’

6) This will move the changes from ‘Staged’ to ‘Commits for master branch’

7) Now click ‘Push all’ and click ‘Ok’ in the Git Push popup window. This will merge the changes into the master branch.

8) Once this done click ‘Build & Deploy’ button

9) Your changes will transition from ‘Pending’ to ‘OK’. Now click the ‘Manage’ button. This will deploy the application with the latest changes on to Bluemix.

10) Do the following to populate the details for the parameters below  with a Twitter app that you create for your application

var tweeter = new twitter({
consumer_key:  API key

>,
consumer_secret: API secret>,
access_token_key:,
access_token_secret:
});

11) To do this log into http://dev.twitter.com

12) Click My applications where your picture is displayed and then click Create application.

13) Enter the details for Name,Description & Website (can be any valid website) and then click Create Twitter application.. This will create the Twitter application.

14) Click the API tab. Scroll down to the bottom and click “Create my access token”.

15) This will generate the Access token & Access token secret. Enter all the details (API Key, API secret, Access Token, Access Token secret into app.js and push to the master branch before deploying on Bluemix

Code changes with Git command line

11) Incidentally the changes to code can also be made through the Git command shell as follows

a) git clone https://hub.jazz.net/git/tvganesh/sentiments

b) Modify the code using any editor and save the changes

c) Go the directory containing the files and do

git add *

d) git commit -m “Cosmetic” app.js

e) git push

This will push the changes to the git repository in the master branch

8) Click the ‘Build & deploy’ in the top right corner. You should see this

9) Click the ‘Manage’ button which will push the application onto the BlueMix

10) To test this application click the link next to ‘Routes’ . Enter a phrase that you would like to search and hit ‘Go’

You should see the application checking Twitter periodically for the tweets.

Thats it! You have built your first Bluemix application.

The ability to integrate Node.js into your cloud application allows one to easily create powerful applications.

Hasta la vista! I’ll be back!

Disclaimer: This article represents the author’s viewpoint only and doesn’t necessarily represent IBM’s positions, strategies or opinions

The brave, new frontiers of computing

This article was published in Telecom Asia, 21 March 2014 – The brave new frontiers of computing

Von Neumann reference architecture and the sequential processing of Turing machines have been the basis for ‘classical’ computers for the last 6 decades. The juggernaut of technology has resulted in faster and denser processors being churned out inexorably by the semiconductor industry, substantiating Gordon Moore’s claim of transistors density in chips doubling every 18 months, now famously known as Moore’s law. These days we have processors with an excess of billion transistors. We are now reaching the physical limit of the number of transistors on a chip. There is now an imminent need to look at alternative paradigms to crack problems of the internet age, confronting human which cannot be solved by classical computing

In the last decade or so 3 new, radical and lateral paradigms have surfaced which hold tremendous promise. They are

i) Deep learning ii) Quantum computing and iii) Genetic programming.

These techniques hold enormous potential and may offer solutions to problems which would take classical computers anywhere between a few years to a few decades to solve.

Deep Learning:Deep Learning is a new area of Machine Learning research. The objective of deep learning is to bring Machine Learning closer to one of its original goals namely Artificial Intelligence. Deep Learning is based on multi-level neural networks called deep neural networks. Deep Learning works on large sets of unclassified data and is able to learn lower level patterns on which it builds higher level representations much the same way the human brain works.

Deep learning tries to mimic the human brain For example, the visual cortex shows a sequence of areas where signals flow from one level to the next. In the visual cortex the feature hierarchy represents input at a different level of abstraction, with more abstract features further up in the hierarchy, defined in terms of the lower-level ones. Deep Learning is based on the premise that humans organize ideas hierarchically and compose more abstract concepts from simpler ones.

Deep Learning algorithms generally requires powerful processors and works on enormous amounts of data to learn key features. The characteristic of Deep Learning algorithms is that the input is passed through several non-linearities before generating its output.

.

About 3 years ago, researcher’s at Google’s Brain ran a deep learning algorithm on 10 million still images extracted from Youtube, on 1000’s of extremely powerful processors called GPUs. Google’s Brain was able independently infer that these images consisted of a preponderance of cat’s videos. A seemingly trivial result, but of great significance as the algorithm inferred this result without any other input!

An interesting article in Nature, “The learning machines”, discusses how deep learning has proved useful for several scientific tasks including handwriting recognition, speech recognition, natural language processing, and in analyzing 3 dimensional images of brain slices etc.

The importance of Deep Learning has not been lost on the Tech titans like Google, Facebook, Microsoft and IBM which have all taken steps to stay ahead in this race.

Deep Learning is in its infancy and is still esoteric knowledge. Deep Learning is truly a fascinating area of research and may be the harbinger of the real breakthrough in Artificial Intelligence has been looking for in decades.

Genetic Programming (GP) is another radical approach to computing. It had its origins in the early 1950’s and has been gaining traction in the last decade. Genetic programming (GP) is a branch of AI, based on Darwinian evolutionary principle of ‘natural selection’ and ‘survival of the fittest’. Essentially GP is a set of instructions and a fitness function to measure how well a computer program has performed a task. It is a specialization of genetic algorithms (GA) where each individual is a computer program.

Genetic Programming is a machine learning technique in which a population of computer programs are optimized according to ‘fitness criteria’ determined by a program’s ability to perform a given computational task. Fit programs survive and are moved along the evolutionary process. Fitness usually denotes the optimum value for a given objective function. In other words the fitness represents the ‘quality’ of a given solution over others. Individuals in a new population are created by the method of ‘reproduction’ and ‘cross over’.

In other words, the ‘most fit’ programs are crossbred and also possibly randomly mutated, creating a new generation of child programs. The unfit programs are discarded out and the best are bred again.

Once set up, the genetic program runs and evolves by itself and needs no further human input. Genetic Programming was pioneered by Stanford’s John Koza who was able to invent an antenna for NASA, identify proteins and invent electrical controllers.

The eerie part of GP is that the code is inscrutable. The program evolves and mutates into variations that cannot be easily reproduced. Clearly this is fodder for science fiction-like scenarios of self-aware, paranoid & psychopathic programs. Here is an interesting article that discusses this- This is What Happens When You Teach Machines the Power of Natural Selection

Quantum computing

Computers of today from hardy mainframes to smartphones operate on binary logic. The entire edifice of today’s computing is based on the binary states of the semiconductor which can be either in the state of ‘0’ or ‘1’. All computation can be reduced to arithmetic and logical operation on binary digits or more simply, binary arithmetic. Quantum computers deviate significantly from the binary arithmetic of classical computers. The unit in the quantum computer is the ‘qubit’ which can be in state ‘0’, ‘1’ and both the state ‘0’ and ‘1’ through the principle of superposition.

To understand the power of quantum computing here is an excerpt from ArsTechnica “A tale of two qubits: How quantum computers work”

“Bits, either classical or quantum, are the simplest possible units of information…. Measuring a bit, either classical or quantum, will result in one of two possible outcomes. At first glance, this makes it sound like there is no difference between bits and qubits. In fact, the difference is not in the possible answers, but in the possible questions. For normal bits, only a single measurement is permitted, meaning that only a single question can be asked: Is this bit a zero or a one? In contrast, a qubit is a system which can be asked many, many different questions, but to each question, only one of two answers can be given”

The article further goes on to state that “Classical computer memories are constrained to exist at any given time as a simple list of zeros and ones. In contrast, in a single quantum memory many such combinations can all exist simultaneously. During a quantum algorithm, this symphony of possibilities is split and merged, eventually coalescing around a single solution. “

Having more than 1 qubit results in additional property called ‘quantum entanglement’. A pair of qubits cannot be described by the states of the individual qubits alone. Those states which exhibit extra correlations are described as ‘entangled’ states. Hence in the case of 2 qubits ‘the whole is greater than the sum of its parts”. Entanglement and superposition are the cornerstones which gives quantum computing its power. Here is a short and interesting animation of quantum computing

With classical computing techniques searching an unsorted phonebook of 10,000 entries, would require us to look up at least 5000 entries, while a quantum search algorithm only needs to guess 100 times. In other words it would take a quantum computer only 5000 guesses to search through a phonebook with 25 million names. That is the power of quantum computers!

Applications of quantum computers range from weather modeling, cryptography, solving problems that have been considered ‘intractable’ with classical computing methods. NASA is planning to use quantum computers in its search for exoplanets.

Deep Learning, Genetic Programming and Quantum Computing represent paradigmatic, lateral shifts in computing. They herald a new era in computing and will enable us to crack extremely complex problems in this Age of the Internet.

Classical computing will continue to play a role in a daily lives but for real world problems of the next decade & beyond it will be these 3 computing approaches that will hold the key to our future!

Rate This

Pregelian philosophy – Thinking Web Scale – Part 2

“If you squint the right way, you will notice there are graphs are everywhere”. This is a line from a Research blog at Google “Large scale graph computing at Google”.  Transportation problems, disease outbreaks, computer networks and social networks all use graph in one way or another. Social networks of today, with friends of  Facebook, followers in Twitter and connections in LinkedIn are all clearly graphs. The billions of pages in the World Wide Web with incoming and outgoing links is a massive directed graph.

Pregel is Google’s computing model for graph processing. Google came up with this programming model to compute Page Ranks of individual web sites. Pregel is a powerful framework for processing of directed graphs. A directed graph has vertices and edges. Edges are directed towards or away from the vertices. Pregel is a highly scalable model and is well suited for Web Scale problems. It is capable of processing directed graphs with billions of vertices and trillion of edges.

The Map Reduce paradigm with its message passing mechanism is not particularly well suited for this purpose. Map Reduce is capable of processing several documents, images, or matrices in parallel. But handling directed graphs with Map-reduce the combiners/reducers have to wait for the mappers to finish their tasks.  In Pregel programs are executed as a sequence of iterations in which each vertex receives messages sent to it in the previous iteration, execute code, and send messages to other vertices. Each vertex can  modify its state and the topology of the graph

Here is a the model of the Pregel.

This picture is taken from the lecture in Web Intelligence and Big Data course by Gautam Shroff on Coursera

Pregel works on a sequence of iterations known as supersteps. In each superstep, S, each vertex will receive messages sent to it in the previous superstep S-1, executes a user-defined function specified for the vertex and sends messages to other vertices which they will receive in superstep S+1. The supersteps at all vertices are conceptually supposed to occur in parallel.  At each superstep the vertex can alter its state and the state of the outgoing edges.  The synchronicity of the model is what makes the model semantically manageable.

Pregel is realized on hundreds of commodty serves. The input to the Pregel model is a directed graph. During initialization the vertices are partitioned and each server receives a set of vertices. Each vertex is associated with a modifiable user defined value.

In each superstep each node computes the user defined function in parallel using the message sent to it in the previous superstep.  A vertex can modify its state, the outgoing edges or the topology of the graph.

Pregel has been used for a variety of different problems ranging from determining Page Rank, Shortest path etc. Vertices are first class citizens in Pregel.  Algorithms terminate by a process of voting to halt. When all vertices vote to halt then the computation in Pregel is assumed to have completed. The algorithm as a whole terminates when all the nodes have voted to halt and there are no messages in transit.

A simple example of how Pregel determines the maximum value is illustrated in the original Google research paper Pregel: A System for Large-Scale Graph Processing.

The pseudo code for this can be written as

compute(){

i_val := val
while (m) {
if (m > val) {
val = m;
}
else if (i_val == val) {
vote_to_halt
}
else {
for each neighbor v
send_message(v, val)
}
}

In the above diagram the 4 vertices are initialized with the values shown. In superstep 1,

vertices 3 & 6 exchange their values. While 3 updates its value to 6 at its vertex, vertex 6 drops it and vote to halt. Similarly vertex 1 will update its value to 6 while vertex 2 which receives the value 1 will  vote to halt. In superstep 2vertex 2 will receive the value 6 from the vertex to its right, will be woken up and will update its value. In superstep 3 no messages are passed and all nodes would have now voted

Another interesting application is the evaluation of Page Rank. Page Rank essentially determines the probability of hitting a Page if a surfer clicked links on a Web page at random.

Page Rank is evaluated iteratively as follows (source wkipedia.org)

This can be done iteratively through Pregel as below

virtual void Compute(MessageIterator* msgs) {
if (superstep() >= 1) {

for (; !msgs->Done(); msgs->Next()) {
sum += msgs->Value();
*MutableValue() = 0.15 / NumVertices() + 0.85 * sum; – – > (A)
}
if (superstep() < 30) {
const int64 n = GetOutEdgeIterator().size();
SendMessageToAllNeighbors(GetValue() / n); – – > (B)
} else {
VoteToHalt();
}
}
}

The Pregel computation is initialized such that in superstep 0, the value of each vertex

is 1 / NumVertices() .  In each of the first 30 supersteps, each vertex sends along each outgoing edge its tentative PageRank divided by the number of outgoing edges (see step B above).

Starting from superstep 1, each vertex sums up the values arriving on messages into sum and sets its own tentative PageRank to 0.15/NumVertices() + 0.85 * sum (see step A)  After reaching superstep 30, no further messages are sent and each vertex votes to halt.

Clearly the computation of PageRank of the pages indexed by Google in the World Wide Web consisting of billions of pages can be computed fairly efficiently by Pregel.

Pregel also includes ‘combiners’ that perform functions like SUM, MIN,MAX and AVERAGE to save computational steps.

Pregel also includes checkpointing where vertices save their states to revert to a previous state in case of failure.

The synchronous methodology of Pregel helps in avoiding issues of deadlocks and races which are prevalent in asynchronous communicating programs.

Pregel is a powerful programming model which will find applications in many Web Scale applications in the future.