What are Optimal Golumb Rulers?

What would solving OGR actually be good for?

If Golomb Rulers up to 150 marks are already known, why are we doing this?

Is there a prize for winning OGR?

What is the total number of stubs/nodes in OGR-24 or OGR-25?

What is the most optimal ruler found by d.net so far?

Tell me about the total project percentage complete and Phase 1 and Phase 2?

Client and proxy answers in this category:
What minimum client and proxy versions are needed for OGR?
the personal proxy's completed count jumps by irregular amounts for completed stubs.
why is OGR disabled on my machine? (It runs OGR elsewhere.)
Why can't I get any OGR blocks sometimes?
How does the client search for OGRs?

Speed answers in this category:
Why do some stubs go faster than others? My stub OGR stub takes too long! My OGR stub has stopped progressing at 1 or 2%!
Why did I receive a very large/small OGR-25 stub?

My client is switching between projects instead of working only on my first choice
I'm confused about keys, stats units, nodes, stubs, packets, blocks, work units,...
Packets take too long to complete on my computer. They should be smaller!

http://members.aol.com/golomb20/intro.htm

^* The 'generic' OGR core in the distributed.net client is an adaptation of Mark Garry's work ("GARSP" stands for 'Garry's Adaptation of Rado's Searching Principles').

But you do get the chance to contribute however fractionally to the sum total of human knowledge, and may even get mentioned in the footnote of some obscure maths journal.

And it is good karma.

Update:

Actually, yes. Jonah Schulte is offering the "winner" 20 U.S. dollars. :) If there is more than one "winner" of OGR, Jonah will select one winner at random to receive the big cash prize.

As OGR is more of an "exhaustion of possibilities" as opposed to an attempt to find the correct key, Alex "froggie" Heighton is offering a genuine, english 1 shilling piece (note: not legal tender in the UK) to the last stub submitted.

NukeEmUp@ThePentagon.com has offered to wire UK£50 to the 'winner', or the equivalent in other major currencies.

neil@whatUseek.com will send you a $50.00 US check/cheque if you "win" OGR. He thinks this a small price to pay for reducing your chances of winning the RC5, and increasing his. ;-)

Hit1Hardhas offered to send a Fl 25,- guilders note to the "winner", "since we Dutch have the nicest money of the world. (its seen as "monopoly" money)"

Keep in mind that the number of nodes within a given stub has absolutely no relation to the "shortness" or "optimality" of the ruler that the project is looking for. The node count merely represents the number of golomb ruler possibilities that were checked within that stub's prefix, of which any single one has a chance of being a golomb ruler that is more optimal than what is currently known.

You may want to also check out: Tell me about the total project percentage complete and Phase 1 and Phase 2?

Computing the percentage complete depends on re-collating all of the completed stubs and accounting for the distribution of stubs that count against the secondary verification pass, and requires entirely reprocessing several hundreds of megabytes of compressed completion data. It also depends on whether you are attempting to compute the overall percentage complete, or just the percentage of phase 1 or phase 2 of the project.

While the projects were running, the percentage complete for OGR-24 and OGR-25 were available at:

  OGR-24 -- http://stats.distributed.net/projects.php?project_id=24

  OGR-25 -- http://stats.distributed.net/projects.php?project_id=25

Phase 2 for OGR-24 started on 16-May-2004, and was completed on 1-Nov-2004.
Phase 2 of OGR-25 started on 16-May-2004, and was completed on 28-Oct-2008.

OGRNG (ie: OGR-26 and beyond) are expected to on only require one phase, however there will still be "sub-phases".

Although we try to present the OGR progress as just two percentages (one for phase 1 and one for phase 2), it is actually a little more complex.

For OGR-24, there was a phase 1, and then two sub-phases in phase 2:

• Phase 1 (aka "OGR24 classic"): 5-diffs stubs (len <= 70) belong to the OGR contest. Completed!
• Phase 2 (aka "OGRp2-24" sub-phase 1): 4-diffs stubs (the client places the 6th mark at a position > 70). Stub len < 80. Total 1131772 stubs. Completed!
• Phase 2 (aka "OGRp2-24" sub-phase 2): 3-diffs stubs (the client places the 5th mark at a position >= 80). Total 95748 stubs. Completed!

Similarly for OGR-25, there was a phase 1, and then there are nine sub-phases in phase 2.

• Phase 1 (aka "OGR25 classic"): 6-diffs stubs (len <= 70) belong to the OGR contest. Completed!
• Phase 2 (aka "OGRp2-25" sub-phases 1 thru 5): 6-diffs stubs (70 < len <= 95). Extension to the OGR contest. Subdivided into five chunks for manageability:
  • 48979672 6-diffs stubs : 70 < stub-length <= 81 Completed!
  • 42196852 6-diffs stubs : 81 < stub-length <= 86 Completed!
  • 47775232 6-diffs stubs : 86 < stub-length <= 90 Completed!
  • 46417392 6-diffs stubs : 90 < stub-length <= 93 Completed!
  • 36267180 6-diffs stubs : 93 < stub-length <= 95 Completed!
  (Total : 221636328 6-diffs stubs.)
• Phase 2 (aka "OGRp2-25" sub-phases 6 thru 7): 5-diffs stubs (len < 112, the client places the 7th mark at a position > 95). Subdivided into two chunks for manageability:
  • 38361468 5-diffs stubs : 0 < stub-length <= 98 Completed!
  • 38106790 5-diffs stubs : 98 < stub-length <= 111 Completed!
  (Total : 76468258 5-diffs stubs.)
• Phase 2 (aka "OGRp2-25" sub-phase 8): 4-diffs stubs (len < 122, the client places the 6th mark at a position >= 112). Completed!
(Total : 6515212 4-diff stubs.)
• Phase 2 (aka "OGRp2-25" sub-phase 9): 3-diffs stubs (the client places the 5th mark at a position >= 122). Completed!
(Total : 237944 3-diffs stubs.)

The higher-diff stubs overlap with the smaller-diff stubs from later sub-phases, so there is less work (fewer average nodes per stub) left for the later sub-phases. This makes the overall project percentage for Phase 2 (which is measured in stubs not nodes) seem to progress more slowly in the early sub-phases, than the later sub-phases.

Additionally, each stub is distributed at least two times in order to get the necessary validation by two different computers.

For OGR-NG (supporting OGR-26 and up)

Client: Requires v2.9101.507 or later. These clients can connect to proxy versions lower than 343, but will not be able to send or receive OGR-NG packets.

For OGR "Classic" (project phase 1)

Client: Requires v2.9008-490 or later. These clients can connect to proxy versions lower than 341, but will not be able to send or receive OGRp2 packets.

[2000-02-14 23:56:33] ogr r=16/16, d=3/3, 63.3 Mnodes/sec, tot=19
[2000-02-14 23:57:37] ogr r=16/16, d=4/3, 75.1 Mnodes/sec, tot=22
[2000-02-14 23:58:35] ogr r=16/16, d=5/3, 91.2 Mnodes/sec, tot=26

the totalNotify count for OGR represents the upper 32-bit word of the total number OGR nodes completed.

For each of the (artificial) OGR stubs in question, there were 13.52 Gnodes (13.52*10^9). The upper 32-bit word of that is (13.52*10^9)/2^32=3.178, which is the origin of the factor that causes your "tot=" count to increment by 3.

The proxy actually keeps track of the full 64-bit word of the total number of nodes completed, but the "tot=" printed only reflects the upper 32-bit word of it.

The current OS and CPU combinations where this automatic disabling is currently effective (subject to change) are as follows:

• RISC OS/ARM: (if the client is not being preemptively tasked)
  all
• MacOS/68k
  all 680x0 processors
• MacOS/PPC:
  PPC601
• Windows16/x86:
  386-class, 486-class, 586-class (incl. Cx6x86 and K5)
• NetWare/x86:
  all

In non-preemptive environments, the client controls its run:yield quantum itself, that is, it runs for a limited, specific, number of keys/nodes (called the timeslice), then yields, then runs, then yields, and so on.

The timeslice is computed dynamically while the computer runs, and generally follows this formula: crunch_rate_per_second/yield_frequency ^(*), where yield_frequency is a semi-static value representing the minimum number of times per second that the client has to yield control for the machine to remain responsive, and crunch_rate_per_second is continuously calculated.

For OGR, which has significant overhead, the larger the timeslice (upto a limit), the more efficient the core is. To put it another way: at small timeslices, which is what would be in effect on slow machines, the core ends up spending more time in starting and stopping than it does in actually working.

Moreover, the time slice cannot be honored precisely, and under some circumstances, the OGR core could end up doing several hundred thousand more nodes than it was told to do. In less critical environments such as Win16 and MacOS such occasional "jerkiness" may be tolerable, and it is left to the user's discretion to disable OGR if they feel such behaviour is unacceptable. In mission critical environments such as NetWare however, any jerkiness may have disastrous consequences, and for NetWare, OGR is completely disabled.

^*: For all practical purposes, the formula mentioned above is sufficient, but there are some gotchas:
yield duration: if another task runs for a not insignificant amount of time, or the OS imposes a maximum "task" switch frequency to avoid scheduling the same task too often, then this "yield duration" is going to affect the crunch_rate_per_second part of the computation, and the timeslice will be lower.
timer resolution: The formula mentioned above implies that that the smallest run:yield quantum that can be computed accurately is equal to the resolution of the monotonic time source. Using longer timing periods and averaging the results makes it possible to increases the accuracy of the computation, but this can still be no better than half the timer's period. This means that if the clock's resolution was say, 100ms, then the client can yield (at best) only every 50ms.

# Best known OGR-10 is of length 55, so don't search past that
For A1 = 1 to 55-OGR[9] # OGR[9] is the length of the optimum 9-mark ruler
  For A2 = A1 to 55-OGR[8]
    For A3 = A2 to 55-OGR[7]
...
      For A10 = A9 to 55
        Does A1 thru A10 form an OGR? If so, we have a new best OGR!
      Next A10
...
    Next A3
  Next A2
Next A1

Of course, this is a highly simplistic view, and there are many tricks that can be used to narrow the search. One important thing to note is that as the outer loop variables get large, the amount of time spent in the inner loops decreases drastically.

For distributed.net, these for loops are split between the client and the master. The master will generate a stub of a ruler, such as '25/6-5-8-21-15-3'. This tells the client that it should work on a 25 mark ruler, with A1=6, A2=5, A3=8, A4=21, A5=15, and A6=3.

Part of what the master does when generating stubs is limit the size of the stub. If this was not done, the number of stubs (and thus the amount of data the master would have to track) would be far larger than it currently is. More important, if initial stub size wasn't limited, many stubs would be generated that would take minutes or even seconds for a client to search. This would create a unacceptably large load on the network.

Greg Hewgill has a page that describes distributed.net's OGR implimentation in a bit more detail.

In general, stubs that have a larger numbered marks in them are "easier" than those with purely smaller numbered marks. Additionally, the node count of a stub will generally vary quite predictably with the values of the first two marks of the stub. Graphs of the node count distributions based on the first two mark values can be found for OGR-24 at http://www.distributed.net/statistics/ogr/ There are also similar graphs for the old OGR-21 effort at http://www.hewgill.com/golomb/

Unfortunately, this is due to the large amount of uncertainty that the client has while evaluating stubs. During the evaluation process, the client will discover that certain portions of the stub do not need to be evaluated and will correspondingly skip over the rest of that portion. Due to this behavior, it is very difficult to provide a linearly progressing percentage bar.

Although we generally tried to intersperse these experimental OGR-25 stubs into the outgoing OGR-24 distribution to minimize giving too many to any single person, we've learned this might not have necessarily been the case.

In any case, since our intended benchmarking use of these experimental stubs is finished, if you see that your client is working on a "25/" stub that does not have exactly 6 values after the slash then you can feel free to discard your entire buff-in.ogr containing these experimental OGR-25 stubs, if you are too impatient and want to process normally sized stubs. (Proper-sized stubs that you accidentally discard along with those will be eventually recycled and reverifed more than once eventually, so it is not a serious concern in this case, though you should avoid intentionally discarding valid blocks whenever possible.)

Even though statistics credit can only be given for OGR-25 stubs with 6 marks, the processing resulting from the larger and smaller sized test stubs still represent valid search ranges within the stub space, and have comparable contribution towards the project's overall search as the equivalent number of proper-sized stubs. The results from those larger/smaller stubs will also be beneficial in providing second-pass verification against clients completing the corresponding group of stubs.