Partial metrics : the story

The story is one of distinct research work into data flow analysis, non-symmetric topology, and domain theory each finding a common interest in developing the seemingly impossible, a notion of metric space for non-Hausdorff topologies.

Deadlock analysis for Gilles Kahn's model of data flow (concurrent) computation was addressed by Bill Wadge's cycle sum test [Wad81]. However, this test defied any obvious generalisation to lazy data flow programming languages such as Lucid [WA85]. This problem became the work of Steve Matthews [Mat85], in whose PhD thesis the difficulty of generalisation became understood in the following terms. Scott's elegant prevailing theory of domains [AJ94] demonstrated the combined partially ordered and non-Hausdorff topological structure of partial objects in computation. Also, Kahn data flow was just one example of how computation over metric spaces [Su75] naturally arises. Thus, there must be a metric structure for the partial objects in computation over a metric space of non-partial (aka total) ones? But, in Matthews' thesis, this led to the seemingly impossible conclusion. For each metric d, each partial object x must have non-zero self-distance d(x,x). Matthews' ideas were studied by Steve Vickers (in unpublished notes [Vi87]) who we believe to be the first person to introduce the triangularity axiom d(x,z)+d(y,y)<=d(x,y)+d(y,z). By 1992 the axioms were finally settled upon, to express the idea that a partial metric is a least generalisation of the notion of metric [Su75] such that self-distance is no longer necessarily zero [Mat92]. Greatly encouraged by Ralph Kopperman (who had recently demonstrated that "All topologies come from generalised metrics" [K088]) this work was presented in 1992 at the Eighth Summer conference on Topology and Applications at Queen's College New York, subsequently refined and published in its proceedings [Mat94]. By this time metrics had already been well known to the poset plus Scott topology school of domain theory. Michel Schellekens comments as follows.

"An alternative to this essentially order theoretic approach was proposed by the Dutch school at CWI and originated in work by De Bakker, Zucker and America. This approach advocates the use of metrics.
In order to reconcile both approaches to Domain Theory, Smyth pioneered at Imperial College the use of methods from the field of Non-Symmetric Topology. This field traditionally studies `quasi-metrics` which are obtained from classical metrics by removing the symmetry requirement. Hence, for quasi-metrics, the distance from a given point to a second point need not be the same as the converse distance. A simple example of a quasi-metric is the 0-1 encoding of a partial order which defines the distance between two points x and y to be 0 in case x is below y in the order and 1 otherwise." [Sch02]

Questions now arose as to how partial metrics related to such quasi-metric non-symmetric topology, and thus how they related to domain theory. Matthews had already introduced the weighted quasi-metric q(x,y)=p(x,y)-p(x,x) for any partial metric p, and shown that not every quasi-metric is weightable. However, it was Künzi and Vajner [KV94] who first properly explored the question, which topologies can arise from a weighted quasi-metric (equivalently a partial metric)? See their abstract.

Simon O'Neil, for his PhD thesis at Warwick, employed valuations to explore the connections between partial metrics and domain theory [O95, O98].

To be continued ...