EP0178473A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for broadcasting of information in a distributed computing network
Assignee: International Business Machines Corp
•
Filing: 1985-09-17
•
Granted: —
•
Expires: 2005-09-17
Abstract
Abstract A method for reliably broadcasting information in a point-to-point network of processors in the presence of component faults provided that the network remains connected using only an exchange of messages. The method possesses the properties (1) that every message broadcast by a fault-free processor is accepted exactly once by all fault-free processors within a bounded time, (2) that every message broadcast is either accepted by all fault-free processors or none of them, and (3) that all messages accepted by fault-free processors are accepted in the same order by all those processors. The method is based on a diffusion technique for broadcasting information and on special message validity test for tolerating any number of component failures up to network partitioning or successful forgery.
Inventors
- 👤 Houtan Aghili
- 👤 Flaviu Ilie Cristian
- 👤 Hovey Raymond Strong
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 16:10
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381; G06F11/00
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
261 words
A method for reliably broadcasting information in a point-to-point network of message exchanging processors, each processor having an amendable log, each processor having a clock approximately synchronized to the clocks of the other processors, the time taken for the transmission of messages between arbitrary points in the network and processing thereof being bounded, comprising the steps of: (a) responsive to a message broadcast request originating at any processor s, formatting a message M and assigning thereto a network unique identifier and a timestamp; adding message M to the processor s's log; signing message M including the assigned values to form message X; and broadcasting message X to network adjacent processors of processor s; (b) responsive to the receipt of a signed message X by each processor p from a network adjacent processor s, verifying its authenticity and deriving from it the original message M and a sequence of signatures of all previous processors that have signed X in the order that they have signed X with the sender's signature being the first signature; and ascertaining the validity of message M; and (c) at each processor q within the set of processors network adjacent to processor s which finds the message M valid, performing the further steps of appending message M to its log; signing the message X; broadcasting said signed message X to its network adjacent neighbors except the processor from whom the message X was received; and, after a predetermined amount of time from the time of message origination, accepting the message M if it is determined to be valid.
Claim 2
Independent Claim
261 words
A method for reliably broadcasting information in a point-to-point network of message exchanging processors, each processor having an amendable log, each processor having a clock approximately synchronized to the clocks of the other processors, the time taken for the transmission of messages between arbitrary points in the network and processing thereof being bounded, comprising the steps of: (a) responsive to a message broadcast request originating at any processor s, formatting a message M and assigning thereto a network unique identifier and a timestamp; adding message M to the processor s's log; signing message M including the assigned values to form message X; and broadcasting message X to network adjacent processors of processor s; (b) responsive to the receipt of a signed message X by each processor p from a network adjacent processor s, verifying its authenticity and deriving from it the original message M and a sequence of signatures of all previous processors that have signed X in the order that they have signed X with the sender's signature being the first signature; and ascertaining the validity of message M; and (c) at each processor q within the set of processors network adjacent to processor s which finds the message M valid, performing the further steps of appending message M to its log; signing the message X; broadcasting said signed message X to its network adjacent neighbors except the processor from whom the message X was received; and, after a predetermined amount of time from the time of message origination, accepting the message M if it is determined to be valid.
Claim 3
Dependent Claim
52 words
A method according to claim 1, wherein the step of ascertaining message validity includes the steps of determining whether the message is authentic, whether it has not already been signed by processor p, whether it contains duplicate signatures, whether it is nonduplicative of a previously received message, and whether it is timely.
Claim 4
Dependent Claim
45 words
A method according to claim 1, wherein said message M has further assigned to it a counter initialized to 1, whereby each processor q within the set of network adjacent processors, which finds the message M valid, performs the incrementing of said counter by I.
Claim 5
Dependent Claim
22 words
A method according to claim 1, in which every message broadcast is either accepted by all fault-free processors or none of them.
Claim 6
Dependent Claim
25 words
A method according to claim 1, in which all message broadcasts accepted by fault-free processors are accepted in the same order by all of them.
Claim 7
Dependent Claim
162 words
A method according to claim 1 comprising the steps of: (a) responsive to a message broadcast request local to any processor s, formatting and assigning to a message a network unique identifier; accepting the message; appending the message to its log; and broadcasting the message including the assigned identifier to the processor network adjacent thereto; (b) responsive to the receipt of a broadcast message at each processor p from a network adjacent processor s, ascertaining message validity as to its being nonduplicative of a previously received message; and (c) at each processor q within the set of processors p which finds the message valid, performing the further steps of: (1) accepting the message; (2) updating its message log by appending the received message thereto; (3) broadcasting the message to its network adjacent processors except the processor from whom the message was received; and (4) after a predetermined amount of time from the time of message origination, erasing that message from the log.
Claim 8
Dependent Claim
15 words
A method according to claim 6, wherein different processors may accept messages in different order.
Claim 9
Dependent Claim
21 words
A method according to claim 6, wherein every message broadcast is either accepted by all fault-free processors or none of them.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.