Tuesday, July 12, 2011

Abstract of Research in Transactional Events

I'll be revising my abstract in this post. Comments appreciated.

Revision 1 (Initial Revision)

Revision 1 (Initial Revision)

Transactional Events is an abstraction (a well-defined concept hiding implementation details) for communication between concurrent processes (multiple programs running at once). The current implementation of Transactional Events provides only the guarantee that a communication will happen if one is possible.

A particularly attractive possible guarantee is that of "fairness," which guarantees that for a concurrent thread which is repeatedly capable of communicating, there is no point after which it never communicates.

In each of our attempts to enforce this property in the implementation, we have been able to construct counterexamples which either prevent the system from making progress or escape the enforcement of the fairness guarantee. This leads us to suspect that enforcing fairness requires the solution of an undecidable problem.

To prove that enforcing fairness requires this solution we are attempting to demonstrate that an implementation which enforces fairness would permit the solution of such an undecidable problem. Such a demonstration would prove the impossibility of enforcing the fairness condition.

Finally, we are exploring if a condition similar to fairness but weak enough to enforce would still be useful.