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

• US 20050065632A1
• Filed: 09/24/2003
• Published: 03/24/2005
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Tracey, John Michael, Jania, Frank L., Douglis, Frederick, Lavoie, Jason D.
• Granted Patent: US 7,325,034 B2
• Time in Patent Office: Days
• US Class Current: 700/200
• 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, in a data processing system, of outputting a communication from a single source to a plurality of recipient devices, comprising:

transmitting the communication to the plurality of recipient devices such that the communication is received by the plurality of recipient devices but is output by only a first subset of the plurality of recipient devices, wherein the first subset is less than all of the plurality of recipient devices;

receiving responses from at least some of the first subset of the plurality of recipient devices;

determining if a predetermined response requirement is met by the responses received from the at least some of the first subset of the plurality of recipient devices; and

outputting the communication on a second subset of the plurality of recipient devices if the predetermined response requirement has not been met by the responses received from the at least some of the first subset of the plurality of recipient devices.

2. The method of claim 1, wherein transmitting the communication to the plurality of recipient devices includes assigning a probability to the communication, and wherein each of the plurality of recipient devices determines whether to output the communication based on the probability assigned to the communication.

3. The method of claim 1, wherein outputting the communication on a second subset of the plurality of recipient devices includes retransmitting the communication to the plurality of recipient devices such that the second subset of the plurality of recipient devices outputs the communication.

4. The method of claim 3, wherein transmitting the communication to the plurality of recipient devices includes assigning a probability to the communication and each of the plurality of recipient devices determines whether to output the communication based on the probability assigned to the communication, and wherein retransmitting the communication to the plurality of recipient devices includes retransmitting the communication with a different probability than the probability that was assigned to the communication.

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

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

7. The method of claim 1, wherein outputting the communication on a second subset of the plurality of recipient devices includes, within each recipient device:

storing the communication in a storage;

determining if a predetermined amount of time has elapsed since a previous determination whether to output the communication has been made;

determining whether to output the communication based on output criteria; and

outputting the communication if the output criteria is satisfied.

8. The method of claim 1, wherein transmitting the communication to the plurality of recipient devices includes comparing, for each recipient device in the plurality of recipient devices, a bit mask to identifiers of the recipient devices, wherein the first subset of the plurality of recipient devices includes recipient devices that are determined to be recipient devices that are to output the communication based on the comparison of the bit mask to the identifiers of the recipient devices.

9. The method of claim 8, wherein outputting the communication on a second subset of the plurality of recipient devices includes:

shifting the bit mask; and

comparing the shifted bit mask to the identifiers of the recipient devices to identify the second subset of the plurality of recipient devices.

10. The method of claim 2, wherein each of the plurality of recipient devices determines whether to output the communication based on the probability by generating a randomized value and comparing the randomized value to the probability to determine whether to output the communication.

11. A system for outputting a communication from a single source to a plurality of recipient devices, comprising:

at least one network;

a communications server coupled to the at least one network; and

a plurality of recipient devices coupled to the at least one network, wherein the communications server transmits the communication to the plurality of recipient devices such that the communication is received by the plurality of recipient devices but is output by only a first subset of the plurality of recipient devices, wherein the first subset is less than all of the plurality of recipient devices, receives responses from at least some of the first subset of the plurality of recipient devices, determines if a predetermined response requirement is met by the responses received from the at least some of the first subset of the plurality of recipient devices, and wherein, if the predetermined response requirement has not been met by the responses received from the at least some of the first subset of the plurality of recipient devices, the communication is output on a second subset of the plurality of recipient devices.

12. The system of claim 11, wherein the communications server assigns a probability to the communication, and wherein each of the plurality of recipient devices determines whether to output the communication based on the probability assigned to the communication.

13. The system of claim 11, wherein the communication is output on a second subset of the plurality of recipient devices by retransmitting the communication to the plurality of recipient devices such that the second subset of the plurality of recipient devices outputs the communication.

14. The system of claim 13, wherein the communications server assigns a first probability to the communication and each of the plurality of recipient devices determines whether to output the communication based on the first probability assigned to the communication, and wherein the communications server assigns a second probability different from the first probability prior to retransmitting the communication to the plurality of recipient devices.

15. The system of claim 11, wherein the communication is one of an instant message and an electronic mail message.

16. The system of claim 11, wherein the communication is one of a PollCast and a SkillTap message.

17. The system of claim 11, wherein each recipient device stores the communication in a temporary storage, determines if a predetermined amount of time has elapsed since a previous determination whether to output the communication has been made, determines whether to output the communication based on output criteria, and outputs the communication if the output criteria is satisfied.

18. The system of claim 11, wherein each recipient device compares a bit mask to an identifier of the recipient device, wherein the first subset of the plurality of recipient devices includes recipient devices that are determined to be recipient devices that are to output the communication based on the comparison of the bit mask to the identifiers of the recipient devices.

19. The system of claim 18, wherein the recipient devices shift the bit mask and compare the shifted bit mask to the identifiers of the recipient devices to identify the second subset of the plurality of recipient devices.

20. 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.