Metro is a project to build an exploratory but practical platform for wide-scale, collaborative, mobile applications accessible using only a web browser. The platform tackles some significant problems affecting current models by employing previous research in collaboration and distributed systems.

Computational tasks are increasingly split across many devices and involve multiple non-coordinated participants. Current techniques for architecting applications are struggling with this: they derive from a model oriented to a single user using a single computer for a self-contained task.

Recently, developers have turned to web-based applications - applications delivered using dynamic HTML - to solve some problems with this model, namely:

• Global accessibility: web-applications can theoretically be accessed from anywhere with a network connection.
• Instant roll-out: applications need only be updated on the central server for that update to be rolled-out to application consumers.

However, lots of problems remain. The deficiencies of HTML as an application environment is being addressed with rich internet application frameworks such as Flex, Laszlo and Silverlight as well as the W3C's own efforts. Deeper systems problems though, include:

• Mobility and multi-synchrony: tasks will involve a concurrent mixture of devices and people, which we will collectively refer to as participants, and any participant may join and leave a computational task at any time. This implies a concurrency model that cannot depend on complete knowledge of the participant group and that allows participants to transition seamlessly from on-line to off-line: that is, a multi-synchronous concurrency model rather than the floor-control model commonly encountered today.
• Continuity: tasks are entities that exist independently of the participants engaged in them at a specific time. Therefore, for a participant to situate herself within the task, a rich representation of the task's history must be present: the participant must be able to view not only the current state but also what lead to the current state. Moreover, it may be impossible to compartmentalise a task according to a pre-fabricated application. A computational task would seem to require applications to be assembled dynamically; according to the semantics of the current state.

Many of these problems have been well explored in research. For example:

• P2P systems such as Pastry explored distributed storage and look-up along with efficient distributed group membership and communication.
• Bayou and others [ Edwards 97 ] explored multi-synchronous mobile applications.
• IceCube [ Preguica et al. 03 ]explored application-independent reconciliation.
• Joyce/Telex explored collaborative/nomadic application models.

This project has two goals: firstly, to solve the deeper systems problems with web applications by applying results from the projects above; and secondly, to produce a Telex system that can be deployed in a practical environment.

We would expect a collaborative, nomadic web application to present the following user experience:

1. The user opens some shared data by browsing to a url or choosing from a Metro provided list: say the user opens presentation.xml
2. If the client device is online, the browser will securely join the collaborative group for presentation.xml and synchronise with the group activity.
3. An application is created that is suitable for client device. The browser will discover behaviour and display information and combine them to form an application interface.
4. Once the application is displayed the user starts interacting with it. Changes she makes are automatically recorded and sent to other participants.
5. Similarly, updates from other participants are reflected in her display. She may control which updates she sees and when, and she can do this without losing any information. If she makes a change that conflicts with another participant, the browser will display her change but hi-light the conflicting content region in the browser display.
6. If there is a connectivity change on the client device the application will seamlessly transition between online and off-line mode. While off-line, the user continues to work in exactly the same way as before. When connectivity is re-established, the browser will re-synchronise and highlight concurrent changes as above.
7. The user is able to visualise a global history of the task. She can use this history to remove edits from a participant, filter edits according to some predicate, and selectively undo edits (where the effect of a selective undo is limited to the undone edit and those edits dependant on it). Her display will immediately update to reflect these history edits.
8. When the user is finished editing she simply browses away from the data: whereupon the browser disengages from the collaborative group. All modifications have been automatically saved. Coarser-grained milestones of the data can also be made.

We will produce a 'webified' Telex: a system that allows a browser or RIA application to participate in a Telex group - i.e. a decentralised, collaborative group exchanging actions and constraints. By extension, our system must also enable a browser to look-up data and discover and bind applications for that data in a de-centralised fashion.

We will use Pastry to distributively look-up data and applications and maintain collaborative groups: specifically, we will extend the ideas presented in [ Castro 02]. The applications presented by the system will use the Telex application model and we will provide a way to project a multilog into the browser display.

Ideally, we would like to produce an extension for the popular browsers that participates in the system directly. However, for simplicity of initial implementation we will produce a proxy server that we expect to be running on devices with applications participating in the system.

To satisfy the user experience described above, the system needs to provide three main services:

• Content storage and discovery: we need to provide a storage mechanism for content that is distributed, secure, and fault tolerant. The user should be able to easily look-up content and content should be accessible from anywhere. The storage mechanism should potentially be global but should also support localised storage accessible only within a controlled domain (e.g. an intranet). Finally, the user should be able to discover new content via notification or search.
• Synchronisation and collaboration: we must supply a multi-synchronous collaboration and synchronisation mechanism. The nature of the problem implies that this mechanism cannot be tied to a specific set of application semantics but must rather be general enough to apply to all applications. The mechanism must also cope with mixtures of connectivity and a high degree of churn in the collaborative group membership. Finally, the mechanism must be able to automatically discover a collaborative group and be able to join it securely.
• Service discovery and binding: we will need to provide a mechanism whereby the user can find applications to edit her content (discovery) and display those applications in her browser or rich client (binding). Ideally, we would like to dynamically synthesise an application from component parts such that it reflects the composition of the content. Moreover, the user should be able to verify that the service implementation comes from a trusted vendor and we should support multiple implementations of a service such that an appropriate implementation can be chosen for a specific context.

Content is the shared material concurrently modified by participants in a collaborative group. In current web architectures content is stored on a centralised server and a participant is required to know the unique address of the content (in the form of a URL). These conditions are difficult to maintain in a de-centralised, variably connected environment so Metro needs to provide content look-up that does not depend on stable connectivity or opaque identifiers.

Instead of a simple URL, content in metro is described using a content certificate specifying the name of the content, a description of the content and contact details of participants in the content's collaborative group. Content certificates are signed with the public key of the participant creating the content and inserted into a DHT called a content ring. The de-centralised nature of the DHT allows participants to access content in a variety of network conditions and localities without the need of a central server.

In practical deployments, the nodes forming a content ring are likely to belong to a particular organisational unit of a company: all the machines in HR or all the servers in engineering for example. Segmenting a DHT in this way makes it easier to administer with respect to security and network configuration (NATs, firewalls etc.) [ Mislove 06 ]. Each node in a content ring is assigned a 128-bit ID that is bound to a public key by some organisational or global authority: this ID/key binding is known as the node certificate and is used to authenticate nodes attempting to use a content ring.

Note that the content certificate - the description of the content - is stored separately from the content data. The content data may be stored on a central server for backwards compatibility or may also be inserted into the content ring. Nodes can discover new content ether by listening to an advertising tree - an internal multicast tree on which content originators post announcement messages - or by searching a distributed index.

Activity - that is modifications to a shared content - will be represented using the action/constraint formalism from Telex. Local modifications are recorded using actions (representing atomic modifications) and constraints (representing invariants) in a graph-structure distributively maintained using an epidemic propagation system.

The collaborative group working on some shared content consists of a small Pastry ring, each node of which is a member of a spanning scribe tree dedicated to propagating multi-log updates. When a new participant joins the tree it will make a vector-clock and update exchange to bring itself up-to-date with the group (and the group up-to-date with it).

A service is a bundle of display and behaviour code capable of editing one or more types of content. Current web applications assume a homogenous client environment and seldom make a distinction between content and its HTML representation: in effect locking content within application code. We, in contrast, wish to support a mixture of clients and connectivity and therefore require services and content to be separate: different clients may require different implementations and we would like to enable different vendors to offer implementations of the same service.

Metro represents services using the service and code certificate ideas presented in [ Castro 02 ]. A service certificate is a description of an abstract service. It specifies the name of the service, a description of the service and a number of code keys that point to different implementations of the service - where implementations may be differentiated by vendor or client technology.

The service certificate is created and digitally signed by the publisher of that service and is pushed into a DHT called a service ring using a secure hash of the certificate as the key (note that this is analogous to publishing content in a content ring.) Service rings may also contain internal multi-cast trees that can be used to advertise new services.

Code certificates describe specific implementations of an abstract service; where implementations are usually differentiated by vendor or client technology. A code certificate contains meta-data such as the name of the implementation, client technology, vendor information etc. and also the display and behaviour code that forms the implementation: the format of which will be defined by the client technology specified in the meta-data.

To publish an implementation, the vendor signs the code key (important for users that do not want to run arbitrary code) and pushes it to a service ring or well known server.

This section will illustrate how the elements described in section 3 work together when creating and consuming content.

1 A code certificate specifies if a service implementation can create new content and the user is presented with a browsing interface presenting all such service implementations.

2 She 'opens' one of these services - an address book in this case.

3 The service loads and creates a base content with a UUID but which has not been published to a content ring.

4 The user modifies this base content to create her first draft - we may or may not keep the logs pertaining to this initial modification.

5 When the first draft is complete the user publishes it to a content ring; filling in necessary information such as contact details. Obviously, much of this process is automated by the metro software.

Other metro participants may discover new content via a search or may be notified of it through an advertising tree. Say an interested user is notified of the content created in section 4.1 via a content certificate received through an advertising tree. To work on the content he must establish himself within the collaborative group for that content, which will involve:

• Authenticating himself and joining the group's multicast tree.
• Retrieving a snapshot of the content data
• Binding a service instance that he can use to edit the content

Ideally, we would like to accomplish all three steps through the content's collaborative group. The procedure would be:

	1 The joiner authenticates and joins the collaborative group.
	2 The joiner asks the group for the most recent snapshot.
	3 The joiner checks its local store for service implementations suitable for the content. If it doesn't have one, it asks the group for a suitable service implementation given the joiner's client type and capability.
	4 The joiner makes a vector-clock and update exchange to synchronise itself with the current state.

However, we expect it to be unlikely that the joiner's contact point is willing or able to expend the bandwidth to transfer content and service data to the new joiner. A naive solution to this would simply be to crawl the multicast tree looking for a capable node:

1. The joiner queries the group for a service suitable for its client technology.
2. The contact node does not have a suitable implementation (e.g. its client technology might be different).
3. Ditto
4. This node does have a suitable implementation and a confirmation message is propagated back.
5. The joiner contacts the service source directly and downloads the service. If the joiner cannot contact the source due to networking issues we could propagate the service data back through the scribe tree, assuming the nodes on the path are willing.

During periods of high churn, this scheme would place undue stress on the group. A better approach may be to form a sub-tree in the group from nodes that have explicitly declared their willingness to forward code and data.

If the joiner is unable to get content and service data from the group, or is unable to contact the group at all (getting to the group may involve crossing a NAT or firewall) then it must use its configured content and service rings.

Assuming that the joiner has no local service implementation, and the group cannot furnish one, it must look one up in one of its configured service rings. Ideally, we would like to search the service ring, perhaps using a distributed index fed when implementations are published to the ring. The joiner specifies the UTI of the content and the implementation technologies it is able to execute:

A simpler alternative is to have the content certificate specify a service key. The joiner looks up the service certificate and downloads a suitable implementation. The procedure would be:

1 The joiner has a content certificate that specifies a service key, say:

{
    name = 'My Corporate Staff',
    uti = 'metro.contacts',
    svc = 890123
}
		

2 The joiner looks up service key 890123 on one or more of its configured service rings:

In this case the service key contains details of a native Windows and an HTML implementation of the service.

3 The joiner picks a suitable implementation, say the HTML one, and looks it up:

The ideal implementation with respect to general adoption would be to produce a Telex extension to Lighttpd - a well-established, light-weight web server that has been used in high-traffic sites such as YouTube. Obviously an extension to Apache is also desirable but a common usage scenario will be to run the server as a proxy on a local device - lighty's small footprint makes it more suitable. However, lighttpd is implemented in C; implying log development times and finicky memory management bugs.

To minimise the amount of time wasted developing a native version we will first produce a prototype in Python. This prototype will probably not be performant enough for production usage but Python should offer rapid development times and cross-platform compatibility.

One thing to note is that FreePastry is implemented in Java so we will have to wrap it in a separate daemon. This is reasonable since the concerns of the two daemons (the metro proxy and the pastry daemon) are quite separate and a general Pastry daemon would be useful.

Development will happen in 3 phases:

In this phase we will produce an activity service - essentially, a web server that 'speaks' Telex such that a browser can:

• Retrieve 'snapshots' of data in the form of a simple HTML application that can be used to edit the data.
• Send multi-log updates
• Retrieve multi-log updates
• Create new snapshots

We will produce a system daemon that provides distributed hashtable and multicast services to client applications. We will war the daemon around FreePastry initially and communicate with local applications via OS IPC mechanisms (possibly using HTTP as the protocol) Once the Pastry Daemon is compete we will use it, and the activity service, to form simple content and service rings.