Paper by Erik D. Demaine
- Erik D. Demaine, “Protocols for Non-Deterministic Communication over Synchronous Channels”, in Proceedings of the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP'98), Orlando, Florida, March 30–April 3, 1998, pages 24–30.
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.
- The paper is 7 pages and the talk is 20 minutes.
- The paper is available in PostScript (104k).
- The talk is also available in PostScript (146k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ProtocolsTR (Adaptive Protocols for Negotiating Non-Deterministic Choice over Synchronous Channels)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by