Boots – shoes – and leggings
Patent
1983-04-13
1986-02-04
Zache, Raulfe B.
Boots, shoes, and leggings
G06F 300
Patent
active
045690154
DESCRIPTION:
BRIEF SUMMARY
TECHNICAL FIELD
This invention relates to a network whose processor nodes exchange information in synchronized phases, and more particularly to methods for achieving agreement among the processors, either to execute a task distributed among them, or not at all, even in the presence of detected faulty processors.
BACKGROUND
It is well appreciated that a computation may consist of concurrently executing tasks distributed over a network of CPUs. Indeed, Hodgkinson, U.S. Pat. No. 4,274,139, entitled "Digital Telecommunications Network Having Improved Data Processing Systems", issued on June 16, 1981, describes a system in which a local CPU executing one task ships another function to another CPU for remote execution, and accepts the output results from the remotely processed task. Likewise, Yost, in copending application Ser. No. 06/459,746, filed on Jan. 21, 1983, entitled "Controlling Multiple Distributed Computations in a Multi CPU Environment from a Single Port", discloses a method for dialoging with distributed concurrently executing tasks of a computation through a single physical port. Among the facilities utilized are those permitting a pass-through, that is, allowing users at one site to log on to a CPU at another, and the transferring of files.
A computation may consist of a number of concurrently executing tasks involving accessing, modifying, and restoring information, either locally or at remotely networked CPUs. This may require coordination, simultaneity of action, or similarity of end effects or results. Examples are diverse such as the debit/credit of distributed accounts by the same amount, or using the same starting clock values. The common attribute of interest is that multiple asynchronous processors use and rely upon an information value originated by one of their number. The quest is to determine whether the value received was the original one sent. Two classes of protocols have been devised to treat this problem. These are respectively, multi-phase commit/abort protocols, and Byzantine Agreements.
Both commit/abort protocols and Byzantine Agreements involve the synchronized phase exchange of messages among the networked CPU's (nodes) and their evaluations at the respective nodes for the purpose of eventually guaranteeing uniform commitment of transactions at all nodes visited by a transaction. There are differences in emphasis among protocol types. For example, Byzantine Agreement assumes that each active node knows the identity of all of the other active nodes in the network, and that there is a direct coupling therebetween. Further, Byzantine Agreement tries to converge agreement within a fixed period of time at a high message overhead. In contrast, multiphase commit protocols, as described by Gray, "Operating Systems, An Advanced Course", Springer Verlag, 1978, focuses on a hierarchy of tasks in which awareness of nodes by any individual node is limited to immediate subordinates.
Multiphase commit protocols can tolerate many lost messages. They cannot, however, tolerate even single instances of failure of the coordinating processor node. This node selectively sends a "commit" to some networked processors and "abort" the transaction to others. In contrast, Byzantine protocols require more messages on the average, and tolerate a limited number of node/link failures, but the failures can be of a variety of types. Thus, when the object of the protocol is to secure guaranteed broadcast, the tradeoff is between message overhead, and reliability of the guarantees.
Also, Skeen, "Non-Blocking Commit Protocols", ACM SIGMOD Conference, 1981, at pp133-142, describes multiphase commit protocols to reduce blocking possibility in the event of failure. Where the computational objective is the concurrent updating of a replicated database, it can be shown that the message traffic between the classes of protocols is of the same magnitude.
Pease et al, "Reaching Agreement in the Presence of Faults", 27 Journal of the ACM, pp228-34, April 1980, defines Byzantine Agreement as a method for achieving co
REFERENCES:
patent: 4030072 (1977-06-01), Bjornsson
patent: 4174536 (1979-11-01), Misunas et al.
patent: 4276594 (1981-06-01), Morley
patent: 4325120 (1982-04-01), Colley et al.
patent: 4354225 (1982-10-01), Frieder et al.
patent: 4418384 (1983-11-01), Holtey et al.
Dolev Danny
Strong Hovey R.
Brodie R. Bruce
Eng David Y.
International Business Machines - Corporation
Zache Raulfe B.
LandOfFree
Method for achieving multiple processor agreement optimized for does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for achieving multiple processor agreement optimized for , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for achieving multiple processor agreement optimized for will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2344727