Factual Knowledge For Developing Concurrent Programs

Andrzej Skowron, Alberto PettorossiAAAI 1986

This classic 1986 paper from the AAAI proceedings explores a foundational challenge in computer science: how to transform a simple, "obviously correct" program into a high-performance concurrent one without losing its correctness. Authors Pettorossi and Skowron propose a framework that uses "factual knowledge"—mathematical properties of the program—to automatically inject communication between parallel processes, effectively turning slow algorithms into fast ones.

The Software Gap and "Eureka Steps"

In the mid-80s, as parallel computing began to emerge, the "software gap" was a major hurdle. Writing concurrent programs is notoriously difficult and error-prone. The standard methodology at the time (the Burstall-Darlington approach) required programmers to write a simple version of a program and then manually apply "eureka steps"—clever, intuitive insights—to transform it into something efficient.

These "eureka steps" were the bottleneck; they were ad-hoc and hard to automate. This paper seeks to formalize those insights as "factual knowledge." The goal is to build a system that can verify these facts and use them to automatically derive distributed algorithms that share data to avoid redundant work.

The Logical System Architecture

The authors propose a Logical System designed to bridge the gap between high-level specifications and efficient concurrent implementations.

The Logical System architecture featuring Calculus C and the Translation Algorithm

The system is composed of three main modules:

  1. Calculus C: A theorem prover that uses symbolic evaluation (running the program with variables instead of numbers) and induction to verify if a suggested "fact" about the program is actually true.
  2. Knowledge Base: A repository that stores transformation rules and "historical information" about past derivations. It includes a "learning process" that tracks which strategies were effective.
  3. Translation Algorithm (Tr): The core engine that takes a verified fact and uses it to rewrite the program. It injects communication annotations like read, write, and comm.

Memoization via Communicating Agents

The system operates on a model of Communicating Agents. When a program runs, it creates a tree of agents. If the system discovers that two different branches of this tree are calculating the same thing, it instructs one agent to write its result to a shared memory location and the other to read it, rather than re-calculating it.

Agent dependency tree showing shared communication to avoid redundant computation

In a standard functional program, redundant calls are just slow. In a concurrent system, they represent a massive waste of resources. The paper treats shared memory locations as a way for parallel agents to "memoize" results for one another on the fly. By identifying overlapping sub-problems through logic, the system can transform a non-linear recursion (which often has exponential complexity) into a linear-time process by ensuring each unique sub-problem is solved only once.

Key Results: The Chinese Rings Problem

As a benchmark, the authors use the N Chinese Rings Problem (a classic recursive puzzle similar to the Tower of Hanoi). They demonstrate that their system can take a recursive definition of the puzzle and, by applying specific logical facts, derive a program that uses a linear number of agents and achieves linear time complexity.

The paper provides a formal proposition stating that if a reading communication is added to a non-linear recursion based on a valid fact, it can save an exponential number of calls. Furthermore, a "Correctness Theorem" guarantees that if the initial program is correct and the facts are verified, the resulting concurrent program will produce the same results, provided it is deadlock-free.

Limitations and Future Work

While groundbreaking, the framework has limitations. The current version of Calculus C is limited to programs with a single recursive case. Additionally, while the system verifies and applies facts, it still largely relies on the programmer to "discover" the initial facts. Future work aims to automate this discovery process and provide universal algorithms for ensuring deadlock-free execution in all cases.

Summary updated

BibTeX
@inproceedings{skowron1986factual,
  author = {Andrzej Skowron and Alberto Pettorossi},
  title = {{Factual Knowledge For Developing Concurrent Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure