US5742812A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel network communications protocol using token passing
Assignee: International Business Machines Corp
•
Filing: 1995-08-28
•
Granted: 1998-04-21
•
Expires: 2015-08-28
Abstract
Abstract A protocol for achieving atomic multicast in a parallel or distributed computing environment. The protocol guarantees concurrency atomicity with a maximum of m-1 message passes among the m server nodes of the system. Under one embodiment of the protocol, an access component message is transferred to the server nodes storing data to be accessed. The first server node of the plurality generates a token to be passed among the accessed nodes. A node can not process its request until it receives the token. A node may pass the token immediately upon ensuring that it is the current expected token.
Inventors
- 👤 Sandra Johnson Baylor
- 👤 Peter Frank Corbett
- 👤 Dror Gershon Feitelson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 09:47
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L9/00; H04L9/40; H04L12/1881; H04L67/00; H04L67/01; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/959; Y10S707/99931; Y10S707/99932; Y10S707/99938; Y10S707/99951; Y10S707/99952
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
124 words
A method for achieving atomic multicasting in a computer having a plurality of system nodes, comprising: sending a first message from a first node to a first plurality of nodes that will receive the multicast message; in a logical first of the first plurality of nodes that receive the message: generating a token; delivering the first message to an application; and passing the token to a next system node; in each node that is not the logical first of the first plurality of nodes that receive the message, delivering the first message to the application after such node has received the token, and if it is not the logical last of the first plurality of nodes, passing the token to a next system node.
Claim 2
Independent Claim
124 words
A method for achieving atomic multicasting in a computer having a plurality of system nodes, comprising: sending a first message from a first node to a first plurality of nodes that will receive the multicast message; in a logical first of the first plurality of nodes that receive the message: generating a token; delivering the first message to an application; and passing the token to a next system node; in each node that is not the logical first of the first plurality of nodes that receive the message, delivering the first message to the application after such node has received the token, and if it is not the logical last of the first plurality of nodes, passing the token to a next system node.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein the next system node is a next sequential node in a canonical ordering of the system nodes.
Claim 4
Dependent Claim
20 words
The method of claim 2, wherein the first plurality of nodes is a subset of the plurality of system nodes.
Claim 5
Dependent Claim
30 words
The method of claim 1, wherein the system is a client-server system, and wherein the first node is a client node and the first plurality of nodes are server nodes.
Claim 6
Dependent Claim
22 words
The method of claim 1, wherein the multicast message is a service request from a client to a plurality of server nodes.
Claim 7
Independent Claim
128 words
A method for processing data accesses of a plurality of system servers in a parallel computer file system, comprising: sending a first data request from a first requesting client to a first plurality of servers storing data to be accessed; in a logical first of the plurality of servers storing the data to be accessed, generating a token, processing the first request and sending the token to a logically adjacent server; in each server that is not the logical first of the plurality of servers storing the data to be accessed, processing the first request after such server has received the token, and if it is not the logical last of the plurality of servers storing data to be accessed, passing the token to a logically adjacent server.
Claim 8
Independent Claim
128 words
A method for processing data accesses of a plurality of system servers in a parallel computer file system, comprising: sending a first data request from a first requesting client to a first plurality of servers storing data to be accessed; in a logical first of the plurality of servers storing the data to be accessed, generating a token, processing the first request and sending the token to a logically adjacent server; in each server that is not the logical first of the plurality of servers storing the data to be accessed, processing the first request after such server has received the token, and if it is not the logical last of the plurality of servers storing data to be accessed, passing the token to a logically adjacent server.
Claim 9
Dependent Claim
27 words
The method of claim 6, wherein a logically adjacent server is defined as a next sequential server in a canonical ordering of the plurality of system servers.
Claim 10
Dependent Claim
129 words
The method of claim 6, further comprising: sending a second data request from a second requesting client to a second plurality of servers storing data to be accessed; in a logical first of the second plurality of servers storing the data to be accessed, generating a second token, processing the second request and sending the second token to a logically adjacent server; in each server that is not the logical first of the second plurality of servers storing the data to be accessed, processing the second request only after such server has both received the second token and processed all prior requests, and if it is not the logical last of the second plurality of servers storing data to be accessed, passing the token to a logically adjacent server.
Claim 11
Dependent Claim
24 words
The method of claim 8, wherein the first plurality of servers and the second plurality of servers have one or more servers in common.
Claim 12
Dependent Claim
19 words
The method of claim 9, wherein the first and second data requests have one or more data in common.
Claim 13
Dependent Claim
19 words
The method of claim 9, wherein the data to be accessed by the first and second requests are identical.
Claim 14
Dependent Claim
15 words
The method of claim 8, wherein the first and second clients are the same client.
Claim 15
Dependent Claim
14 words
The method of claim 8, wherein the first and second clients are different clients.
Claim 16
Dependent Claim
58 words
The method of claim 6, wherein the first data request comprises an access component message sent to each server storing data to be accessed, the access component message containing a data request message and an identification of a next subsequent server in the plurality of servers receiving an access component message as part of the first data request.
Claim 17
Dependent Claim
25 words
The method of claim 14, wherein the first data request message further comprises an identification of the first requesting client and an access sequence number.
Claim 18
Dependent Claim
50 words
The method of claim 14, wherein the first data request message further comprises an indication of whether the server receiving it is the logical first of the plurality of servers storing data to be accessed as part of the first request, or the logical last of the plurality of servers.
Claim 19
Dependent Claim
46 words
The method of claim 6, wherein each token comprises a token counter representing the number of tokens passed by the preceding server, a request identifier identifying the request with which the token is associated, and the address of the next server to receive a request message.
Claim 20
Dependent Claim
96 words
The method of claim 17, wherein the step of processing the second request only after such server has both received the second token and processed all previous requests, comprises: receiving a token; storing the token in a token queue; comparing the token with a token in-counter; incrementing the token in-counter when the token matches the token in-counter; comparing the request identifier of the token with the request identifier of the received requests; when the token matches one of the received requests, relaying the token to the next node, incrementing the token out-counter and performing the request.
Claim 21
Dependent Claim
22 words
The method of claim 18, further comprising maintaining a count in each server of the number of tokens sent by that server.
Claim 22
Dependent Claim
54 words
The method of claim 18, wherein the step of passing the token to another server comprises writing in the token the address of the server to the next server to receive a request component, sending the token to that address and incrementing the count of the number of tokens sent by the sending server.
Claim 23
Dependent Claim
26 words
The method of claim 6, wherein the first access component message identifies each server in the plurality of servers that will receive the first data request.
Claim 24
Dependent Claim
29 words
The method of claim 21, wherein the first access component message identifies each server that will receive the first data request by means of a list of such servers.
Claim 25
Dependent Claim
31 words
The method of claim 21, wherein the first access component message identifies each server that will receive the first data request by providing an identifier of a predetermined configuration of servers.
Claim 26
Dependent Claim
39 words
The method of claim 21, wherein the first access component message identifies each server that will receive the first data request by providing a bit map in which each bit corresponds to a server in a system of servers.
Claim 27
Dependent Claim
45 words
The method of claim 7, wherein the logical last server sends an acknowledgement message to the client after matching the first access request to a token, and wherein the client is prevented from sending the second access request until it has received the acknowledgement message.
Claim 28
Dependent Claim
29 words
The method of claim 6, wherein the request from the first requesting client comprises a plurality of access component messages sent to each of the first plurality of servers.
Claim 29
Dependent Claim
29 words
The method of claim 18, wherein the request from the first requesting client comprises a plurality of access component messages sent to each of the first plurality of servers.
Claim 30
Dependent Claim
51 words
The method of claim 27, wherein each access component message contains a field specifying the total number of access component messages of that request that are destined for that node, and wherein the token is held at that node until it is successfully matched with that number of access component messages.
Claim 31
Dependent Claim
112 words
The method of claim 6, further comprising: sending a second data request from a second requesting client to one server of a second plurality of servers storing data to be accessed; generating a second token in the one server of the second plurality, processing the second request and sending the second token to a logically adjacent of the second plurality of servers; in each of the other servers in the second plurality of servers, processing the second request after such server has received the second token, and if it is not the logical last of the second plurality of servers, passing the token to a logically adjacent of the plurality of servers.
Claim 32
Independent Claim
122 words
A method for processing data accesses of a plurality of servers in a parallel computing system, comprising: sending a first data request from a first requesting client to one server of a plurality of servers storing data to be accessed; generating a token in the one server, processing the first request and sending the token to a logically adjacent of the plurality of servers; in each of the other servers in the first plurality of servers storing the data to be accessed, processing the first request after such server has received the token, and if it is not the logical last of the plurality of servers storing data to be accessed, passing the token a logically adjacent of the plurality of servers.
Claim 33
Independent Claim
122 words
A method for processing data accesses of a plurality of servers in a parallel computing system, comprising: sending a first data request from a first requesting client to one server of a plurality of servers storing data to be accessed; generating a token in the one server, processing the first request and sending the token to a logically adjacent of the plurality of servers; in each of the other servers in the first plurality of servers storing the data to be accessed, processing the first request after such server has received the token, and if it is not the logical last of the plurality of servers storing data to be accessed, passing the token a logically adjacent of the plurality of servers.
Claim 34
Dependent Claim
123 words
The method of claim 30, further comprising: sending a second data request from a second requesting client to one of a second plurality of servers storing data to be accessed; generating a second token in the one server of the second plurality, processing the second request and sending the second token to another of the plurality of servers; in each of the other servers in the second plurality of servers storing the data to be accessed, processing the second request only after such server has both received the second token and processed all prior requests, and if such server is not the logical last of the second plurality of servers storing data to be accessed, passing the token to a logically adjacent server.
Claim 35
Dependent Claim
18 words
The method of claim 31, further comprising designating a pair of servers between which no token can pass.
Claim 36
Independent Claim
134 words
A system for achieving atomic multicasting in a computer having a plurality of system nodes, comprising: means for sending a first message from a first node to a first plurality of nodes that will receive the multicast message; means in a logical first of the first plurality of nodes that receive the multicast message: for generating a token; for delivering the first message to an application; and for passing the token to a next system node; means in each node that is not the logical first of the first plurality of nodes that receive the message, for delivering the first message to the application after such node has received the token, and if it is not the logical last of the first plurality of nodes, for passing the token to a next system node.
Claim 37
Independent Claim
134 words
A system for achieving atomic multicasting in a computer having a plurality of system nodes, comprising: means for sending a first message from a first node to a first plurality of nodes that will receive the multicast message; means in a logical first of the first plurality of nodes that receive the multicast message: for generating a token; for delivering the first message to an application; and for passing the token to a next system node; means in each node that is not the logical first of the first plurality of nodes that receive the message, for delivering the first message to the application after such node has received the token, and if it is not the logical last of the first plurality of nodes, for passing the token to a next system node.
References Cited (Backward Citations)
US5452445A
Cited
US5434994A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-20 | 2001-10-20 | 2002-04-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-20 | 2005-10-20 | 2006-04-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-20 | 2009-10-20 | 2010-04-21 | $7700.00 | Window Closed / Lapsed |