Fair,biased, and self-balancing merge operators: Their specification and implementation in Concurrent Prolog |
| |
Authors: | Ehud Shapiro Colin Mierowsky |
| |
Affiliation: | 1. Department of Applied Mathematics, The Weizmann Institute of Science, 76100, Rehovot, Israel
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|