http://www.cs.waikato.ac.nz/~hinze/DEBS2006/
List of accepted papers
paper p03 (full paper presentation)
Dimension-Based Subscription Pruning for Publish/Subscribe Systems
Sven Bittner & Annika Hinze, Department of Computer Science
University of Waikato, Hamilton, New Zealand
{s.bittner, a.hinze}@cs.waikato.ac.nz
Subscription pruning has been proven as valuable
routing optimization for Boolean subscriptions in publish/
subscribe systems. It aims at optimizing subscriptions
independently of each other and is thus applicable for all
kinds of subscriptions regardless of their individual and collective
structures. The original subscription pruning approach
tries to optimize the event routing process based on
the expected increase in network load. However, a closer
look at pruning-based routing reveals its further applicability
to optimizations in respect to other dimensions.
In this paper, we introduce and investigate subscription
pruning based on three dimensions of optimization:
network load, memory usage, and system throughput. We
present the algorithms to perform prunings based on these
dimensions and discuss the results of a series of practical
experiments. Our analysis reveals the advantages and disadvantages
of the different dimensions of optimization and
allows conclusions about the suitability of dimension-based
pruning for different application requirements.
paper p04 (full paper presentation)
Handling Overload in Publish/Subscribe Systems
Zbigniew Jerzak, Christof Fetzer
Dresden University of Technology
D-01062 Dresden, Germany
Telephone: ++49 351 463–39708
Fax: ++49 351 463–39710
Email: {Zbigniew.Jerzak, Christof.Fetzer}@tu-dresden.de
Abstract—This paper proposes a new approach for handling overload
in Publish/Subscribe systems. We focus on the fact that every service has
to cope with the limitations imposed by the external environment (e.g.,
network congestion) and the limitations resulting directly from within
the service itself – e.g., the maximum available computational power.
This work seeks to aid Publish/Subscribe mechanisms with the ability to
handle both aforementioned constraints in a graceful way, simultaneously
ensuring for the most valuable information to be given the highest chance
of a successful delivery.
paper p06 (short paper presentation)
Semantics and Rule Based Event-driven Services-Oriented Agricultural
Recommendation System
Zakir Laliwala1, Vikram Sorathia1 and Sanjay Chaudhary1
1 Dhirubhai Ambani-Institute of Information and Communication Technology
Gandhinagar, 382009, India
{zakir_laliwala, vikram_sorathia, sanjay_chaudhary}@da-iict.org
Agricultural Information Systems (AIS) are rich
sources of information being created, maintained and
published for the benefits of the farmers and agroprofessionals.
Ongoing research has generated
knowledge regarding best practices in various aspects for
farming practices to improve the yield. On the other
hand, advancements in information technology and
sensor technology have enabled new avenues of
information for informed decisions and to utilize near
real-time monitoring of data to provide effective
recommendations. Even in this scenario, finding,
extracting and integrating information from distributed
heterogeneous sources of AIS and assimilating with realtime
events like change in climatic conditions, change in
market etc have raised interesting issues. We need a
mechanism to collect and integrate the information from
scattered sources according to events and to notify the
end-users with precise recommendations according to
user context, location and requirements. In this paper, we
have proposed a semantics and rule based event-driven
Services-Oriented Architecture to facilitate the seamless
and meaningful information integration and
interoperation of distributed and heterogeneous web
hosted AIS services to deliver personalized
recommendation driven by real-time events and user
preferences.
paper p07 (short paper presentation)
Preservation of Correctness During System
Reconfiguration in Data Distribution Service for
Real-Time Systems (DDS)
Bogumil Zieba
Thales Nederland B.V,
AWS Department
Haaksbergerstraat 49, Hengelo (O), 7554 PA,
The Netherlands
bogumil.zieba@nl.thalesgroup.com
Marten van Sinderen
University of Twente,
Department of Computer Science,
Centre for Telematics and Information Technology,
PO Box 217, 7500 AE, Enschede, The Netherlands
m.vansinderen@utwente.nl
This paper addresses dynamic
reconfiguration of distributed systems that use a
publish/subscribe (pub/sub) middleware. The objective of
dynamic reconfiguration is to evolve incrementally from
one system configuration to another at run-time in order
to e.g., ensure the reliability of the system. The correctness
notion of a distributed system is introduced that assures
that the system parts that interact with entities under
reconfiguration do not fail because of reconfiguration. We
analyse the OMG specification of pub/sub systems - DDS
(Data Distribution Service for Real-Time Systems) with
respect to its support for the correctness preservation
during reconfiguration. We notice that the DDS
specification defines such an architecture and behaviour of
the pub/sub system that automatically preserves
correctness. This differentiates the DDS from other
middleware technologies that require that the correctness
preservation is guaranteed on application level or by
reconfiguration manager/controller. We give several
examples of automatic correctness preservation supported
by the DDS.
paper p08 (short paper presentation)
Combining Programming Paradigms in
Asynchronous Systems
paper has been withdrawn
paper p10 (full paper presentation)
Reconfiguring Publish/Subscribe Overlay Topologies
Helge Parzyjegla Gero M¨uhl Michael A. Jaegery
Communication and Operating Systems Group
Berlin University of Technology
Einsteinufer 17, 10587 Berlin, Germany
parzy@cs.tu-berlin.de, fg muehl,michael.jaegerg@acm.org
Distributed content-based publish/subscribe systems are
usually implemented by a set of brokers forming an overlay
network. Most existing publish/subscribe middleware
assumes that the overlay topology is static. Those that consider
reconfiguration, exchange a single link that is teared
down by another link that comes up. However, they do not
guarantee that no notifications are lost or duplicated nor do
they ensure FIFO-publisher or causal ordering.
In this paper, we discuss the dynamic reconfiguration of
publish/subscribe systems which are built on content-based
routing. We present algorithms that allow for reconfigurations
without notification loss or duplication that can also
ensure FIFO-publisher and causal ordering. Moreover, the
efficiency of reconfigurations is increased by limiting their
effects to those parts of the network which are directly affected
by the reconfiguration.
paper p11 (short paper presentation)
Preventing Spam in Publish/Subscribe
Sasu Tarkoma
Helsinki Institute for Information Technology
Tammasaarenkatu 3, P.O. Box 9800
02015 TKK, Finland
E-mail: sasu.tarkoma@hiit.fi
Abstract—Publish/subscribe protocols are becoming popular
on the Internet with the advent of RSS-feeds, Session Initiation
Protocol (SIP) events, peer-to-peer networks, and Web services.
Since publish/subscribe is by nature many-to-many form of
communication, it is vital to prevent spam and Denial of
Service (DoS) attacks. This problem has not been yet been
fully addressed. In this paper, we investigate the spam problem
in publish/subscribe and outline several solutions inspired by
current email spam prevention techniques. We analyze filterbased
spam in distributed pub/sub systems and focus on the
detection and mitigation of bogus publishers and brokers.
paper p12 (full paper presentation)
Content-Based Publish/Subscribe: A Reassessment
Costin Raiciu David S. Rosenblum Mark Handley
Department of Computer Science
University College London
{c.raiciu|d.rosenblum|m.handley}@cs.ucl.ac.uk
Content-based publish/subscribe is a very appealing
interaction model that has attracted intense efforts
from the research community in the quest to obtain
“Internet-wide” scalability. Despite many promising
proposals, wide-area applications using content-based publish/
subscribe are yet to be deployed. In this paper, we
list possible reasons for this lack of adoption and propose
a series of approaches to mitigate this state of affairs. To
simplify the problem tackled, we argue for the separation
of content-based matching and event-routing. To cope with
application diversity, we propose the development of configurable
solutions for parts of the problem space and provide
a proof-of-concept solution for content-based matching. Finally,
we briefly discuss some issues related to the deployment
of content-based publish/subscribe solutions and applications.
paper p16 (full paper presentation)
On The Accuracy of Event Distribution Lists for Publish/Subscribe
in Dynamic Distributed Systems
R. Baldoni1, G. Cortese2, F. Morabito2, L. Querzoni1, S. Tucci Piergiovanni1 and A. Virgillito1
1. Dipartimento di Informatica e Sistemistica 2. Telecom Italia Learning Services S.p.A.
Universit`a di Roma “La Sapienza” Via Giovanni Falcone 25, I-67010 Coppito - Italy
Via Salaria 113, I-00198 Roma - Italy g.cortese@computer.org
{baldoni, querzoni, tucci, virgi}@dis.uniroma1.it federico.morabito@telecomitalia.it
The advent of very large scale distributed applica-
tions in the form of peer-to-peer systems, introduced
new problems caused by their intrinsic dynamic be-
havior (i.e., nodes continuously joining and leaving
the system). Such problems inhibit the usage of tech-
niques developed for quasi-static distributed systems.
In this paper we analyze the behavior of a simple rout-
ing algorithm (based on subscription flooding) for pub-
lish/subscribe when coping with highly dynamic behav-
ior. Specifically we define the problem of keeping com-
plete and accurate along the time a list of processes
matching a given event (Event Distribution Lists). We
propose a simple variant of the subscription flooding
algorithm, introducing expiration of subscriptions and
their periodic refresh, and show how it can maintain
accurate and complete EDLs in a dynamic distributed
system.
paper p17 (full paper presentation)
Specification-based Unit Testing of Publish/Subscribe Applications
Anton Michlmayr, Pascal Fenkam, Schahram Dustdar
Vienna University of Technology, Distributed Systems Group
A-1040 Wien, Argentinierstrasse 8/184-1
{michlmayr,fenkam,dustdar}@infosys.tuwien.ac.at
Testing remains the most applied verification method
for software systems. Typically, the behavior of such
systems is evaluated against their informal or formal
specifications. In this paper, we consider an
architecture-driven approach to software testing. We
support the argument that, in many cases, the difficulties
in testing can be alleviated by optimizing the test
methodology to leverage the architecture of the application
under test. To support this claim, we present a
test framework for publish/subscribe applications. This
paper evaluates our initial steps in this regard. We focus
on the design of our framework, and illustrate how
to accomplish unit testing of publish/subscribe applications
against LTL specifications, considering a realworld
application as example.
paper p19 (full paper presentation)
Coping with Variable Latency and Disorder in
Distributed Event Streams
Roger S. Barga and Gueorgui Chkodrov
Microsoft Research
barga@microsoft.com
Distributed event processing systems often require input streams ordered in some predetermined way
and that events arrive within a fixed time interval, or window. This order may simply be arrival order
or given explicitly on specific event attributes, such as timestamp or sequence number. Standing
event queries over multiple streams, such as a temporal correlation of events across multiple streams,
often block if one of the input streams is very slow or produce an incorrect answer if events fail to
arrive within the fixed time window. Punctuation and heartbeats have been proposed in the literature,
but in practice it is a challenge to incorporate such mechanisms into a robust and scalable event
correlation service for use in industrial applications.
In this paper, we introduce a punctuation-carrying stream conditioning mechanism we have
developed for Event Correlation Services (ECS), a high performance event processing service for
monitoring distributed applications, currently being developed and tested within Microsoft. We show
how heartbeats and timestamps can be regularly generated by low-level nodes and propagated upward,
to unblock standing event queries and align events from multiple distributed streams. Additionally,
our stream conditioning mechanism can be used for other applications in distributed event processing
such as performance monitoring of event flows and optimizing distributed event queries.
paper p20 (full paper presentation)
An Event Service Supporting Autonomic
Management of Ubiquitous Systems for e-Health
Stephen Strowes, Nagwa Badr, Naranker Dulayy, Steven Heeps, Emil Lupuy, Morris Slomany and Joe Sventek
Department of Computing Science, University of Glasgow
fsds,nagwa,heeps,joeg@dcs.gla.ac.uk
yDepartment of Computing, Imperial College London
fn.dulay,e.c.lupu,m.slomang@doc.ic.ac.uk
http://www.dcs.gla.ac.uk/amuse/
Healthcare and economic drivers have increased the
desire to deploy systems for continuous monitoring of patients,
both in hospital and outpatient settings. Such systems must
operate autonomically, and must meet a number of operational
constraints. Event systems used in traditional monitoring systems
have not been designed with these constraints in mind. We
describe the design, implementation, and performance characteristics
of an event system targeted at this application domain.
paper p22 (full paper presentation)
Reducing Latency in Rendezvous-Based Publish-Subscribe Systems forWireless
Ad Hoc Networks
Nuno Carvalho
University of Lisbon
nunomrc@di.fc.ul.pt
Filipe Ara´ujo
University of Lisbon
filipius@di.fc.ul.pt
Lu´ýs Rodrigues
University of Lisbon
ler@di.fc.ul.pt
To ensure decoupling between publishers and subscribers,
most publish-subscribe systems route notifications
through intermediate message brokers. A byproduct of this
practice is that notifications often follow suboptimal paths
that are much longer than a direct path. Hence, in this
paper, we propose a publish-subscribe architecture called
GeoRendezvous which aims to reduce the latency experienced
by end clients in the delivery of notifications. We
base our system on a position-based distributed hash table
(DHT) that supports rendezvous points where the interests
of publishers and subscribers match. Leveraging from previous
work, we replicate the rendezvous points to give multiple
choices of paths to the subscribers. We show that in
this way, the subscriber is able to achieve latencies comparable
to a direct publisher-subscriber path without breaking
the decoupling assumptions of the publish-subscribe model.
Additionally, we show that scalability is one of the most
prominent features of GeoRendezvous, as the number of
rendezvous points scales with the network size.
paper p23 (full paper presentation)
Automatic Subscriptions In Publish-Subscribe Systems
Lars Brenna Cathal Gurrin Dag Johansen Dmitrii Zagorodnov
Dept of Computer Science
University of Tromsø, Norway
{larsb, gurrin, dag, dmitrii}@cs.uit.no
To this point, the research community has created
advanced publish-subscribe systems with highly expressive
and scalable event dissemination. Such systems
have made it possible for publishers of short-lived
and urgent information to forward events efficiently to
larger amounts of users. However, such systems are
often very complex with proprietary query languages
making them useful only to experienced programmers.
Even the popular publish-subscribe system RSS has a
complicated subscription process.
We present a proof-of-concept prototype, in which
we use attention data from Web browsers to introduce
zero-click subscriptions to Web micronews and video
news stories. We demonstrate how to fully automate
subscription to complex publish-subscribe interfaces.
paper p25 (full paper presentation)
Finding Optimal Join Tree for Multi-Join Stream Queries in a Production System
Joseph S. Gomes
The George Washington University
Washington, DC
joegomes@gwu.edu
Heyong-Ah Choi
The George Washington University
Washington, DC
hchoi@gwu.edu
Data Stream Management Systems (DSMS) have recently
received a lot of attention from the database research
community. DSMS handles a particular type of applications
that involve multiple continuous data streams with inputs
arriving at highly variable and unpredictable rates. Since
data rate fluctuates over time in this type of applications
the appropriate join tree is crucial for maintaining high
system throughput. DSMS must also be able to adaptively
change the join tree according to the environment. We consider
the problem of finding optimal join tree for performing
count based sliding window multi-joins over continuous
streams. We use a unit-time based cost model to evaluate
the expected performance for a given join tree. We materialize
all intermediate results assuming there is enough main
memory to store all partial results and window buffers. We
give a polynomial time algorithm that finds the optimal join
tree under our cost model for a given non-commuting order
of streams. This algorithm can be used in conjunction
with any linear order producing heuristic to give the optimal
tree for that order. Our algorithm is implemented in the
JESS rule engine and an extensive experimental evaluation
is provided.
paper p27 (full paper presentation)
On Quality-of-Service and Publish-Subscribe
Stefan Behnel
Databases and Distributed Systems Group,
Technische Universit¨at Darmstadt (TUD),
Darmstadt, Germany,
behnel@dvs1.informatik.tu-darmstadt.de
Ludger Fiege
Siemens AG,
Munich, Germany,
ludger.fiege@siemens.com
Gero M¨uhl
Communication and Operating Systems,
Technische Universit¨at Berlin,
Berlin, Germany,
gmuehl@cs.tu-berlin.de
Publish-subscribe is a powerful paradigm for distributed
communication that is based on the decoupling of
producers and consumers of information. Its event-driven nature
makes it very appealing for large-scale data dissemination
infrastructures. Various architectural designs were proposed in
recent years that provide very diverse features. However, there
are few well-defined metrics available in the publish-subscribe
area that allow their evaluation and comparison.
In this paper, we provide a broad overview of relevant
quality-of-service metrics and describe their specific meaning in
the context of distributed and decentralized publish-subscribe
systems. Our goal is to provide a common base for future
evaluations of emerging systems and for the design of qualityof-
service aware publish-subscribe infrastructures.
paper p28 (full paper presentation)
Throughput Performance of Java Messaging
Services Using WebsphereMQ
Robert Henjes, Michael Menth, and Christian Zepfel
Department of Distributed Systems
Institute of Computer Science
University of Würzburg, Germany
Email: {henjes,menth,zepfel}@informatik.uni-wuerzburg.de
The Java messaging service (JMS) is a middlewareoriented
messaging technology working according to the publish/
subscribe principle. If subscribers install filter rules on the
JMS server, JMS can be used as a message routing platform,
but it is not clear whether its message throughput is sufficiently
high to support large-scale systems. In this paper we investigate
the capacity of the Websphere Message Queue JMS server. In
contrast to other studies, we focus on the message throughput
in the presence of filters and show that filtering reduces the
performance significantly. We also present a model that describes
the service time for a single message depending on the number
of installed filters and validate it by measurements. This model
helps to calculate the system throughput for specific application
scenarios.