Method and apparatus for scalable peer-to-peer inquiries in a network of untrusted parties

• US 7,325,034 B2
• Filed: 09/24/2003
• Issued: 01/29/2008
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Jania, Frank L., Tracey, John Michael, Douglis, Frederick, LaVoie, Jason D.
• Primary Examiner(s): Winder; Patrice
• Assistant Examiner(s): MOUZON, LAJUANIA N
• Application Number:
  US10/670,138
• Publication Number:
  US 20050065632A1
• Time in Patent Office: 1,588 Days
• Field of Search: None
• US Class Current: 709/205
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and apparatus for scalable inquiries in a network of communicating peers are provided. The method and apparatus of the present invention make use of communal filters and randomization to determine which client devices will output a message that is to be broadcast to a community of client devices. Each message is assigned a probability value that is determined based on various criteria or may be determined randomly. The message is then transmitted to the client devices who apply their own respective display criteria to the message parameters to determine if the message is one that is of interest to the user of the client device. If the message is not of interest to the user of the client device, the message is discarded. If the message is of interest to the user, logic is applied to the parameters of the message to determine whether the message should be displayed to the user or not. This logic may involve determining whether the message has been previously displayed to the user, whether the message has been received but not previously displayed, and the like. In addition, if the message has not been previously displayed to the user, a randomly generated number, which may be weighted based on other criteria, is generated and compared with the probability value associated with the message. Based on this comparison, the message is either displayed or not displayed on the client device. This probability value of the message may be adjusted with each subsequent rebroadcast of the message to increase the size of the subset of users that will see the message.

Claims

1. A method of scaling communication messages in a network of data processing systems, each one of the data processing systems capable of transmitting alert messages to any other one of the data processing systems, the method comprising:

transmitting an alert message, which requests a reply, from a source one of the data processing systems to a plurality of recipient ones of the data processing systems, the alert message being received by the plurality of recipient ones of the data processing systems;

outputting the alert message by only a first subset of the plurality of recipient ones of the data processing systems, the first subset being fewer than all of the plurality of recipient ones of the data processing systems;

receiving, by the source one of the data processing systems, reply messages transmitted from at least some of the first subset of the plurality of recipient ones of the data processing systems in response to a receipt of the alert message;

determining, by the source one of the data processing systems, if a predetermined number of reply messages has been received from the at least some of the first subset of the plurality of recipient ones of the data processing systems;

in response to determining that the predetermined number of reply messages has not been received, retransmitting the alert message to the plurality of recipient ones of the data processing systems, the retransmitted alert message being received by the plurality of recipient ones of the data processing systems;

outputting the retransmitted alert message by a second subset of the plurality of recipient ones of the data processing systems;

assigning a probability to the alert message; and

determining, by each of the plurality of recipient ones of the data processing systems, whether to output the alert message based on the probability assigned to the alert message.

2. The method of claim 1, further comprising:

assigning a second probability to the retransmission of the alert message; and

determining, by each of the plurality of recipient ones of the data processing systems, whether to output the retransmission of the alert message based on the second probability assigned to the retransmission of the alert message.

3. The method of claim 1, wherein the alert message is one of an instant message and an electronic mail message.

4. The method of claim 1, wherein the alert message is one of a PollCast and a SkillTap message.

5. The method of claim 1, further comprising within each recipient device:

storing the alert message in a storage device;

determining if a predetermined amount of time has elapsed since a previous determination was made about whether to output the alert message;

determining whether to output the alert message based on output criteria; and

outputting the alert message if the output criteria is satisfied.

6. The method of claim 1, further comprising:

each of the plurality of recipient ones of the data processing systems determining whether to output the alert message by generating a randomized value and comparing the randomized value to the probability.

7. The method according to claim 1, further comprising the probability being determined using a random number generator.

8. The method according to claim 1, further comprising the probability being based on a total number of the plurality of recipient ones of the data processing systems.

9. The method according to claim 1, further comprising increasing the probability when the alert message is retransmitted.

10. A system for scaling communication messages in a network of communicating peer data processing systems, each one of the data processing systems capable of transmitting alert messages to any other of the data processing systems, comprising:

a source one of the data processing systems transmitting an alert message, which requests a reply, to a plurality of recipient ones of the data processing systems, the alert message being received by the plurality of recipient ones of the data processing systems;

only a first subset of the plurality of recipient ones of the data processing systems outputting the alert message, the first subset being fewer than all of the plurality of recipient ones of the data processing systems;

the source one of the data processing systems receiving reply messages transmitted from at least some of the first subset of the plurality of recipient ones of the data processing systems in response to a receipt of the alert message;

the source one of the data processing systems determining if a predetermined number of reply messages has been received from the at least some of the first subset of the plurality of recipient ones of the data processing systems;

in response to determining that the predetermined number of reply messages has not been received, the source one of the data processing systems retransmitting the alert message to the plurality of recipient ones of the data processing systems, the retransmitted alert message being received by the plurality of recipient ones of the data processing systems;

a second subset of the plurality of recipient ones of the data processing systems outputting the retransmitted alert message; and

wherein the source one of the data processing systems server assigns a probability to the alert message, and wherein each of the plurality of recipient ones of the data processing systems determines whether to output the alert message based on the probability assigned to the alert message.

11. The system of claim 10, wherein the source one of the data processing systems assigns a second probability to the retransmission of the alert message;

and determines whether to output the retransmission of the alert message based on the second probability assigned to the retransmission of the alert message.

12. The system of claim 10, wherein the alert message is one of an instant message and an electronic mail message.

13. The system of claim 10, wherein the alert message is one of a PollCast and a SkillTap message.

14. The system of claim 10, wherein each recipient one of the data processing systems stores the alert message in a temporary storage, determines if a predetermined amount of time has elapsed since a previous determination was made about whether to output the alert message, determines whether to output the alert message based on output criteria, and outputs the alert message if the output criteria is satisfied.

15. A method of distributing messages to a plurality of client devices in a network, comprising:

receiving a message for broadcast to a plurality of client devices;

assigning a probability value to the message;

transmitting the message to the plurality of client devices;

at each client device, generating a randomized value;

comparing the randomized value of a client device to the probability value of the message; and

outputting the message based on the comparison of randomized value and the probability value.