Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-04-05
2001-12-04
Teska, Kevin J. (Department: 2123)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S207000, C370S412000
Reexamination Certificate
active
06327630
ABSTRACT:
This invention relates to complex computing systems. It was developed primarily to answer a problem with distributed systems, but it has been realised that it is equally applicable to systems which, are not normally considered to be distributed, such as a multi-processor computer. Although their physical separation may be negligible, nonetheless the processors are distinct and form a “distributed” system within the computer to which this invention is applicable.
A landmark paper on distributed systems is that of Lamport (“Time, Clocks and the Ordering of Events in a Distributed System”—Communications of the ACM Vol. 21 No. 7, 1978 pp 558-565). In that, a distributed system is defined as a collection of distinct processes which are spatially separated and which communicate with one another by exchanging messages, and in which the message transmission delay is not negligible compared to the time between events in a single process. In such a system, it is sometimes impossible to say that one of two events occurred first, Lamport proposed a logical clock to achieve a partial ordering of all the events, and he postulated a single integer timestamp on each message, corresponding to the time the message was sent.
Fridge (in “Logical Time in Distributed Computing Systems”—IEEE Computer 24(8) August 1991 pp 28-33) argued that the time stamps of Lamport clocks (totally ordered logical clocks) impose on unrelated concurrent events an arbitrary ordering, so that the observer cannot distinguish from genuine causal relationships. He proposed partially ordered time readings and timestamping rules which enable a causal relationship between two events to be established. Their order could then be determined. But where there is no causal relationship between events, no definitive order exists, and different total orderings of events (or interleavings) are possible. This means that some messages are assigned an arbitrary order.
This ordering problem is known as the “race condition problem” and it can be illustrated by a simple analogy. A dictates a first message to secretary B, who faxes the typed version to C. A telephones C with a second message. Unless ordered, the communication system will not know whether the first or second message reached C first, although it will know that the dictation preceded the fax.
It is the aim of this invention to resolve this problem and to allow someone to programme a distributed system as if he was programming a uni-processor. In other words, he can think about time linearly and he will not have to be concerned about concurrency or the race condition problem.
According to one aspect of the present invention there is provided a complex computing system comprising a plurality of nodes connected to each other by channels along which timestamped 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 nodes, and each node comprising: means; for storing each input data message, means for determining the seniority of input data messages by progressive comparison of respective generations in the timestamps until the first distinction exists, means for delivering these messages for processing, means for applying a timestamp to each output message derived from such processing comprising the 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.
The delivery means will generally be arranged to deliver messages in order according to which message has the most senior timestamp indicator.
For a data message received from outside the system the initial timestamp indicator will preferably include an indication of the time of receipt of said data message at the node, while for a data message generated by a node of the system the new generation seniority indicator of the timestamp will preferably include an indication of the place of said data message in the ordered sequence of such messages at said node. This indication may be real time or logical time.
Conveniently, monotonic integers are utilised as said generation seniority indicators in the timestamps.
Advantageously, the delivery means of a node delivers data messages only either once a message has been received on each of the input channels of said node or when at least one data message received on each of the input channels of said node is stored in the storage means.
Preferably each node will be adapted to perform at least one channel flushing routine triggerable by lack or paucity of channel traffic.
Ideally, all data messages caused by a first data message anywhere in the system will be delivered to a node before any messages caused by a second data message, junior to the first data message, are delivered to said node.
According to another aspect of the present invention there is provided 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 the most senior timestamp being delivered first, wherein the timestamping at each node is cumulative so that the timestamp of a particular message indicates the seniority acquired by that message, generation by generation, and wherein the seniority of one message against another is determined by the progressive comparison of respective generations in the timestamps until the first distinction exists.
According to a further aspect of the present invention there is provided a complex computing system comprising a plurality of nodes between which data messages are exchanged, wherein after the arrival at a node of a message, delivery of the message by the node is delayed until after the delivery and consequences of all more senior messages which affect the node.
Such a system may be either a distributed computing system, a symmetric multi-processor computer, or a massively parallel processor computer.
Assumiptions
To understand later explanations, certain assumptions about a distributed computing system will be set out.
Such a system is a set of nodes or processes connected by FIFO (first in, first out) channels. Conventionally, ‘nodes’ refer to the hardware and ‘processes’ to the software and operations performed at the nodes, but the terms may be used interchangeably here. Some of these processes have external channels through which they communicate with the system's environment, the whole system being driven by input messages through some external channels, and sending out an arbitrary number of consequential output messages through other external channels.
Each process can be regarded as an application layer and a presentation layer, which handle the following events:
(a) Message arrival (at the presentation layer)
(b) Message delivery (from presentation to application layer)
(c) Message send request (from application to presentation layer)
(d) Message send (from presentation layer)
(e) Message processing complete (from application to presentation layer).
At any event (b), the application layer
i) generates one or more events (c)
ii) changes the process state, and
iii) generates event (e)—which indicates that it is ready to receive a further message.
A set of such events will be termed a message handler invocation. Such invocations are the basic building blocks or atomic units of a distributed system, and a process history is a sequence of such invocations. Each invocation may affect subsequent invocations by changing the internal state of the process.
At the application layer, the channels are simplex. However, auxiliary messages, from one presentation layer to the other, are allowed in both directions.
The
Borshchev Andrei Vladilenovich
Carroll Jeremy John
Hewlett--Packard Company
Teska Kevin J.
Thomson William
LandOfFree
Ordered message reception in a distributed data processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ordered message reception in a distributed data processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ordered message reception in a distributed data processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599546