Go up to Top Go forward to 2 Using the Toolkit

1 Introduction

This reports describes the DAJ toolkit for designing, implementing, testing, simulating, and visualizing distributed algorithms in Java [4]. DAJ consists of a Java class library with a deliberately simple programming interface that allows to develop distributed algorithms in a message passing model. The resulting programs may be executed in standalone mode by a Java interpreter or embedded as applets into HTML pages and executed by available Web browsers.

Our motivation for this work stems from some uneasiness with how to teach distributed algorithms and programming: there are various excellent textbooks on this topic [6][1], but they describe distributed algorithms in an abstract notation rather far away from real programs. Furthermore, there is a lack of an easy to use and universally accessible platform for implementing the algorithms taught in class and investigating their dynamical behavior. Distributed message passing libraries like PVM [3] or systems based on the MPI standard [2] are too "heavy-weight" for use in education; they force to deal with a number of low-level technical details, and they do not allow the easy observation of the "internals" of the execution.

We therefore have designed and implement the DAJ toolkit that provides an easy way of programming distributed algorithms and visualizing their dynamic behavior based on a programming model that is intuitive but still close to "real" systems. DAJ has been implemented using Sun's Java Development Kit [5]. Despite of a few problems related to Java's Abstract Window Toolkit (AWT), the resulting programs should run in any Java environment and be embeddable as applets into HTML pages; this gives the possibility to develop documents that integrate text and executable code in a single framework.

An application developed with DAJ may run in one of three modes:

• standalone, without visualization,
• standalone, with visualization,
• as an applet embedded in a Web page.

The programming model has been deliberately kept simple with minimum conceptual overhead:

• The execution model consists of a network of nodes that are partially linked by channels and that operate asynchronously and independently of each other.
• The basic communication mechanism are point-to-point messages between those nodes that are linked by channels.
• Furthermore, a node may send messages via channel sets and receive (non-deterministically) messages from channel sets.
• A timeout value may be specified to limit the time that a node is blocked listening on an empty channel (or channel set).
• Each node has a local time that is implicitly advanced by each communication operation and that may be accessed by the programmer.

The visualization is based on the following elements:

• a screen of user-defined size displays the network as laid out by the user;
• the states of nodes and channels are indicated by colors as well as by messages in a foot line;
• the current local time of each node is displayed;
• the internal states of nodes and channels (i.e., the messages it contains) are exhibited by pop-up windows as defined by the programmer;
• network execution may be slowed down, interrupted, performed step by step, and restarted.

Program execution may be customized by

• user-defined node schedulers that determine the next ready node for execution, and by
• user-defined message selectors that determine the next message to be delivered from a channel,

Furthermore, the programmer may state assertions about the global state of the network (nodes and channels), which gives the possibility to check the validity of invariance conditions which may be formally proved in class.

The structure of this report is as follows:

Using the Toolkit

is a tutorial on the use of the toolkit by a simple example.

Installing the Toolkit

describes the installation of DAJ and related issues.

Building Applications

is a reference manual on the construction of applications in DAJ by composing nodes to networks.

Programming Nodes

is a reference manual on the writing of node programs in DAJ running on individual network nodes.

Proving Assertions

sketches how to proof assertions about programs designed and implemented in DAJ.

A Distributed Algorithm

contains an example of a non-trivial distributed algorithm designed and implemented in DAJ.

The DAJ toolkit is freely available at the URL

http://www.risc.uni-linz.ac.at/software/daj

Wolfgang.Schreiner@risc.uni-linz.ac.at