|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers)|
|General project answers in this category:|
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?
|Other popular answers from other categories:
My client is switching between projects instead of working only on my first choice
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : What are Optimal Golumb Rulers?|
A excellent explanation of what Optimal Golumb Rulers are is at Mark Garry's* 20/21 search website:
* 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').
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : What would solving OGR actually be good for?|
|OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications. Dr. Golomb was one of the first to analyze them for use in these areas.
|http://www.research.ibm.com/people/s/shearer/grbib.html#grapp lists some papers that show how Golomb rulers can be useful in the fields of information theory and communications.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : If Golomb Rulers up to 150 marks are already known, why are we doing this?|
There are a number of references that list best-known rulers, such as James B. Shearer's list that contains rulers up to 150 marks. However, it should be noted that most of the rulers listed there (ie: those greater than 23) are just loose identifications and have not been proven to necessarily be the most optimal ruler with that number of marks. Additionally, it may well be possible to identify even more optimal rulers for those instances by executing an exhaustive search.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : Is there a prize for winning OGR?|
Not a cash prize. Unlike the RC5 and other crypto challenges in which distributed.net has participated, there is nobody offering a prize for a new, shorter Golomb ruler.
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.
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)"
|I'll donate 2 token ring cards!
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : What is the total number of stubs/nodes in OGR-24 or OGR-25?|
|For OGR-24 phase 1, there are approximately 6,000,000 "5-stubs" per pass (it is planned to have two complete passes for verification purposes). Each of these stubs has a variable number of nodes, ranging from fewer than 900,000 nodes to more than 150,000,000,000 nodes per stub. The 3D surface plots at http://www.distributed.net/statistics/ogr/ show the range and predictability of the number of nodes within any given 5-stub. The horizontal axes within those surface plots represent the first two numbers in the stubs that are distributed, that is the "x" and "y" in "24/x-y-?-?-?"; while the height of the plot represent the number of nodes within the completed stub.
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?
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : What is the most optimal ruler found by d.net so far?|
|The client does not attempt to compute or determine the "optimality" of the rulers it is evaluating. It instead only evaluates rulers to see if they are better than the best ruler speculated by mathematicians. As soon as a ruler (node) is determined to definitely be no better than best-known one, full computation of that ruler's optimality is discontinued and the next node is attempted. As such, the client will only transmit a "success" when it believes it has found one that is better.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : Tell me about the total project percentage complete and Phase 1 and Phase 2?|
|The process of determining the current percentage complete is a much more computationally intensive process than our past cryptographic challenges have been, so it is very difficult to provide percentage data on a regular basis.
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
Phase 2 for OGR-24 started on 16-May-2004, and was completed on 1-Nov-2004.
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:
Similarly for OGR-25, there was a phase 1, and then there are nine sub-phases in phase 2.
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.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : What minimum client and proxy versions are needed for OGR?|
For OGR-NG (supporting OGR-26 and up)Proxy: Requires build 343 or higher. Proxy build 343 will only receive OGR-NG workunits from an upstream server that is also running build 343 or higher.
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.
Client: Requires v2.8009-460 or later. There are a number of client versions earlier than v2.8009-460 that provide the ability to process OGR, however due to known verification bugs in those earlier versions all work computed by them will be discarded by the servers. (Note: OGR may be automatically disabled for non-preemptive operating environments running on lower-end hardware. Details are here: why is OGR disabled on my machine? (It runs OGR elsewhere.))
For OGRp2 (project phase 2)Proxy: Requires build 341 or higher. Proxy build 341 will only connect to an upstream server that is also running build 341 or higher.
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.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : the personal proxy's completed count jumps by irregular amounts for completed stubs.|
|The following is example output for sequentially submited OGR stubs to a personal proxy:
[2000-02-14 23:56:33] ogr r=16/16, d=3/3, 63.3 Mnodes/sec, tot=19
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.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : why is OGR disabled on my machine? (It runs OGR elsewhere.)|
OGR may be automatically disabled for non-preemptive operating environments
running on low(er)-end hardware.
The current OS and CPU combinations where this automatic disabling is currently effective (subject to change) are as follows:
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.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : Why can't I get any OGR blocks sometimes?|
Please read this page for an explanation why.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : How does the client search for OGRs?|
A brute force OGR search is essentially a set of nested for loops. For example, an OGR-10 search might look like this:
# Best known OGR-10 is of length 55, so don't search past that For A1 = 1 to 55-OGR # OGR is the length of the optimum 9-mark ruler For A2 = A1 to 55-OGR For A3 = A2 to 55-OGR ... 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.
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : 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%!|
|By their nature, OGR stubs vary greatly in the number of nodes that must be checked by your client. Therefore, some stubs may complete much more rapidly than others. Additionally, it may sometimes appear that no progress has been made on a stub, even after many minutes or even hours, when in reality progress has been made, but it is simply not expressable as a change in percentage. The slow performance of a portion of a stub should not be considered to represent the performance of the rest of the stub.
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.
Note also that the percent bar will go much faster the further you get through the stub. Generally, the first 10% may appear to take the longest amount of time.
Do not be alarmed if stubs take 40 or more hours on even a 500+ Mhz PIII. It is not a measure of hardness, but of allocation unit size. Keep in mind that other mathematical contests such as Mersenne Primes can take several weeks to process a single allocation unit. The extremely small block size of previous RC5 contests has "spoiled" the expectations of many of us into thinking that all work units should be completed in the same amount of time, and in only a few minutes/hours.
|Other popular answers from other categories:|
Packets take too long to complete on my computer. They should be smaller!
Why did I receive a very large/small OGR-25 stub?
|distributed.net Faq-O-Matic : Project: OGR (Optimal Golomb Rulers) : Why did I receive a very large/small OGR-25 stub?|
|During the initial transition from OGR-24 to OGR-25, there was a small number of varying sized stubs that were distributed to clients for testing purposes so that we could get some public feedback about their completion times. For OGR-25, we've settled on distributing so-called "6-stubs" (that is, a stub fragment
where the first 6 marks are specified by our servers). Such stubs will
be displayed by the client as "25/1-2-3-4-5-6". It can be observed that "25/" stubs that have more than 6 marks will take considerably shorter duration to complete, stubs with fewer marks will take considerably longer duration.
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.
© Copyright distributed.net 1997-2013 - All rights reserved