Introduction

Distributed computing—in particular, techniques that hinge upon borrowing or renting spare CPU cycles from PCs that would otherwise be idle—is a well-established approach to solving computationally complex problems. Projects such as SETI@home (analyzing radio telescope data looking for potential extraterrestrial broadcasts), Folding@home (analyzing how proteins fold themselves), and Prime95 (searching for very large Mersenne primes) are just three of the better-known distributed computing projects currently underway. There are literally hundreds, and some of them are massively popular. Sony has even integrated a specially dimensioned Folding@home client into the mainstream firmware for the PLAYSTATION®3 game console.

Making use of free CPU cycles on idle computers is all very well, but a few difficulties with traditional approaches to this technique include:

• If you release the source code for your application, you've just disclosed your algorithm to the general public, which might not be desirable. Since any required encryption keys and cryptosystems have to be in the source code as well, you've also just opened up your source data stream to the world. Even worse, people can use hacked versions of the client software to inject bogus results into your calculations.
• On the other hand, if you don't release your source code, it can be hard for people to trust that your application is wholly benign. After all, a properly functioning distributed computing client will frequently be transferring data to and from its parent server; who's to say that it is not logging keystrokes and gathering passwords, or sending interesting chunks of your documents to someone?
• Not all analytical tasks can easily be "factored" (divided into convenient bite-sized chunks that don't depend on each other and can hence be processed independently).
• There is a single point of failure—you—for collecting results and managing the workload. Anyone who wants to attack your research effort can do so by merely executing a denial-of-service attack on the home base server whose address is hardcoded into your client software.

The basic inspiration for this article stems in part from a cryptanalytic technique referred to as the "Chinese Lottery Attack." This is a hypothetical method for finding encryption keys by employing consumer appliances as distributed computing nodes. The premise is simple: A government would first develop an inexpensive codebreaking chip (this attack was proposed in the days when 56-bit DES was considered reasonably secure encryption) designed to run a brute-force attack over a small chunk of keyspace. The government would then introduce legislation requiring all radios and TV sets sold domestically to be fitted with this chip. (This is not at all far-fetched, by the way. Recall that the United States successfully legislated the V-Chip into television sets starting in the year 2000.) Over the airwaves, each appliance would be assigned a small piece of the keyspace to analyze. If the device believed it had found a potential solution, it would light up an LED and the owner would call a toll-free number to claim a cash prize; the government would then retrieve the "winning" device and read out the key from its memory.

Back to top

Problems with distributed computing systems

A problem with the Chinese Lottery, as with the other distributed computing systems described above, is that everyone who has the technology to reverse-engineer your crypto chip and then listens to your broadcast knows exactly what you're trying to break. This has bigger implications than you might appreciate, because it means your opponents get a strong clue as to which of their communications channels are being intercepted.

Worse, they can make a very accurate estimate of when you're going to break any particular key, because the computation power of each node is known, and anyone who is listening to the broadcast channel and who also knows what key is being attacked will know exactly when the "winning" packet is sent out. One can also postulate several types of attack against such a system. For instance, an attacker could build a small transmitter that would override the broadcast signal within a small radius and hand out bogus "winning" packets to swamp the prize-claim hotline with fake "wins."

There are mechanisms for dealing with all of these comments, of course, but the fact remains that it would be interesting and useful to have a distributed computing mechanism with at least the following traits:

• Redundant design with no single point of failure
• Resistance to information leakage through traffic analysis
• An easily analyzed computational engine which can be freely disclosed without compromising the task at hand, and which can readily be proved to be harmless to the end-user
• Opacity of purpose where, even if given the algorithm and data payload for any given node, it is not possible for an observer to deduce what the system as a whole is doing

Back to top

The Internet: A redundant information network

Probably the world's best example of a redundant information network is, of course, the Internet. If you use standard Internet protocols to link your nodes, you can ride a huge raft of existing technology with no extra engineering cost. For this reason, you should choose HTTP as your transport protocol. This automatically gives you all the Internet's normal routing redundancy, plus the ability to use automated load-balancing and failover mechanisms which are ubiquitous on today's Internet. A couple of other bonus side effects will become apparent after we discuss the algorithm itself, but for the moment just consider the issue of redundancy and then move on to the other goals.

How do you achieve resistance to traffic analysis? Well, first let me define what it is. Traffic analysis attacks attempt to glean information about a message or protocol by observing which parties are talking to whom, and in some cases how much data is being transferred. For instance, suppose you are trying to log into a system A. You enter a username and password pair, and watch the traffic. Observe that system A sends a small data packet to system B, and waits for a response packet before granting or denying the login request. You might infer from this that system B holds the actual authentication database, and system A is merely a front-end. This is perhaps a trivial example, but analysis of the type I have just described can be the thin end of the wedge in penetrating a cryptosystem.

You can harden your system against attacks of this type using two methods:

1. Geographically scattered nodes in a mesh topology. It will not be feasible for an attacker to monitor all the links between the nodes, because no single entity (government or otherwise) will have access to all of the relevant backbone segments.
2. Outside entities cannot know where the input and output boundaries of your system are. All the nodes are constantly transferring information to one another. Only a person with a "map" of the network, as currently configured, will know which node(s) are currently providing meaningful outputs and what those outputs represent. To everybody else, each node is merely pouring out a stream of random numbers.

Back to top

Neural networks

This brings us nicely to the meat of the program, namely the processing algorithm itself. The latter two of my design goals above can be fulfilled neatly by a neural network (assuming that the original computational problem can be solved with such a network, of course). Research into neural networks has faded into and out of vogue over the past few decades, but this type of algorithm is fairly widely used in such diverse applications as optical character recognition, credit scoring, weather prediction, and even controlling certain home white goods.

At its most basic, any neural network consists of some number of interconnected nodes. Each node has n inputs, i₁ ... i_n, each of which has a corresponding weighting coefficient, w₁ ... w_n, and one output O. Note that the variable names I've assigned here are my own, though the terminology is standardized. The output of each node is the result of running the node's sigma (summing) function over all the inputs, which in the very simplest case can be represented as:

It is common, though certainly not a scientific requirement as such, to define node inputs as varying in the range -1 ≤ i_n ≤ 1 when the input represents a digital (yes/no) value. The weights can be any real number.

Neural networks have several different topologies, but the simplest is known as a feedforward network. The actual neural part of such a network normally consists of three layers: input, hidden, and output (shown in yellow, green, and purple, respectively in Figure 2 below). A complete system, however, includes a couple of other pieces, which are shown here:

To understand what these pieces mean, consider an optical character recognition system that scans glyphs printed on paper and converts them into three-digit decimal numbers. This is a typical sort of application where neural networks might be employed. (Resources contains a link to a fun hands-on demonstration of this type of network.)

The input to the system is a scanned image of the original paper. Next, the system might divide the image into blocks of 2 x 3 grayscale pixels, each block containing a single character; this is the feature extraction step shown above. 2 x 3 probably wouldn't be enough resolution for this application, but we're just discussing a hypothetical application here, and Figure 1 would be too hard to understand if I showed more nodes.

Each pixel's grayscale value is then fed to each of six input layer nodes. The output of each input layer node is fed to each of six hidden-layer nodes, which in turn feed three output nodes. I'll define the outputs such that I expect each output node to give me a number in the range 0 through 9. In other words, I can simply take the integer portion of the output and use that as the appropriate digit of the expected output code.

You should note that there is no particular magic about the number of nodes I've placed into each layer; in fact, each layer might even consist of further sub-layers of nodes. Generally speaking, the greater the number of nodes, the more finely tunable the network becomes. At the extreme, you could use combinations of weights and interconnections to build the equivalent of Boolean gates that would give you a "simple" combinatorial system, but this isn't an efficient way of exploiting the strengths of neural network programming; this type of algorithm is better suited to deriving probabilistic answers from fuzzy inputs.

So far I've shown how the interconnects are built (it's a general-purpose, open-ended wiring plan; hopefully, you've observed that any of these pathways can be effectively removed if the appropriate input weight in the destination node is zeroed), how the sigma function runs, and how you can define the characteristics of both the input and output using some method that has meaning to you. The one important piece we are missing is an explanation of the weights. These are obtained by training the network with known input data (see Resources), and no real analysis will glean objective meaning from these numbers; they are truly magic. Weights have meaning only in the context of the specific network where they were learned.

Herein lies the charm of the neural network, and the feature that makes it uniquely suitable for our list of design goals. By themselves, the weights are utterly opaque magic numbers—nothing can be inferred from them. (This is sometimes cause for complaint, in fact—you cannot extract a simple algorithm by looking at a neural network. But it's perfect for us, because it means that nobody can work out what the system is doing by looking at one node, or even a group of nodes). Likewise, by itself the routing information that describes how nodes are interconnected has very little meaning without the corresponding weights.

It only remains to build a demonstration system. The sample code for this article implements a simple node of the type I have described. Although it's written in C, you could very easily write it in practically any language: perl, Pascal, Java, or even as a bash shell script. It operates as follows:

Each node is assigned a unique identifying serial number. Any number of nodes can run on a single host. Each node has n inputs i1 through in, each of which has an associated weight w1 through wn and the serial number of the node that generates that input, s1 through sn. In the example code, the weights are randomly assigned (representing an untrained network). The node also assumes that all other nodes are running on localhost (127.0.0.1), for simplicity in testing. In a real environment, additional routing information would be required to associate specific serial numbers with different hosts.

The system as a whole has a quantized concept of time: Time begins at 1 and increments every time signals propagate from one layer to the next. A node will not generate an output for time n+1 until all its inputs for time n have been collected and summed.

Start the demonstration applet using the following command line:

neurnode a b c

where a is the serial number of this node, b is the serial number of the first input node, and c is the serial number of the last input node. For example, neurnode 100 200 299 starts a node with serial# 100, which takes as input 100 nodes, serial numbers 200 to 299. Note that the program expects to be run in the root directory of your Web server.

Once per second, each node attempts to gather its inputs. The input URLs are constructed from the serial number of the source node for that input and the current value for time. For example, if you have a node, serial number 20, whose inputs are nodes 5 through 10, and the current value of time is 3, the node will fetch the following URLs:

http://127.0.0.1/5-3.txt
http://127.0.0.1/6-3.txt
http://127.0.0.1/7-3.txt
http://127.0.0.1/8-3.txt
http://127.0.0.1/9-3.txt
http://127.0.0.1/10-3.txt


If all the inputs were fetched successfully, the program calculates its output signal and writes the result to the file "./20-3.txt"—ready for the next layer, if any, to fetch. Otherwise the program sleeps for a second and tries again. You can run a demo system with a single output, ten intermediate layer nodes, and ten inputs, using the following commands (remember to start in the home directory of your Web server):

neurnet 100 1 10 >/dev/null & neurnet 101 1 10 >/dev/null & neurnet 102 1 10 >/dev/null & neurnet 103 1 10 >/dev/null & neurnet 104 1 10 >/dev/null & neurnet 105 1 10 >/dev/null & neurnet 106 1 10 >/dev/null & neurnet 107 1 10 >/dev/null & neurnet 108 1 10 >/dev/null & neurnet 109 1 10 >/dev/null & neurnet 200 100 109

At the input end of the overall system, you simply need to create the relevant input files for the first layer of the network directly. The program expects to find a single floating-point number in ASCII format; any extraneous characters will be ignored. At the output end, you can read out the results using any Web browser.

You might be wondering why I implemented the transport mechanism using this slightly odd pull methodology. The reason is to obscure the results from outside observers. If the nodes used a push methodology, then it would be easy to deduce from the routing table which nodes are final outputs. With the pull methodology, individual nodes have no way of knowing if they are in the input, hidden, or output layer.

Also note that this push method can very easily be integrated with a steganography module to conceal neuron interactions inside other data. For example, you could have the output of each node embedded in an image file and stored on a Web server, ready to be fetched by the next hop in the network. If you wanted to be ultra cunning, you could have the output placed in a random place on the Internet, embedded in a page with a magic search keyword that wouldn't normally occur elsewhere. To retrieve it, you would use a regular Internet search engine to locate the container page. (Obviously, this would introduce very large delays in message delivery, but it's an interesting thought).

Conclusion

So there you have a working, if simplistic, standards-based distributed neural network with some intriguing properties. To make this into a fully functional distributed computing client, you would need to add an infrastructure to assign and route nodes, and set and update the weighting factors inside each node. Applications where this technique might be useful include systems where data is gathered over a wide area and processed to form some monetizable result.

Back to top

Download

Information about download methods

Resources

Learn

• The Folding@home project can be found at Stanford University, while SETI@home is hosted at Berkeley. See also Wikipedia's list of distributed computing projects.
  
  
• RFC3607 outlines the structure of a Chinese Lottery Attack; for further reading, see also "Applied Cryptography" (2nd edition) Bruce Schneier, ISBN 0-471-12845-7.
  
  
• Find an interesting, entry-level discussion of neural networks (along with a JavaScript implementation of a very simple network) in Bernard Willers & Sep Vrba's section of the ThinkQuest library.
  
  
• Neil Fraser has a very light introduction to network training —this article includes a Windows-based, self-learning character recognition program, with source code.
  
  
• Learn more about the next logical step in distributed networking at the developerWorks Grid zone.
  
  
• Get your hands on more helpful, technical articles from the Web development zone technical library.
  
  
• Subscribe to the developerWorks Web development newsletter.
  
  

Get products and technologies

• Download IBM product evaluation versions.
  
  

Discuss

• Get involved in the developerWorks community: blogs, forums, and so much more.
  
  

About the author

Comments (Undergoing maintenance)

Back to top

Trademarks  |  My developerWorks terms and conditions

Table of contents

• Introduction
• Problems with distributed computing systems
• The Internet: A redundant information network
• Neural networks
• Conclusion
• Download
• Resources
• About the author
• Comments

Local resources

• IBM Innovation Center - Austin, TX
• IBM Innovation Center - Chicago, IL
• IBM Innovation Center - Dallas, TX
• IBM Innovation Center - San Mateo, CA
• IBM Innovation Center - Waltham, MA
• Technical Briefings in North America

My developerWorks community

Dig deeper into Web development on developerWorks

Rate a product. Write a review.

Write a review for Rational products today!

Special offers