Fair,biased, and self-balancing merge operators: Their specification and implementation in Concurrent Prolog

The problem of allowing a dynamically changing set of processes fair access to a shared resource is considered, in the context of communication-stream based systems. It is argued that fair binary merge operators alone cannot solve this problem satisfactorily. Two solutions are proposed. One employs binary merge operators with a programmable bias; the other binary and ternary fair merge operators capable of self-balancing, using the concept of 2–3 trees. A Concurrent Prolog implementation of these operators is described. The implementation of the self-balancing merge operators illustrates the expressive power of incomplete messages, a programming technique that supports messages that contain communication channels as arguments. In the course of implementing the self-balancing merge operator, it was necessary to develop a distributed variant of the 2–3 tree deletion algorithm.