Following on from the discussion on link consistency and
Hyper-G I enclose the following message from Dave Ingham, a
researcher in the Computing Science department at Newcastle
University.
Dave gave a paper at the Boston WWW Conference and is giving one at
the Paris conference. I'd be interested in comments on his work
and whether W3Objects has a role to play for eLib projects - it would
be a pity if we missed out on important work being developed within
the UK Higher Education community.
Further information about W3Objects is available at the URL
http://arjuna.ncl.ac.uk/w3objects/
This contains a pointer to background material and his Boston paper
- a link to his Paris papr will be available shortly.
I you have any comments for Dave, please include him
([log in to unmask]) in the distribution list as he's not a
member of this list.
thanks
Brian
------------------------------------------------------------
The use of database technology for link maintenance allows Hyper-G to
provide referential integrity for 'local' links, i.e. those which
originate and terminate within the same server. Another technique is
required for links which span servers, 'surface links' I believe
Hyper-G terms them.
What follows is an extract from our paper "Fixing the Broken-Link
Problem: The W3Objects Approach", to be presented at WWW5, Paris, May
96. We propose a technique based on forward referencing with chain
shortcutting. I'm currently making a few changes to the paper based on
reviewers comments but will make it generally available soon. I'll get
Brian to announce it here if there is interest.
---start---
Maintaining referential integrity for surface resources requires a
server update protocol to propagate update information describing the
deletion or migration of resources and creation or deletion of links.
This information is added to an update list. A flooding algorithm
(p-flood) is used to disseminate this update information to all other
servers. Therefore, a server's update list contains both locally
generated messages and those received from other servers. Exact
details of the operation of the flooding algorithm may be found in
[Kappe95a] but essentially the servers are organised in a circle and
periodically each server sends its update list to a small number of
other servers resulting in the eventual transmission of all updates to
all servers.
Analysis of this update scheme reveals a number of drawbacks:
Scaleability: The remote server update mechanism claims to scale well.
In fact, since it is a broadcast mechanism, in the sense that all
servers are informed of all updates, the total additional message
traffic required scales proportionally to the number of servers. The
forward referencing approach scales proportionally to the number of
outward links held by an object, a much smaller figure than the number
of servers.
Cost Distribution: The cost associated with the maintenance of
referential integrity is distributed among all of the servers. The
vast majority of update requests that a particular server will process
will be for resources that are of no local interest. The W3Objects
forward referencing approach divides the cost between reference
holders only. Therefore a cost is only incurred by those parties who
are explicitly interested in the object.
Consistency: The proposed update mechanisms will not eliminate broken
links entirely since update information is disseminated lazily
resulting in a period of time when links will be invalid. Conversely,
forward referencing provides strong consistency; a path to the object
will always exist.
In conclusion, while the Hyper-G flood-based approach for maintaining
distributed referential integrity may be appropriate for
enterprise-wide systems, it is questionable whether the approach is
appropriate for an Internet-wide system where the number of servers is
likely to be measured in millions.
[Kappe95a] F. Kappe, "A Scalable Architecture for Maintaining
Referential Integrity in Distributed Information Systems," J.UCS Vol.
1, No. 2, pp. 84-104, Springer, February. 1995.
-----------------------------------------------------------------------------
David Ingham (Research Associate) PHONE: 0191 222 8067
Department of Computing Science, FAX: 0191 222 8232
The University, URL: http://www.cs.ncl.ac.uk/~dave.ingham
Newcastle upon Tyne, NE1 7RU, EMAIL: [log in to unmask]
United Kingdom or [log in to unmask]
-----------------------------------------------------------------------------
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|