Browse Prior Art Database

Deadlock-Free Message Passing Protocol in Csp-Based Languages

IP.com Disclosure Number: IPCOM000037293D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 16K

Publishing Venue

IBM

Related People

Jung, CD: AUTHOR

Abstract

Disclosed is a message-passing communication protocol which establishes a hierarchical relationship between message-send (output) statement and message-receive (input) statement in CSP-based (1) languages in order to avoid indefinite-wait condition without prohibiting the use of the output statement as a guard. The protocol establishes a hierarchical relationship generally whether an input or output statement is involved in polling (selective operation on a set of input and output statements) or not. The protocol also provides an effective polling termination paradigm by eliminating the need for a polling process to check the termination status of the polling partners.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 4

Deadlock-Free Message Passing Protocol in Csp-Based Languages

Disclosed is a message-passing communication protocol which establishes a hierarchical relationship between message-send (output) statement and message-receive (input) statement in CSP-based (1) languages in order to avoid indefinite-wait condition without prohibiting the use of the output statement as a guard. The protocol establishes a hierarchical relationship generally whether an input or output statement is involved in polling (selective operation on a set of input and output statements) or not. The protocol also provides an effective polling termination paradigm by eliminating the need for a polling process to check the termination status of the polling partners.

Hoare introduced the concept of polling in his Communicating Sequential Processes (CSPs) (1) to handle nondeterministic message communication in distributed programming. The major problem of CSP-based polling is that the language prohibits the use of output guard in the polling statement in order to avoid an indefinite-wait situation which can be caused by simultaneous polling among distributed processes. This causes a language asymmetry in CSP. Silberschatz (2) proposed a hierarchical relationship to avoid simultaneous polling without prohibiting the use of an output guard; a message communication (correspond or rendezvous) between two processes occurs using input and output statements in which at most one of them can be involved in polling at any given time and a polling process becomes a slave in the relationship. However, Silberschatz's proposal did not introduce how to establish a hierarchical relationship between two input/output statements which are not involved in polling, and it did not consider process termination in the distributed message communication.

This invention extends Silberschatz's proposal and solves the problems through the following message communication protocol:

The input or output statement which is not involved in polling initiates the handshaking and becomes the master if no handshaking has already been initiated by the partner. Otherwise (handshaking has been initiated by the partner), it becomes a slave.

The input/output guards in the polling statement never initiate handshaking and they become slaves in any message communication.

Polling terminates if no handshaking has been received from any communicating partner, unless the polling process is intentionally put to sleep by the programmer's explicit specification.

The following is a detailed descriptions of the protocol. Input/output statements not engaged in polling are called hard input/output statements, and they are called soft input/output statements if they are used as input/output guards in polling. In the following description, main-msg is the main message to be communicated between two processes, and the rest are messages for handshaking purposes.

Hard Input Statement:

1

Page 2 of 4

IF no main-msg from partner is i...