Method of propagating data through a distributed information system

• US 5,805,824 A
• Filed: 02/28/1996
• Issued: 09/08/1998
• Est. Priority Date: 02/28/1996
• Status: Expired due to Fees

• Current Assignee: Hyper-G Software Forchungs-Und Entwicklungsgesellschaft MGH
• Original Assignee: Hyper-G Software Forchungs-Und EntwicklungsGmbH
• Inventors: Kappe, Frank Michael
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/608,302
• Time in Patent Office: 923 Days
• Field of Search: 395/200.72, 395/610, 395/615, 395/200.7, 395/200.82, 340/825.02
• US Class Current: 709/242
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24565 Triggers; Constraints
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting

Abstract

A method of propagating data through a distributed information system is closed wherein in a computer implemented distributed information system, a method of maintaining referential integrity of a plurality of links and documents by propagating updates from a server to a plurality of servers, comprising the steps of; i) the server maintaining an ordered list of the plurality of servers in the distributed information system; ii) the server maintaining a link database containing the plurality of links for locating remote documents stored remotely which are referenced by documents stored locally at the server; iii) the server maintaining an update list including messages reflecting changes to local documents and links and remote documents and links; iv) selecting a priority value (p) with which to transmit the update list wherein the priority value is a real number greater than or equal to 1; v) on a predetermined clock cycle, the server transmitting the update list according to the priority value wherein, the server transmits the update list to a receiving server located adjacent to it on the ordered list, to an integer portion of p-1 other receiving servers selected at random from the ordered list and to another receiving server selected at random from the ordered list with a probability equal to a fractional portion of p; vi) the receiving servers updating their link databases and the locally stored documents with messages from the update list and appending the receiving servers respective lists of object data with the received list of object data; and vii) repeating steps v) through vii).

Claims

1. In a computer implemented distributed information system, a method of propagating data through a plurality of servers, comprising the steps of:

i) each of the servers individually maintaining an ordered list of the servers in the distributed information system;

ii) each of the servers individually maintaining a database containing address data for locating remote data stored remotely which is referenced by local data stored locally at each of the servers;

iii) each of the servers individually maintaining a list of data reflecting changes to the local data and remote data;

iv) selecting a priority value (p) with which to transmit the list of data wherein the priority is a real number greater than or equal to 1;

v) on a predetermined clock cycle, each of the servers transmitting their respective list of data to at least one server selected from the ordered list according to the priority value;

vi) each of the servers deleting their respective list of data once acknowledgement of the transmission is received from the at least one server;

vii) each of the at least one server receiving their respective list of data and updating their database and their local data with the received list of data, and appending their list of data with the received list of data;

viii) repeating steps v) through viii), wherein in step v), when p=1 each of the servers transmit their respective lists to a server located adjacent to each of servers on the ordered list and when p is an integer number greater than one, each of the servers transmit their respective lists to the adjacent server and to p-1 other servers selected at random from the ordered list.

2. The method according to claim 1 wherein in step i), the ordered list is arranged by an approximate geographical orientation of the plurality of server.

3. The method according to claim 2 wherein the approximate geographical orientation is circular.

4. The method of claim 1 wherein in step iv) the priority value is a real number in the range from about 1 to about 3.

5. The method of claim 1 wherein in step v), when p=1 each of the servers transmit their respective lists to a server located adjacent to each of servers on the ordered list.

6. The method of claim 1 wherein in step v), when p is a real number greater than one, each of the servers transmit their respective lists to the adjacent server, to the integer portion of p-1 other servers selected at random from the ordered list and to one other server selected at random with a probability equal to the decimal portion of p.

7. In a computer implemented distributed information system, a method of propagating object data from a server to a plurality of servers, comprising the steps of:

i) the server maintaining an ordered list of the plurality of servers in the distributed information system;

ii) the server maintaining a database containing address data for locating remote objects stored at some of the plurality of file servers which are referenced by local objects stored at the server;

iii) the server individually maintaining a list of object data including changes to the address data, local objects and remote objects;

iv) selecting a priority value with which to transmit the list of object data wherein the priority is greater than or equal to 1;

v) on a predetermined clock cycle, the server transmitting the list of object data to at least one server selected from the ordered list according to the priority value;

vi) the server deleting the list of object data once acknowledgement of the transmission is received from the at least one server;

vii) the at least one server receiving the list of object data and updating the database and the local objects with the object data, and appending the at least one servers'"'"' list of object data with the received list of object data;

viii) repeating steps v) through viii) when p=1 the server transmits the list to a server located adjacent to it on the ordered list and wherein in step v), when p is an integer number greater than one, the server transmits the list to the adjacent server and to p-1 other servers selected at random from the ordered list.

8. The method according to claim 7 wherein the plurality of servers individually perform the steps of i) through viii) in parallel.

9. The method according to claim 8 wherein in step v) each of the plurality of servers individually maintains their own predetermined clock cycle.

10. The method according to claim 9 wherein the individually maintained clock cycles are not synchronized across the distributed information system.

11. The method according to claim 8 wherein in step i), the ordered list is arranged by an approximate geographical orientation of the plurality of server.

12. The method according to claim 11 wherein the approximate geographical orientation is circular.

13. The method of one of claims 7 or 8 wherein in step iv) the priority value is a real number in the range from about 1 to about 3.

14. The method of claim 7 wherein in step v), when p is a real number greater than one, the server transmits the lists the adjacent server, to the integer portion of p-1 the other servers selected at random and to another server selected at random with a probability equal to the decimal portion of p.

15. In a computer implemented distributed information system, a method of maintaining referential integrity of a plurality of links and documents by propagating updates from a server to a plurality of servers, comprising the steps of;

i) the server maintaining an ordered list of the plurality of servers in the distributed information system;

ii) the server maintaining a link database containing the plurality of links for locating remote documents stored remotely which are referenced by documents stored locally at the server;

iii) the server maintaining an update list including messages reflecting changes to local documents and links and remote documents and links;

iv) selecting a priority value (p) with which to transmit the update list wherein the priority value is a real number greater than or equal to 1;

v) on a predetermined clock cycle, the server transmitting the update list according to the priority value wherein, the server transmits the update list to a receiving server located adjacent to it on the ordered list, to an integer portion of p-1 other receiving servers selected at random from the ordered list and to another receiving server selected at random from the ordered list with a probability equal to a fractional portion of p;

vi) the receiving servers updating their link databases and the locally stored documents with messages from the update list and appending the receiving servers'"'"' respective lists of object data with the received list of object data;

vii) repeating steps v) through vii).

16. The method according to claim 15 wherein each of the plurality of servers individually perform the steps of i) through vii) in parallel.

17. The method according to claim 16 wherein in step v) each of the plurality of servers individually maintains their own predetermined clock cycle.

18. The method according to claim 17 wherein the individually maintained clock cycles are not synchronized across the distributed information system.

19. The method according to claim 15 wherein in step i), the ordered list is arranged by an approximate geographical orientation of the plurality of server.

20. The method according to claim 19 wherein the approximate geographical orientation is circular.