Paper by Erik D. Demaine

Reference:

Erik D. Demaine, “Adaptive Protocols for Negotiating Non-Deterministic Choice over Synchronous Channels”, Technical Report CS-97-35, Department of Computer Science, University of Waterloo, September 1997.

Abstract:

In this paper, we propose several deadlock-free protocols for implementing the generalized alternative construct, where a process non-deterministically chooses between sending or receiving among various synchronous channels. We consider general many-to-many channels and examine in detail the special case of fan (many-to-one and one-to-many) channels, which are common and can be implemented much more efficiently. We propose a protocol that achieves an optimal number of message cycles per user-level communication, significantly improving on previous results. We propose several other “less aggressive” protocols, which may be more suitable for some applications and networks, and demonstrate how to adaptively switch between them and modify protocol parameters. Finally, we show how to maintain dynamic membership of channels, while avoiding race conditions that would prevent garbage collection of processes.

Length:

The paper is 16 pages.

Availability:

The paper is available in PostScript (190k).

See information on file formats.

[Google Scholar search]

Related papers:

IPPS98 (Protocols for Non-Deterministic Communication over Synchronous Channels)