US6327630B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ordered message reception in a distributed data processing system
Assignee: Hewlett Packard Development Co LP
•
Filing: 1997-07-24
•
Granted: 2001-12-04
•
Expires: 2017-07-24
Abstract
Abstract A complex computing system has a plurality of nodes interconnected by channels through which data messages are exchanged. The underlying principle is that after arrival at a node of a message, delivery of that message is delayed until after delivery and consequences of all more senior messages which affect the node. The messages are progressively timestamped at each node so that each time stamp contains generation by generation indicators of the origin of the associated message. The seniority of that message is uniquely determined thereby and total ordering of the messages can be achieved. When comparing timestamps for such ordering, comparison of respective generation indicators is necessary only until there is a distinction.
Inventors
- 👤 Jeremy John Carroll
- 👤 Andrei Vladilenovich Borshchev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 04:52
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/54; G06F9/542; G06F9/546; G06F2209/00; G06F2209/54; G06F2209/546
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
130 words
A complex computing system comprising: a plurality of nodes connected to each other by channels along which time stamped data messages are sent and received, each timestamp being indicative, generation by generation, of its seniority acquired through its ancestors' arrival in the system and in any upstream nodezs, and each node including: means for storing each input data message, means for determining the seniority of input data messages by progressive comparison of respective generations in the timestamups until a first distinction exists, means for delivering the input data messages for processing, means for applying a timestamp to each output message derived from such processing comprising an immediately ancestral message's timestamp augmented by a new generation seniority indicator consistent with the ordering, and means for outputting such ordered and timestamped messages.
Claim 2
Dependent Claim
130 words
A complex computing system comprising: a plurality of nodes connected to each other by channels along which time stamped data messages are sent and received, each timestamp being indicative, generation by generation, of its seniority acquired through its ancestors' arrival in the system and in any upstream nodezs, and each node including: means for storing each input data message, means for determining the seniority of input data messages by progressive comparison of respective generations in the timestamups until a first distinction exists, means for delivering the input data messages for processing, means for applying a timestamp to each output message derived from such processing comprising an immediately ancestral message's timestamp augmented by a new generation seniority indicator consistent with the ordering, and means for outputting such ordered and timestamped messages.
Claim 3
Dependent Claim
32 words
A complex computing system as claimed in claim 1 , wherein the means for delivering is arranged to deliver messages in order according to which message has the most senior timestamp indicator.
Claim 4
Dependent Claim
39 words
A complex computing system as claimed in claim 1 , wherein for a data message received from outside the system, an initial timestamp indicator includes an indication of a time of receipt of said data message at the node.
Claim 5
Dependent Claim
50 words
A complex computing system as claimed in claim 1 , wherein for a data message generated by a node of the system, a new generation seniority indicator of the timestamp includes an indication of the place of said data message in the ordered sequence of such messages at said node.
Claim 6
Dependent Claim
23 words
A complex computing system as claimed in claim 1 , wherein monotonic integers are utilized as said generation seniority indicators in the timestamps.
Claim 7
Dependent Claim
35 words
A complex computing system as claimed in claim 1 , wherein the means for delivering of a node delivers data messages only once a message has been received on each input channel of said node.
Claim 8
Dependent Claim
42 words
A complex computing system as claimed in claim 1 , wherein the means for delivering of a node delivers data messages only when at least one data message received on each input channel of said node is stored in the storage means.
Claim 9
Dependent Claim
31 words
A complex computing system as claimed in claim 6 , wherein each node is adapted to perform at least one channel flushing routine triggerable by lack or paucity of channel traffic.
Claim 10
Dependent Claim
49 words
A complex computing system as claimed in claim 1 , wherein all data messages caused by a first data message anywhere in the system are delivered to a node before any messages caused by a second data message, junior to the first data message, are delivered to said node.
Claim 11
Independent Claim
130 words
A method of ordering data messages within a complex computing system comprising a plurality of nodes connected to each other by channels along which data messages are sent and received, the method comprising, for each node, timestamping each message on arrival, queuing messages until a message has been received on each input channel to the node, and delivering the queued messages for processing sequentially in accordance with their timestamps, the message having a most senior timestamp being delivered first, wherein timestamping at each node is cumulative so that a timestamp of a particular message indicates a seniority acquired by that message, generation by generation, and wherein the seniority of one message against another is determined by a progressive comparison of respective generations in the timestamps until a first distinction exists.
Claim 12
Independent Claim
130 words
A method of ordering data messages within a complex computing system comprising a plurality of nodes connected to each other by channels along which data messages are sent and received, the method comprising, for each node, timestamping each message on arrival, queuing messages until a message has been received on each input channel to the node, and delivering the queued messages for processing sequentially in accordance with their timestamps, the message having a most senior timestamp being delivered first, wherein timestamping at each node is cumulative so that a timestamp of a particular message indicates a seniority acquired by that message, generation by generation, and wherein the seniority of one message against another is determined by a progressive comparison of respective generations in the timestamps until a first distinction exists.
Claim 13
Dependent Claim
29 words
A complex computing system as claimed in claim 1 , wherein the system is either a distributed computing system, a symmetric multi-processor computer, or a massively parallel processor computer.
References Cited (Backward Citations)
US4725834A
Cited
US4930124A
Cited
US4952930A
Cited
US5544316A
Cited
US5396613A
Cited
US5664190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-03 | 2005-06-04 | 2005-12-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-03 | 2009-06-04 | 2009-12-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-03 | 2013-06-04 | 2013-12-04 | $7700.00 | Window Closed / Lapsed |