Fifth International World Wide Web ConferenceMay 6-10, 1996, Paris, France
Fifth International World Wide Web Conference
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.
Semantic Web Graph Layer
Figure 1: SWGL architecture
Description and Motivation
The Semantic Web Graph Layer (SWGL) is an interpretive layer which
filters the interaction between the reader and the content of the
Web. This is where the various graph models mentioned above are
implemented (see Figure 1). This section will describe the graph layer
in greater detail, with an eye toward architecture, its interface, and
its extensibility.Architectural View: Filter Stream
Freely combining graph semantics uses the fact that the SWGL is
implemented as a stream of filters which interpret extended HTML as
graph content. Filters can be composed, the exact order and number of
filters being the specification of a particular graph layer protocol
(see Figure 2). Protocol filter streams have been explored in other
collaborative tools such as XPEL [M93].
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.
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.
Multi-Client Models
Concurrent browsing, having multiple browsing paths active at the same
time, suggests a logical next step of synchronizing multiple readers
using multiple browsers. This addition of synchronization between
multiple, remote browsers is an important step in this research and
that protocol was a primary motivation for the construction of the graph
layer. Petri Nets
Petri nets are a model of computation used to describe parallel
processes. Petri nets are bipartite graphs with place nodes and
transition nodes connected by links. Links are constrained to connect
only either a place to a transition or a transition to a place.
Places can contain tokens, which are markers representing the state of the
computation. In a traditional monochromatic Petri net, when all of the
places pointing into a transition contain at least one token, the
transition is active. Computation in the Petri net proceeds by
firing an active transition, removing one token from each of the
incoming places and adding one token to each of the outgoing places
from the fired transition. Figure 3.a shows a simple Petri
net; the transition is active because the incoming places are all marked.
Figure 3: Petri net transitions
Sessions
Sharing running applications is a common but difficult problem in distributed
computing [H92]. Sharing can be done by sharing the
view of a single running program [MA-W95] or by
keeping two copies of a program synchronized on equivalent input streams
[DR94]. We use the second approach, keeping the
multiple browsers synchronized by pointing them at appropriate URLs in the
Web space.Scenarios
Given the above descriptions, we will now revisit the simple
two-player game example from the introduction. This illustration is
sufficient to show how the system works with CPNs. Our research
is aimed, however, at exploring how this system can be used in
classroom-based computer-aided instruction situations. The Trellis
[SF89] project has shown how CPNs can be used to
program hypertexts for use in moderated meetings, more complex
gameplaying, and other learning tasks. The graphs for those tasks,
however, are too complicated to be instructive about CPNs within the
scope of this paper.
Figure 4: CPN for two-player gameImplementation
Programming
The first MMM project's most basic requirement was that it be easy for
users to integrate into their systems. In order to display even the
standard Web graph differently, changes to the Web client were
unavoidable. However, it was possible to avoid altering the server by
keeping the additional multi-link information in the HTML pages. This
had the added benefit of keeping link control in the hands of the
author, the original goal of the project, rather than in server
functions. The great majority of active web browsing software was
downloaded from the Internet, so we believed that users might be
comfortable downloading our modified client.HTML Language Extensions
Multi-link: <MHMT [gr] [tx | dtx | tx dtx]> body </MHMT>
gr: GRAPH="text"
tx: TEXT="text"
dtx: DISPLAY_TEXT="text"
text: any plain text string
body: (text | iref | anchor)*
iref: <IREF HREF="url" [act]>
anchor: <A HREF="url" [act]> text </A>
act: ACTIVATE=text
url: Universal Resource Locator
Conclusion and Future Work
As in the previous paper, we end with a look to the future. Because this
project is unsupported research, we have no specific plans for future work;
we do have some new research directions, some of which are detailed below.
Current information about the MMM project is available at http://www.cs.unc.edu/~stotts/MMM/.Authoring Environment
The hardest part of using the extended graph models is writing the complex
link and node structures. In addition to choosing a suitable graph
protocol the author must manually insert the appropriate MHTML link
constructs in each page of the document. Automated authoring support is
necessary to make these extensions conveniently usable, especially for
making graphs that are interesting for more than a single protocol.More protocols
In addition to the editor, another next step for the research is
taking advantage of the general graph layer by developing further
graph protocols. Timed CPNs and And/Or graphs are obvious choices
though we hope to spend some time looking at novel combinations of
our various filter capabilities. We also expect to provide these graph
protocol layers to user text groups so we can study the real-world
implications of the additional semantic power of the various graph models.Conclusion
To conclude, we feel that the additional semantic power offered by
further graph models gives authors more precise control over how their
documents are browsed. The Semantic Web Graph Layer offers a
convenient abstraction for providing graph model controls, as well as
a convenient architecture for implementing such. Though we have not
as yet fully explored the potential of the SWGL, we feel that the
multi-client requirements of the Colored Petri Net protocol was an
adequate test of the architecture. As well, the CPN protocol provides
the semantic control needed for specific situations, such as moderated
meetings or group browsing sessions, that have often been solved in an
ad hoc and limited manner. Initial studies show that the
system is well-suited to the classroom environment for which is
intended--as well as to multi-player Web games.
Acknowledgements
We would like to thank members of the University of North Carolina at
Chapel Hill Computer Science Graduate Department, specifically those
enrolled in the Software Engineering course in the 1995-1996 year.
These students did the bulk of the programming work on the Semantic
Web Graph Layer and the CPN protocol, as well as often giving valuable
input into the design and research process. Though they are too many
to credit directly for the paper, each of them deserves that
distinction. Team members were Lars Bishop, Gentaro Hirota, Jayant
Kolhe, Jason Smith, Narendra Tulpule, and Jason Wilson.References