TARDE (Tabulation and Revision in a Distributed Prolog Environment)

Project Summary

The logical integration of several uncertainty reasoning forms in a logic programming language is becoming increasingly important for real world applications, in particular for the construction of the Semantic Web. The reasoning forms of interest include in particular, fuzzy-logic, posssibilistic logic, probabilistic systems, bayesian networks, default logic, autoepistemic logics, and non-monotonic logics. In recent work, we have partially shown how this amalgamation can be achieved via logic programming extensions, resorting to program transformations and complex fixpoint computations.

The implementation of new systems with these capabilities should naturally be supported on top of existing and robust programming languages, being PROLOG a good candidate. A particularly interesting feature of PROLOG systems is the existence of a non-monotonic negation, typically known as negation by failure, essential for knowledge representation and common sense reasoning. However, the lack of an appropriate semantics for negation by failure rendered some programs useless. In addition, the lack of a mechanism for explicitly stating falsities was an obstacle for more industrious applications. Furthermore, the PROLOG basic inference mechanism, SLDNF-resolution, has exponential behaviour for some polynomial algorithms and it does not terminate under very general conditions.

Tabling systems have embodied both the theoretical and practical work made during the last 10 years, paving the way for more reliable and efficient logic programming environments. In particular, the project will resort to the state-of-the-art XSB-PVM-PROLOG resulting from the integration of the XSB-PROLOG and PVM-PROLOG systems developed by the XSB group from the State Univ. of New York at Stony Brook and by TARDE members, respectively. Better termination properties and increased efficiency can be guaranteed by using logic programming tabling systems, crucial for natural implementations of the above mentioned fixpoint computations.

The use of declarative languages, in particular logic programming languages, for programming distributed and parallel systems is a promising area of research where important results have been obtained. Distributed logic programming abstractions are required in order to exploit the potentialities of parallel and distributed platforms, in particular for Web applications. In previous work, the (XSB) PVM-Prolog model has been developed and used to implement distributed programming constructs and their applications, in particular a basic distributed tabling system.

The combination of tabling systems, reasoning systems and distributed programming is mandatory and promising. It is expected in this much-focused project to cross-fertilise the know-how in the implementation of PROLOG distributed systems with the know-how in tabling systems and reasoning techniques. This will result in building an advanced and efficient portable distributed logic programming system, incorporating the most recent semantical and operational techniques currently available.

Project Members

Project Description

The original TARDE project was proposed in 1998, but most of the project goals remain actual and of substantial relevance. During this time no distributed tabling system has been described in the literature, besides our own and a previous work by Rui Hu (nevertheless, an or-parallel tabling system has been developed at University of Porto for definite logic programs only, see YAP’s page). The initial motivation for the project has changed, since three years have passed and meanwhile the Internet and Web technology matured and built up. We start by pointing out our long-term objective for the technology we plan to produce in this project. We will not explain again all the scientific details behind logic programming tabled evaluation. Instead, we provide the new context of the TARDE project and afterwards present the objectives and project planning for the next 3 years.

Most of the actual Web content is for human consumption. The extraction, aggregation and integration of information and knowledge by automated tools is a desiderate of the Web of the future. This has been recognized by the W3 Consortium resulting in the Semantic Web Activity. The Semantic Web Activity Statement identifies the following technological areas that are likely to contribute to the shape of the new Web:

In our opinion, distributed logic programming tabling systems are vital on helping to attain every of the previous aspects for the Web based on logic programming technology, which will afford it with integrated knowledge representation and reasoning functionalities:

In the project’s first phase, the application to the Web was not a concern for the TARDE team. However, the results obtained lend support tools and algorithms for more complex goals, in particular for Web applications. We summarize the most relevant first achievements of TARDE for the project continuation and general research goals:

Our work will be focused on defining and implementing an advanced distributed tabling systems, which technology can be inspiring for the construction of distributed (Web) based logical agents. Building upon the groundwork of the initial stage, we expect to accomplish the following objectives during the project’s second phase:

  1. Complete the dynamic distributed tabling implementation for definite and normal logic programs.
  2. Finish the implementation of the XSB-PVM threaded engine
  3. Evaluate the efficiency and complexity of the system, namely through tools that support on-line and off-line instrumentation and monitoring of MPI-2 programs.
  4. Develop tabling inference algorithms for particular instances of Antitonic Logic Programs.
  5. Integrate the threaded engine with PVM and MPI-2, defining a general API for distributed programming in (XSB-)Prolog.
  6. Provide a socket-based interface for web applications, resorting to the proposals of the RuleML group.
  7. Exploit the architecture for distributed applications.
  8. Incorporate in the system light weight communication protocols.

The project is organized into six tasks: distributed tabling system, system architecture, benchmarking, light weight communication protocols, applications, and assessment. Each task selects some of the previously listed objectives to accomplish. We also indicate the task responsible and milestones. There will be two yearly reports on the project execution and a final report. We add for each task relevant publications by team members. More can be found in the personal home pages of each task responsible.

  The hardware platform of the TARDE project is built around a cluster of eight PCs running LINUX with a heterogeneous interconnect infrastructure of Fast and Gigabit Ethernet. XSB-Prolog has access to this fast interconnect structure through a distributed programming API which is an interface to standard message-passing libraries like PVM and MPI. We allocated part of the budget for maintenance and upgrading of the cluster. The project has substantial programming effort, so we reserved part of the budget for hiring a programmer.

  Finally, we dropped the revision framework from our goals, since we were not able to find anyone interested in implementing it. Now, the “R” of our acronym should be understood as “Reasoning”. 

Project Tasks 

TASK 1 – Distributed Tabling System
RESPONSIBLE: Carlos Viegas Damásio
MAIN OBJECTIVES: 1, 6

The major issue to be addressed is the dynamic completion mechanism, i.e. the way of detecting when tables are completed (month 12).  This is fundamental for the implementation of garbage collection routines and negation (month 24). We will also define an interface for using the system components on the World Wide Web, making use of the proposals of the RuleML initiative (month 36).

All the requirements imposed by this task will be reflected in the system architecture. The resulting algorithms will be implemented on top of XSB-PVM, i.e. they will be XSB-PVM PROLOG meta-interpreters. If time allows, we will try to define program transformations to overcome the meta-interpretation overhead. This will be dependent on a fully functional XSB-threaded engine (month 36).

TASK 2 – System Architecture
RESPONSIBLE: José Cardoso e Cunha
MAIN OBJECTIVES:  2, 5  

The overall software system architecture, distributed computational model, process organisation and primitives will be defined in this task (month 12). In particular, the implementation of the XSB-threaded engine will be the major concern of this task (month 24). All general-purpose algorithms and corresponding XSB-PROLOG software modules will also be implemented in this task. This will include support for both PVM and MPI-2, on-line and off-line instrumentation and monitoring of MPI-2 programs (month 36).

These mechanisms will be made available at the level of the defined API for distributed programming in XSB-PROLOG. They will be used to enable the observation of the program behaviour that will be used in task 3, for performance evaluation. On the other hand, such mechanisms will provide support for the development of distributed applications, which will be able to dynamically adapt and change according to the computation behaviour. These functionalities are expected to become fundamental in new generations of problem-solving environments.

TASK 3 –Benchmarking
RESPONSIBLE: Salvador Pinto Abreu
MAIN OBJECTIVES:  3  

The distributed tabling system and threaded engine will be subject to a set of standard benchmarks and comparisons (month 18). The time and message complexity will be addressed, and most importantly, the speedups relative to the sequential version of the system (month 36).

The results of this task will be used to compare the gains obtained with the introduction of optimised communication primitives to be developed in task 4. This will mostly to be used to compare the performance of the algorithms on the cluster versus on the Web, to verify whether it is necessary to migrate some part of the system for a lower level implementation language.

TASK 4 – Light Weight Communication Protocols
RESPONSIBLE: Pedro Medeiros
MAIN OBJECTIVES:  8

In this task, we will integrate in the distributed programming API the so called "lightweight communication protocols" which allow the (almost) direct access of the applications to the communications hardware (month 24). One example of such lightweight communication protocols is the Intel/Compaq/Microsoft VIA standard (www.vidf.org and http://www.nersc.gov/research/FTG/via).

The implementation will be tested against the benchmarks developed in task 3 (month 36).

  The standard message-passing libraries use the standard socket system call interface, which incorporates in the communication path the overheads, associated with the processing of TCP and IP protocols. The integration of the proposed protocols will support message-passing with reduced latency, when suitable hardware is available.

TASK 4 - Applications
RESPONSIBLE: José Júlio Alferes
MAIN OBJECTIVES:  4,7

In this task, we will exploit several applications and experiment with the developed technology. One of the issues is the implementation of the advanced logical agents architecture MINERVA (month 12).  The reasoning capabilities will be extended by the definition of tabled algorithms for antitonic logic programs, allowing for the representation of uncertainty in the agent’s knowledge base (month 24). We also foresee the use of argumentation and cooperation in order to obtain and share knowledge among agents (month 36).

TASK 5 – Assessment
RESPONSIBLE: Luís Moniz Pereira

This is a coordination task helping to maintain the focus of the project, and providing directions during the project time-span. The task will also help to establish bridges with other developments in CENTRIA’s area of expertise.