Maintaining Distributed Recursive Views Incrementally

Distributed logic programming languages, that allow bothfacts and programs to be distributed among different nodesin a network, have been recently proposed and used to declarativelyprogram a wide-range of distributed systems, such asnetwork protocols and multi-agent systems. However, the distributednature of the underlying systems poses serious challengesto developing efficient and correct algorithms for evaluatingthese programs. This paper proposes an efficient asynchronousalgorithm to compute incrementally the changes tothe states in response to insertions and deletions of base facts.Our algorithm is formally proven to be correct in the presenceof message reordering in the system. To our knowledge, thisis the first formal proof of correctness for such an algorithm