Fan W.,Laboratory for Foundations of Computer Science |
Geerts F.,Middelheimlaan |
Wijsen J.,Institute dInformatique
ACM Transactions on Database Systems | Year: 2012
Data in real-life databases become obsolete rapidly. One often finds that multiple values of the same entity reside in a database. While all of these values were once correct, most of them may have become stale and inaccurate. Worse still, the values often do not carry reliable timestamps. With this comes the need for studying data currency, to identify the current value of an entity in a database and to answer queries with the current values, in the absence of reliable timestamps. This article investigates the currency of data. (1) We propose a model that specifies partial currency orders in terms of simple constraints. The model also allows us to express what values are copied from other data sources, bearing currency orders in those sources, in terms of copy functions defined on correlated attributes. (2) We study fundamental problems for data currency, to determine whether a specification is consistent, whether a value is more current than another, and whether a query answer is certain no matter how partial currency orders are completed. (3) Moreover, we identify several problems associated with copy functions, to decide whether a copy function imports sufficient current data to answer a query, whether a copy function can be extended to import necessary current data for a query while respecting the constraints, and whether it suffices to copy data of a bounded size. (4) We establish upper and lower bounds of these problems, all matching, for combined complexity and data complexity, and for a variety of query languages. We also identify special cases that warrant lower complexity. © 2012 ACM.
Bianchi S.,University of Neuchatel |
Felber P.,Institute Dinformatique |
Gradinariu Potop-Butucaru M.,French Institute for Research in Computer Science and Automation
IEEE Transactions on Parallel and Distributed Systems | Year: 2010
Publish/subscribe systems provide useful platforms for delivering data (events) from publishers to subscribers in a decoupled fashion. Developing efficient publish/subscribe schemes in dynamic distributed systems is still an open problem for complex subscriptions (spanning multidimensional intervals). We propose a distributed R-tree (DR-tree) structure that uses R-tree-based spatial filters to construct a peer-to-peer overlay optimized for scalable and efficient selective dissemination of information. We adapt well-known variants of R-trees to organize publishers and subscribers in balanced peer-to-peer networks that support content-based filtering in publish/subscribe systems. DR-tree overlays guarantee subscription and publication times logarithmic in the size of the network while keeping space requirements low (comparable to distributed hash tables). The maintenance of the overlay is local and the structure is balanced with height logarithmic in the number of nodes. DR-tree overlays disseminate messages with no false negatives and very few false positives in the embedded publish/subscribe system. In addition, we propose self-stabilizing algorithms that guarantee consistency despite failures and changes in the peer population. © 2006 IEEE.
Matos M.,HASLab High Assurance Software Laboratory |
Schiavoni V.,Institute Dinformatique |
Felber P.,Institute Dinformatique |
Oliveira R.,HASLab High Assurance Software Laboratory |
Riviere E.,Institute Dinformatique
Journal of Parallel and Distributed Computing | Year: 2013
Today's intensive demand for data such as live broadcast or news feeds requires efficient and robust dissemination systems. Traditionally, designs focus on extremes of the efficiency/robustness spectrum by either using structures, such as trees for efficiency or by using loosely-coupled epidemic protocols for robustness. We present Brisa, a hybrid approach combining the robustness of epidemics with the efficiency of structured approaches. Brisa implicitly emerges embedded dissemination structures from an underlying epidemic substrate. The structures' links are chosen with local knowledge only, but still ensuring connectivity. Failures can be promptly compensated and repaired thanks to the epidemic substrate, and their impact on dissemination delays masked by the use of multiple independent structures. Besides presenting the protocol design, we conduct an extensive evaluation in real environments, analyzing the effectiveness of the structure creation mechanism and its robustness under dynamic conditions. Results confirm Brisa as an efficient and robust approach to data dissemination in large dynamic environments. © 2013 Elsevier Ltd. All rights reserved.