Example Knowbot Program Applications

[Contents] [Prev] [Next]

In addition to the full-fledged demonstration applications provided with the Knowbot environment, the directory examples contains a number of small programs that demonstrate possible applications of Knowbot programs. Each of these examples is described briefly here. The command lines presented below to run the demonstrations assume that $KOSROOT is the current directory.


To invoke from $KOSROOT directory:

submit examples/nomad.py -- -s 3 -l 7
The nomad KP is a simple demonstration of migration. The nomad will migrate from service station to service station, printing its location as it moves. At each location, it sleeps for a user-specified amount of time before moving on. The code is short and demonstrates several useful techniques: the KP's command line arguments, use of the namespace to find service stations, and migration itself.


To invoke from the $KOSROOT directory:

submit -s unsorted:examples/sort-medium.m examples/mergesort.py -- 3

Mergesort is a standard sorting algorithm that is often used to introduce the divide-and-conquer strategy in introducty algorithms courses. The mergesort example creates many KP clones and divides its work among them.

The mergesort algorithm sorts a list of n numbers as follows. First, it divides the list into sublists of n/2 elements, and recursively invokes mergesort on each of the sublists. After the sublists are sorted, it merges them together in sorted order. The real work is performed in the merge phase, beginning with the base case of the recursion where each sublist has 1 element.

In the mergesort example, each recursive invocation of the mergesort algorithm creates two new KP clones that sort each of the sublists. When they have completed, they return the sorted lists to the KP that created them; the parent KP performs the merge. Each of the clones runs at a different service station than either its parent or its sibling.

To avoid creating tens or hundreds of clones, the KP scans the namespace to determine how many KSSs are running and determines the total number of clones it can create, based on user-defined limit on the number of KPs per KSS (default is 2 KPs/KSS).

This example provides some useful insight on how to structure parallel programs that might be written using Knowbot programs. The application is constructed in a continuation-passing style. Each KP starts with a specific task to perform (sort the list of unsorted numbers) and an interface to call on to deliver the results -- the continuation. (The application itself is relatively uninteresting; the overhead of sending KPs and waiting for them to return outweighs the limited parallelism exposed in the program and there are easier ways to sort numbers).


To invoke from $KOSROOT directory:

submit examples/ping.py

This KP measures the distance between pairs of service stations using the Network plugin. At each service station running the plugin, it uses the ping service to measure the network latency to each of the other service stations. The KP demonstrates a general purpose way to look for connectors. It uses the kos.list_services() method to look for all the connectors of a particular type and then picks an arbitrary match.

Caveat: The Network plugin requires root access to run. If the Network plugin is not found running anywhere, the KP will raise an exception after having migrated to every possible KSS.

buyer.py and seller.py

To invoke from $KOSROOT directory:

submit examples/seller.py &
submit examples/buyer.py

Agents are often touted as a technology that will be useful for electronic commerce. We have some crude demonstrates of programs that use the Seller1 interface to set and ask about prices. The automated acquistion of negotiated resources extends this idea.

The buyer KP can be run more than once (and the seller KP will up its price each time). After running the buyer, the seller must be killed, e.g., by sending an interrupt signal to its submit process or by using the killkp utility.


Warning: This code is provided only to look at. DON'T RUN THIS EXAMPLE CODE. IT MESSES WITH THE KOE NAMESPACE.

The current implementation of the Knowbot system has very little security. The scramble KP demonstrates one kind of attack that can be made -- changing namespace bindings. The demonstration is intended to make you aware of the holes available for mischievous and malicious KPs to exploit. (We don't mean to suggest that the system is fundamentally insecure or that we don't care about security. Future versions of the system will be more secure.)

The KP changes all of the bindings in the "/kos" context of the namespace. After it runs, the names in "/kos" will be bound to the wrong service station. A lookup of "/kos/foo" will return the namespace of a different service station (say bar). The service station itself will be unaware of the change, and KPs can continue to use the namespace. They'll just wind up at a different service station than they expected.

[Contents] [Prev] [Next]
Copyright © 1998 by the Corporation for National Research Initiatives.