Contention detection and resolution

• US 20080133690A1
• Filed: 10/05/2007
• Published: 06/05/2008
• Est. Priority Date: 10/05/2006
• Status: Abandoned Application

• Current Assignee: John M. Holt
• Original Assignee: John M. Holt
• Inventors: Holt, John M.
• Application Number:
  US11/973,376
• Publication Number:
  US 20080133690A1
• Time in Patent Office: Days
• US Class Current: 709/212
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A multiple computer system is disclosed in which n computers (M1, M2 . . . Mn) each run a different portion of a single application program written to execute only on a single computer. The local memory of each computer is maintained substantially the same by updating all computers with every change made to addressed memory locations. Contention can arise when the same memory location is substantially simultaneously updated by two or more machines because of transmission delays and latency of the communications network interconnecting all the computers. In particular a method of detecting and resolving contention is disclosed which utilizes a count value indicative of the number of the sequence of occasions on which each memory location has been updated. Contention is indicated if the currently stored count value and the incoming updating count value are the same. The contention can be resolved by providing a further rule. One such further rule is that in the presence of contention the updating message from the higher numbered computer is to be accepted and the updating message from the lower numbered computer is to be rejected. Other further rules are also disclosed.

Claims

1. A system for resolving contention in replica memory updating for a multiple computer system comprising a multiplicity of computers, each or the a multiplicity of computers interconnected via at least one communications network, and each executing a different portion of an application program written to execute on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, said system for resolving contention in replica memory updating for a multiple computer system comprising:

at least one memory location having a specific location identifier;

a plurality of sources each of which can update said replicated memory location(s) and each of which utilizes an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the replicated memory location to be updated, the content with which said replicated memory location is to be updated, and a resident updating count of the updating source associated with the replicated memory location, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resolution value of the updating source associated with the replicated memory location, said resolution value said resolution value comprising a unique value to or of the updating source;

a storage means associated with each said replicated memory location and in which the updating count and resolution value of the previously received updating is stored;

comparison means to compare the previously stored updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet;

contention indicating means connected with said comparison means and operable to indicate a contention situation if the compared updating counts are the same; and

contention resolution means connected with said contention indicating means to institute a contention resolution procedure.

2. A system for resolving contention in replica memory updating for a multiple computer system as in claim 1, wherein said contention resolution procedure further comprises:

comparing the presently resident resolution value associated with the replicated memory location to be updated with the updating resolution value of the currently received updating signal or packet; and

(i) if the currently received resolution value is greater than the presently resident resolution value, overwriting the associated replicated memory location with the currently received data content, and overwriting the presently resident updating count with the currently received updating count, and overwriting the presently resident resolution value with the currently received resolution value;

or

(ii) if the currently received resolution value is less than the presently resident resolution value, not overwriting the associated replicated memory location with the currently received data content, and not overwriting the presently resident updating count with the currently received updating count, and not overwriting the presently resident resolution value with the currently received resolution value.

3. The system as in claim 1, wherein said contention indicating means includes an overwrite means which acts upon the currently received updating signal or packet to replace the content of the specific memory location with the content of the incoming signal or packet, and replaces the presently resident updating count with the updating count of the incoming signal or packet.

4. The system as in claim 1, wherein the operation of said contention resolution means is substantially independent of time.

5. The system as in claim 1, wherein said contention resolution means includes a comparator means, each said updating source is assigned an indicative number, the indicative numbers of the last updating source and the currently updating, but contention indicated, source are compared by said comparator means, and the currently received updating signal or packet is acted upon only if the comparison is positive.

6. The system as in claim 1, wherein said contention resolution means includes a comparator means, each said updating source is assigned an indicative number, the indicative numbers of the last updating source and the currently updating, but contention indicated, source are compared by said comparator means, and the currently received updating signal or packet is acted upon only if the comparison is negative.

7. The system as in claim 5, wherein said indicative number represents the number of a computer in a hierarchy of computers.

8. The system as in claim 5, wherein said indicative number is a substantially random number.

9. The system as in claim 1, wherein said memory location is one of a plurality of memory locations resident in one of a plurality of computers and each of said plurality of computers has substantially the same structure of memory locations.

10. The system as in claim 9, wherein each said updatable memory location in one of said computers has a corresponding memory location in each of the others of said computers.

11. The system as in claim 10, wherein each said updatable memory location has a local memory address which is different from said location identifier.

12. A method of resolving contention in replica memory updating for a multiple computer system comprising a multiplicity of computers, each interconnected via at least one communications network, and each executing a different portion of an application program written to execute on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, and in which a memory location having a specific location identifier can be updated substantially simultaneously from a plurality of sources, said method of resolving contention in replica memory updating for a multiple computer system comprising:

(a) utilizing an updating format for a signal or packet of information carrying out the updating, said updating format comprising a specific identifier of the replicated memory location to be updated, the content with which said replicated memory location is to be updated, a resident updating count of the updating source associated with the replicated memory location, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resident resolution value, and a resolution value of the updating source associated with the replicated memory location, said resolution value comprising a unique value to or of the updating source;

(b) storing for each receiving replicated memory location the updating count and resolution value of the previously received updating;

(c) comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of any currently received updating signal or packet; and

(d) actioning or not actioning the incoming signal or packet according to predetermined policies.

13. A method of resolving contention in replica memory updating for a multiple computer system as in claim 12, wherein the actioning or not actioning of the incoming signal or packet predetermined policies include:

(i) if the currently received updating count associated with the replicated memory location to be updated is equal to the presently resident updating count, not actioning the incoming signal or packet;

or

(ii) if the currently received updating count is less than the currently resident updating count, actioning the incoming signal or packet;

or

(iii) if the currently received updating count is equal to the presently resident updating count, comparing the presently resident resolution value associated with the replicated memory location to be updated with the updating resolution value of the currently received updating signal or packet; and

(iv) if the currently received resolution value is greater than the presently resident resolution value, overwriting the associated replicated memory location with the currently received data content, and overwriting the presently resident updating count with the currently received updating count, and overwriting the presently resident resolution value with the currently received resolution value;

or

(v) if the currently received resolution value is less than the presently resident resolution value, not overwriting the associated replicated memory location with the currently received data content, and not overwriting the presently resident updating count with the currently received updating count, and not overwriting the presently resident resolution value with the currently received resolution value.

14. The method as in claim 12, in which actioning the incoming signal or packet includes the steps of:

replacing the content of the specific memory location with the content of the incoming signal or packet, and replacing the presently resident updating count with the updating count of the incoming signal or packet.

15. The method as in claim 12, wherein said instituted contention resolution procedure is substantially independent of time.

16. The method as in claim 15, wherein said contention resolution procedure comprises the steps of:

(vii) determining the identity of each updating source, said updating sources being assigned a hierarchial order; and

(viii) accepting the updating signal or packet from the source, with the higher ranking in said hierarchial order.

17. The method as in claim 15, wherein said contention resolution procedure comprises the steps of:

(ix) determining the identity of each updating source, said updating sources being assigned a hierarchial order; and

(x) accepting the updating signal or packet from the source with the lower ranking in said hierarchial order.

18. The method as in claim 15, wherein in said contention resolution procedure comprises the steps of:

(xi) allocating a substantially random number to each updating source; and

(xii) accepting the updating signal or packet from the source with the higher random number.

19. The method as in claim 15, wherein in said contention resolution procedure comprises the steps of:

(xiii) allocating a substantially random number to each updating source; and

(xiv) accepting the updating signal or packet from the source with the lower random number.

20. A computer program stored in a computer readable media, the computer program adapted for execution in a processor within a computer or information appliance and a memory coupled with the processor to modify the operation of the computer or information appliance, for modifying the operation of the computer or information appliance in a multiple computer system including a multiplicity of computers, each interconnected via at least one communications network, and each executing a different portion of an application program written to execute on only a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, and in which a memory location having a specific location identifier can be updated substantially simultaneously from a plurality of sources, the modification including performing a method of resolving contention in replica memory updating for the multiple computer system, the method comprising:

(a) utilizing an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the replicated memory location to be updated, the content with which said replicated memory location is to be updated, a resident updating count of the updating source associated with the replicated memory location, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resident, and a resolution value of the updating source associated with the replicated memory location, said resolution value comprising a unique value to or of the updating source;

(b) storing for each receiving memory location the updating count and resolution value of the previously received updating;

(c) comparing the updating count presently resident at the receiving memory location with the updating count of any currently received updating signal or packet; and

(d) actioning or not actioning the incoming signal or packet according to predetermined policies.

21. A computer program as in claim 20, wherein the actioning or not actioning of the incoming signal or packet predetermined policies include:

(i) if the currently received updating count associated with the replicated memory location to be updated is equal to the presently resident updating count, not actioning the incoming signal or packet;

or

(ii) if the currently received updating count is less than the currently resident updating count, actioning the incoming signal or packet, or

(iii) if the currently received updating count is equal to the presently resident updating count, comparing the presently resident resolution value associated with the replicated memory location to be updated with the updating resolution value of the currently received updating signal or packet; and

(iv) if the currently received resolution value is greater than the presently resident resolution value, overwriting the associated replicated memory location with the currently received data content, and overwriting the presently resident updating count with the currently received updating count, and overwriting the presently resident resolution value with the currently received resolution value;

or

(v) if the currently received resolution value is less than the presently resident resolution value, not overwriting the associated replicated memory location with the currently received data content, and not overwriting the presently resident updating count with the currently received updating count, and not overwriting the presently resident resolution value with the currently received resolution value.

22. In a multiple computer system comprising a multiplicity of computers, each interconnected via at least one communications network, and each executing a different portion of an applications program written to execute on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, a method of resolving contention in replica memory updating in which a memory location having a specific location identifier and replicated on at least two of the multiplicity of computers can be updated substantially simultaneously from a plurality of sources, said method comprising the steps of:

(i) utilizing an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resolution value of the updating source, said resolution value comprising a unique value to or of the updating source;

(ii) storing for each replicated memory location the updating count and resolution value of the previously sent or received updating;

(iii) comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet; and

(a) if the currently received updating count is equal to the presently resident updating count, comparing the presently resident resolution value associated with the replicated memory location to be updated with the updating resolution value of the currently received updating signal or packet; and

(b) if the currently received resolution value is greater than the presently resident resolution value, overwriting the associated replicated memory location with the currently received data content, and overwriting the presently resident updating count with the currently received updating count, and overwriting the presently resident resolution value with the currently received resolution value;

or

(c) if the currently received resolution value is less than the presently resident resolution value, not overwriting the associated replicated memory location with the currently received data content, and not overwriting the presently resident updating count with the currently received updating count, and not overwriting the presently resident resolution value with the currently received resolution value.

23. A system for resolving contention in replica memory updating in a multiple computer network including a plurality of networked computers each executing a different portion of an applications program written to execute on a single computer, each having an independent local memory with at least one memory location being replicated in each said local memory, said system for resolving contention in replica memory updating involving at least one memory location having a specific location identifier and replicated on at least two computer machines and updated to remain substantially similar upon occasion of a machine modifying a replica of its value;

said system for resolving contention in replica memory updating further comprising;

a plurality of sources, each of which can update said memory location(s) and each of which utilizes an updating format for the signal or packet carrying out the updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, and a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and a resolution value of the updating source, said resolution value comprising a unique value to or of the updating source;

a storage means associated with each said replicated memory location and in which the updating count and resolution value of the previously sent or received updating is stored;

comparison means to compare the currently received updating count value associated with the replicated memory location to be updated with the presently resident updating count value; and

if the compared updating counts are the same, comparing the presently resident resolution value associated with the replicated memory location to be updated with the updating resolution value of the currently received updating signal or packet; and

if the currently received resolution value is greater than the presently resident resolution value, overwriting the associated replicated memory location with the currently received data content, and overwriting the presently resident updating count with the currently received updating count, and overwriting the presently resident resolution value with the currently received resolution value;

or

if the currently received resolution value is less than the presently resident resolution value, not overwriting the associated replicated memory location with the currently received data content, and not overwriting the presently resident updating count with the currently received updating count, and not overwriting the presently resident resolution value with the currently received resolution value.