Pub/sub is an elegant paradigm for disseminating information efficiently and anonymously among producers (publishers) and consumers (subscribers). However, with current topic and content-based pub/sub approaches it is difficult to formulate subscriptions that adequately and accurately express the interest of the consumers in a semantic information domain. In this paper we introduce GraPS, a pub/sub middleware that provides a publication model based on graphs. Points of interest in the information domain are mapped to nodes, and relationships between points of interest are mapped to edges. Consumers can effectively express their interest in publications by means of graph subscriptions that exploit the properties of nodes and the semantics of the edge relationships. Graph subscriptions do not require complete knowledge of the graph and can be updated whenever the consumer's interest changes. Furthermore, graph subscriptions are automatically updated whenever the information domain changes. We illustrate GraPS by means of three application scenarios and present a set of experiments with an implementation of GraPS based on standard pub/sub middleware.

This article is concerned with the problem of implementing an unbounded timestamp object from multiwriter atomic registers, in an asynchronous distributed system of n processes with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen et al. [2008] showed that √ n /2 − O (1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processes can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n /6 − 1 registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen et al. [2008] constructed a wait-free algorithm that uses n − 1 registers. Second we show that √2 n − log n − O (1) registers are required for any obstruction-free implementation of one-shot timestamp systems (meaning each process can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses at most ⌈2√ n ⌉ registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.

This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert [7] showed that √n/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps).