Building Scalable Tools with Lilith


Basic and advanced ways to use Lilith for Tool Building

Bookmarks:



Lilith-based tools are easy to develop since users are only responsible for writing the code for the tool functionality, with Lilith handling the details of the user code distribution and result collection.

Lilith's principle task is to span a tree of machines executing user-defined code. The tree structure is chosen to provide logarithmic scaling. Beginning from a single object, Lilith recursively links host objects on adjacent machines until the entire tree is occupied. The hosts propagate user code, called Lilim, down the tree. The Lilim perform user-designated functions on every machine. Finally, the hosts propagate the results of the user code back up the tree. The Lilim can do further processing on the results from lower nodes as they are passed back up the tree. Overall, the code undergoes a three phase process: distribution, execution, and result collection.

Three phase process for user code under Lilith: distribution, execution, and result collection. Lilith handles the details of the user code distribution and result collection as well as communication amongst nodes on the tree.


Tools can be created by the suitable development of user code which implements the direct action of the desired tool on a single node, while Lilith handles the details of user code distribution and instantiation, result collection, and communications.

A simple example is a distributed sort tool. This usage capatalizes on the fact that it is faster to sort a set of presorted sets than to sort an entire unsorted list from scratch. In this case the downward processing will consist of: the Lilim on each node getting from its parent a list of numbers to sort, subdividing that list into pieces for itself and its children to sort, and then sending the appropriate pieces down to its children. The Lilim on each node will then sort its own piece. Finally, the upward processing of the results consists of gathering the childrens' sorted lists, combining their results with its own via a merge sort, and then passing the combined sorted list up to its parent.

In this example, the data distribution, execution, and result collection occur in a simple sequential fashion. Communication patterns are also simple with data being sent down the entire tree and collected up the entire tree. Furthermore, should several lists require sorting, this could be handled by a simple looping of the above events, with different data, but the same functionalities involved. This simple type of behavior is representative of many potential tools and thus Lilith provides a special Lilim with a simple interface to handle this overall behavior. Details on this easy way to obtain basic functionality can be found in Lilly - an easy way to use Lilith. We anticipate that the Lilly functionality will be sufficient for many users needs. However, in the event that more complicated actions are required, such as more complicated communications sequences, users can write own Lilim, making more direct calls to the Lilith framework to suit their special case. These users should see Beyond Lilly. For comparison purposes, we will illustrate the distribute sort with both Lilly and the more direct Lilith interactions.