Richer graph models permit authors to "program" the browsing behavior they want readers to see by turning the hypertext into a hyperprogram with specific semantics. Multiple browsing streams can be started under the author's control and then kept in step through the synchronization mechanisms provided by the graph model. Our current work adds a Semantic Web Graph Layer (SWGL) which allows dynamic interpretation of link and node structures according to graph models.
As a motivating example of the utility of the SWGL, we have chosen to implement the graph model for Colored Petri Nets (CPNs). The previous MMM project [LC95] implemented a limited subset of the Petri net model to give Web authors the ability to control concurrency and synchronization in a single reader's browsing session. CPNs extend this protocol to give control of multiple readers in a like fashion.
This paper details the SWGL and its architecture, some sample protocol implementations, and the latest extensions to MHTML [LC95] that were necessary to support these enhancements.
Precise control of how documents are presented to the user is beyond the basic model of the Web. One can see the problem, and its ad hoc solutions, at many levels. The use of monolithic documents and linear linking to ensure a certain browsing path is used at the expense of clarity, and indeed, loss of the motivating concept of hypertext. Complex server workarounds are built to allow storage of state in a system with a stateless communication protocol, and recently we see plug-in technology to render pages in more complete description formats than HTML. Often only extensions to Web protocols permit authors greater control over readers' browsing options [LC95].
Richer graph models permit authors to "program" the browsing behavior they want readers to see by turning the hypertext into a hyperprogram with specific semantics. Multiple browsing streams can be started under the author's control (not unlike the Netscape "FRAME" extension) and then kept in step through the synchronization mechanisms provided by the graph model.
Our previous work with Multi-head Multi-tail Mosaic [LC95] extended the Web graph model to include the programming power and semantics of parallel finite automata (PFA). This current work extends the browsing streams which can be synchronized beyond those of a single user. Authors can now write documents which keep multiple users' browsing paths synchronized.
Coordinated multi-user browsing streams have obvious utility. A trivial example is a two-player, head-to-head game that requires synchronization between the browsing streams of two separate processes. This behavior can be specified with a simple multi-user graph model such as Colored Petri Nets (CPNs).
Rather than just increase the power of a single extended graph model, our current work also focuses on inserting a semantic graph layer in the browser. The layer provides an API for addition of new graph models, which allows the browser to dynamically reinterpret links and nodes within a new model. The author may suggest, and the reader may choose from, multiple graph models such as PFAs, monochromatic Petri nets, CPNs, And/Or graphs, the Dexter Hypermedia model [HS94], and so forth.
The remainder of this paper is laid out as follows:
Permitting authors to script a reader's interaction with a hypertext has been tried before in different ways [T88, Z88]. The current work is similar in approach to Trellis [SF89] where hypertexts are designed as Petri nets with specific browsing behaviors programmed into the network. The act of browsing is then the act of marking the net and firing activated transitions. Our graph layer generalizes this approach by offering authors a number of options for how their nodes and links are to be interpreted.
Our work offers a way to provide multi-head and multi-tail links. One recent non-standard Netscape extension to HTML, Frames [N96b], offers multi-tail capabilities. The functionality of frames is subsumed by our work; we have more complete synchronization between multiple browsing streams and can coordinate the browsing of multiple readers.
The SWGL interprets an extended version of HTML (see Language Extensions below), filtering the interaction between the reader and the Web content in the context of the current graph model. This means nodes and links can be dynamically interpreted as if they were part of a monochromatic Petri net, a parallel finite automata, or even part of the Web graph model. Setting the current graph model is usually handled by the document's author though these settings can be overridden with the SWGL user interface.
What we are calling graph layer protocols are descriptions of specific graph models combined with methods for properly rendering pages in that graph model for the reader. For example, the parallel finite automaton modeled in the original MMM project required different text colors to represent the difference between active and inactive transitions; a PFA protocol would combine that sort of information with a specification of PFA semantics.
This extension of the MMM architecture yields great flexibility for graph theory research. Significant work has already been invested in analyzing graph semantics, and a user-definable, dynamically-switchable interpretive layer offers a significant tool for such research. As well, the SWGL has a straightforward API which facilitates trial specification and implementation of experimental graph protocols. The original MMM project's PFA protocol was based on a specific driving problem in computer aided instruction, as is the CPN for this project, and we believe both graph protocols have proven particularly useful.
The SGWL allows us to combine features of existing semantics with others to investigate additional possible protocols. And in addition, the SWGL was implemented so that its use requires only a version of Netscape, a popular web browser publicly-available on a variety of computing platforms. It is hoped that this easy availability will allow the SGWL to be used as a tool to catalyze graph research projects that we have not envisioned.
As an example of the power of filter composition, consider that the difference between PFAs and Petri nets is that PFAs do not keep track of multiple markings of a given place; additional tokens are simply discarded. Given the specification of a PFA graph layer protocol, the Petri net protocol requires only the addition of a "token counting" filter to the filter stream implementing the PFA graph layer protocol.
We exploit the generally hierarchical nature of the relationship between graph semantics to allow rapid extension of available protocols. The above graphs, as well as CPNs, all share a basic digraph with active/inactive transitions and marking modes. Adding protocols for completely unrelated graph types would still require the addition of a great many filters, but that addition in turn gives a starting point to achieve all protocols which are closely related in the graph hierarchy. In general, the addition of each filter will nearly double the number of available protocols.
Currently, the API's function categories include groups for tasks such as HTTP communications, MHTML parsing, window management, and protocol interpretation (e.g. token counting). The details of specific functions are not within the scope of this paper, but the documentation is included in the public release of the SWGL package.
This model of computation can be applied to browsing a hypertext [SF89] document. In Web terms: a page is a place, a page is made visible in our browser when it has at least one token, and our specialized Multi-HTML constructs are transitions, complete with the list of links into and out of the transition. The previous work used a slight simplification of this interpretation, parallel finite automata, that are like Petri nets except that they do not track any more than a single token in a place.
An interesting extension to monochromatic Petri nets is the Colored Petri Net (CPN) [P81]. Here there are different classifications of tokens, known as colors, and transitions can have more complicated formulae for activation such as "A token in each of the two input places, but they must not be of the same color." The transition in Figure 3.a would not be active if this rule were added, but the transition in Figure 3.b can be fired because the colors of the tokens are different. In Figure 3.c the rule is modified to make the color requirements constant, so the transition is no longer active. Our enhanced browser interprets each person in a session (see Sessions below) to use different-colored tokens. Hence the author can specify the desired browsing semantics for a group by describing the transition activation rules.
A standard problem in synchronous collaboration is "finding" others to collaborate with. Our approach is to group users into collaborative sessions; sessions are maintained by a centralized session manager. A session, then, is a group of running browsers which can communicate among themselves and be synchronized. The session manager handles the allocation of token colors to the various browsers, listing members of a session, and changes to that list during the session. It is implemented as a centralized database server through which the group members communicate distributed events. The manager linearly orders those events to prevent users from taking conflicting actions. Each action that could change the state of the collaboration is checked and ordered, and only if the server deems it acceptable is it then broadcast and applied. Though this causes a minor delay between the time a user clicks on a link and the time the display is updated, we rely on the fact that users of the Web are quite accustomed to such delays and that communication delay may in fact be subsumed by page fetch time.
The CPN for a simple game is shown in Figure 4. Places are shown as circles, transitions as rectangles, and links leading from a place to a transition are marked with the rules for activating that transition. The variables on a transition can be matched with any color (or color constants can be added to the expressions to bind one of the colors to a particular color).
When two potential opponents in the same session enter the Find Opponent page, the Start Game transition becomes active and is displayed as a click-able hyperlink in both browsers. Either opponent clicking it will advance both to the Take Turn page; note that this does mean that the behavior of one user affects the state of another. As each player commits his move, she clicks on the Finish Turn transition and advances to the Awaiting Next Turn page. When both are finished, the Start Next Turn transition becomes active and they can advance. Note that an extension to CPN called timed CPNs (similar to the Netscape client-pull constructs [N96a]) which would fire the activated Start Next Turn transition automatically. The Trellis project contained timing on arcs [SF90, SF91], but we have not yet implemented timed CPNs for the MMM project.
Since the time of previous implementation, advancements in browsers have allowed us to do our window management using standard HTML techniques rather than client modifications. The Frames syntax developed by Netscape allows our specially-prepared pages to have controls for history-list traversal and for each content node to be displayed in a distinct "window". The SWGL has been developed as a proxy server rather than a client modification; with caching disabled, all HTTP requests from the client must go through the proxy, and there the SWGL returns the proper pageset to the browser. The SWGL proxy server was designed to be compatible with Netscape 2.0 beta (and now 2.0), and it is currently compiled to run on various popular Unix platforms. Versions for other platforms, and specifically Microsoft Windows 95, are planned.
We knew that the multi-client protocols would require session management. With the requirement that there be no server modifications, our options were reduced to finding a broadcast communications network across the clients. We experimented with a star communications topology, but eventually found that having the first client start a special server was more feasible. Though this creates a communications bottleneck, we envision our collaborative protocols to be used by either very small groups of two to four researchers or classroom environments in which we would expect the instructor to have a higher-performance workstation on the same local network as the students' machines.
Multi-link: <MHMT [gr] [tx | dtx | tx dtx]> body </MHMT>
text: any plain text string
body: (text | iref | anchor)*
iref: <IREF HREF="url" [act]>
anchor: <A HREF="url" [act]> text </A>
url: Universal Resource Locator
The previous implementation of MMM introduced MHTML[LC95], or Multi-HTML. MHTML adds the <MHMT> (Multi-Head, Multi-Tail) environment tag to standard HTML [H95]. The <MHMT> tag encodes a transition in the contents of an HTML page; it also includes information on how to display the transition. There are attributes for the text to render and what to display on the status line when the pointer passes over the transition. There are also lists of the transition's incoming and outgoing links.
MHTML is designed to permit rational behavior in browsers that do not have a SWGL addition. This takes advantage of the general behavior that browsers ignore tags they fail to recognize. A browser without a SWGL will ignore the <MHMT> and <IREF> tags, rendering only the <A HREF="..."> tags; the MHTML transition is replaced with a set of hyperlinks corresponding to the outgoing links from the transition.
Two major additions to MHTML v2.0 are the GRAPH attribute on the <MHMT> tag and the ACTIVATE attribute on the <IREF> tag. The GRAPH attribute specifies what graph model intended the current multi-link to be browsed with. This can be overridden by the reader; we currently depend on social protocols to "enforce" the intended browsing semantics.
The ACTIVATE attribute specifies the activation conditions for a link leading into a transition (that is the relationship between colors of tokens which must be on that page and the color of the current browser). A simple set of boolean connectives is supported with color constants, variables which are any color but the current browser's color, and the current browser's color ("current"). The default value for ACTIVATE is "current", making a default CPN behave as a monochromatic Petri net.
Authoring support should provide an overview of the graph structure which can be edited to add nodes, links, and transitions as well as an editable view of the contents of the various nodes. The editor should produce navigable MHTML files with appropriately structured links. The Trellis [SF89] project has a Petri net editor, xTed, which has already implemented many of the visual aspects of such a graph editor. We hope to leverage xTed by adding MHTML export filters so we can have a graph editor as soon as possible.