Links und Funktionen

Sie sind hier: Startseite / Lehre / WS 2010/11 / Oberseminar / Vivek Nigam, Maintaining Distributed Recursive Views Incrementally


Vivek Nigam, Maintaining Distributed Recursive Views Incrementally

TCS Oberseminar, 26.11.2010, 14:15
Wann 14:15 15:00 26.11.2010
von bis
Wo L109
Termin übernehmen vCal

 Vivek Nigam, Maintaining Distributed Recursive Views Incrementally

Recently many languages based on Datalog, such as Network Datalog, MELD and Netlog, have been proposed that allow programs to be distributed among different agents in a network. By using these languages, one is able write programs for distributed systems such as networks and multi-agent robotic systems in a declarative fashion. However, in order to run efficiently, they rely on the key observation that distributed systems deal at their core with maintaining distributed states. This paper proposes an algorithm to compute incrementally the changes to distributed recursive database views in response to insertions and deletions of base facts. Our algorithm uses a pipelined semi-\naive (PSN) evaluation strategy introduced in declarative networking. Unlike prior work, our algorithm is formally proven to be correct for recursive query computation in the presence of message reordering in the system. Our proof proceeds in two stages. First, we show that all the operations performed by our PSN algorithm computes the same set of results as traditional centralized semi-\naive\ evaluation. Second, we prove that our algorithm terminates, even in the presence of cyclic derivations due to recursion.


abgelegt unter: