OGR-24 project geëindigd: DPC overtuigend op #1

Begin deze maand heeft distributed.net het einde aangekondigd van haar project OGR-24. Bij dit distributed-computingproject werd gezocht naar de OGR van 24 merktekens, die nu gevonden is. De Dutch Power Cows (DPC) hebben dit project winnend afgesloten; zij hebben de afgelopen jaren veruit de meeste OGR's onderzocht en eindigden daardoor ruimschoots bovenaan de teamranglijst.

Over OGR

OGR staat voor Optimal Golomb Ruler. Eenvoudiger gezegd is het de kortst mogelijke liniaal met een bepaald aantal punten, waarbij alle maatstrepen op verschillende afstand van elkaar zitten. OGR's maken het mogelijk zo veel mogelijk afstanden te meten met een minimum aan meetpunten. Zo is het bijvoorbeeld mogelijk om met een OGR die vijf meetpunten omvat, tien afstanden te meten:

Juist de eigenschap dat met zo min mogelijk meetpunten zo veel mogelijk afstanden gemeten kunnen worden, maken OGR's interessant voor toepassing in bijvoorbeeld radiotechnologie, sensorplaatsing en röntgenapparatuur.

Het project

Er zijn in het verleden al veel mogelijke OGR's opgeschreven. Mogelijke OGR's, omdat er slechts van een beperkt aantal is aangetoond dat het ook werkelijk OGR's zijn. Het bewijzen van een OGR gebeurt door alle andere mogelijke linialen na te gaan, en te kijken of het een OGR is. Tot en met vier merktekens zijn OGR's nog redelijk goed uit het hoofd te bepalen, tot en met acht merktekens is het met pen en papier te doen.

Later bewezen de eerste computers hun nut; in 1972 al werden met behulp van een computer OGR's met negen tot en met elf merktekens bewezen. Tussen 1979 en 1994 werden OGR's van twaalf tot en met negentien merktekens bewezen, door steeds verder verbeterde computerprogramma's, maar daarna bleef het een tijdje stil. De exponentiële toename in te doorzoeken mogelijkheden zorgde ervoor dat het niet langer handig was om OGR's met slechts één computer te zoeken. In 1997 werden er clients ontwikkeld waarmee het werk te verdelen valt over meerdere computers. OGR-20 tot en met OGR-23 werden hiermee bewezen. In 1999 werd het overleg met distributed.net gestart om OGR's op wereldwijde schaal te gaan zoeken. Half 2000 werd hiervoor de eerste distributed computing-client voor OGR-24 uitgebracht.

DPC en OGR

OGR werd aangekondigd als project op het moment dat DPC druk in gevecht was met Team AnandTech bij RC5-64, het eerste project waar DPC aan meedeed en waarmee DPC zijn wereldwijde DC-bekendheid heeft verworven. Er was op dat moment nog maar weinig interesse in OGR. Nadat AnandTech was verslagen en de voorsprong groeide, werd OGR populairder. Ook hier werden nu de pijlen op de #1 gericht. OGR was inmiddels echter een gebundeld project van OGR-24 en OGR-25, waarbij de eerste fase van OGR-24 eigenlijk al grotendeels voorbij was toen DPC goed op gang kwam. De #1 bij OGR-25 werd dan ook eerder bereikt dan bij OGR-24. Dat gebeurde pas toen wat resten OGR-24 beschikbaar kwamen en DPC er vol op dook.

Bij de tweede fase van OGR, waarbij de vele zeer kleine porties gecombineerd konden worden om de infrastructuur niet in gevaar te brengen, liet DPC wederom zien zeer snel over te kunnen schakelen naar nieuwe clients en bouwde de voorsprong nog verder uit.

Einde van het project OGR-24

Ruim vier jaar na de start van het project is de kortste liniaal uiteindelijk bepaald. Het is:
24/9-24-4-1-59-25-7-11-2-10-39-14-3-44-26-8-40-6-21-15-16-19-22

Deze kortste liniaal is als eerste gevonden door Matt Richards (Matt_R in #distributed) op 24 mei 2004. Mitsuru Aoki van het SEGA Users Group Team bevestigde dit op 3 juli 2004. Maar pas toen Sebastian "Pax" Schmitz op 13 oktober 2004 de allerlaatste mogelijkheid had ingeleverd was duidelijk dat het echt de kortste OGR-24 was.

De liniaal is dezelfde als die in 1967 werd voorspeld. Hiermee is OGR-24 ten einde en kan in de lijst worden vermeld dat OGR-24 bewezen is. DPC mag zich met recht de grootste deelnemer noemen. Namens DPC en ook namens distributed.net worden alle deelnemers bedankt voor hun deelname.

Voortgang van het project OGR

Het OGR-25 project loopt nog volop. DPC heeft hier twee weken terug zelfs de 500 miljoen mijlpaal gehaald. De verwachting is dat de algoritmes om OGR's te bewijzen de komende jaren nog behoorlijk verbeteren, zodat na het afronden van OGR-25 een OGR-26 verwacht kan worden. Wie dit een interessant project vindt, kan in het vorige nieuwsbericht over OGR lezen hoe er kan worden meegedaan aan OGR-25.

Reacties (52)

[holycow]

Gaan de mensen van OGR hun koetjes nu voor de kinderziektes (TSC) laten grazen? Laten we met z´n allen dit zinnige project ondersteunen....

[mvds]

Waarom krijgt hij nou een Troll aan zijn broek?

Eerlijk gezegd vind ik het energieverbruik van al de PC's die gebruikt zijn voor dit project, alleen maar om iets te bewijzen wat al bekend was, ook niet echt opwegen tegen het nut van dit project. Ik weet niet hoelang dit project erover gedaan heeft, maar ik weet wel dat er vele megawatt's ervoor nodig geweest zijn om al die PC's te laten rekenen. Leuk dat we nu dus zeker weten dat die schatting uit 1967 klopt, maar is dat nou echt die extra milieuvervuiling waard?

Het toepassingsgebied van zo'n lineaal is imho zo beperkt dat ik het verspilde moeite vind. Dan vind ik het zoeken naar iets wat nog niet bekend is ook veel nuttiger dan zoiets als dit.

@Zammam ik snap ook wel wat, hoe en waarom ze het wilde bewijzen, dat staat namelijk gewoon in het artikel. En er zijn miljarden dingen te bedenken die je met distributed projecten kan doen. Ik zeg alleen dat ik het nut van dit project, en het toepassingsgebied van de uitkomst, niet vind opwegen tegen de energie die het kost om dit te bewijzen. Dat het mogelijk is om te berekenen wil niet meteen zeggen dat het ook maar gedaan moet worden!

[Luud]

Ik zeg alleen dat ik het nut van dit project, en het toepassingsgebied van de uitkomst, niet vind opwegen tegen de energie die het kost om dit te bewijzen.

Het jammere van deze houding is dat je helemaal niet kunt bepalen of het ene project zinniger is dan het andere.

Een folding project b.v. klinkt als veel nuttiger om dat het dichter bij de medische wereld staat, zeker voor de gewone leek.

Het is echter niet gezegd dat het oplossen van OGR in de toekomst niet net zo belangrijk (of nog belangrijker) kan blijken te zijn voor het verbeteren van onze welvaart en gezondheid. (Het zou zelfs mogelijk kunnen helpen bij het verbeteren van de algoritmen voor een folding project bijv.)

Sommige wiskundige bewijzen lijken slechts leuk te zijn voor wiskundigen als puzels, als deze stellingen echter bewezen zijn blijken ze vaak zeer bruikbaar voor meer wereldse en tastbare problemen.

In ieder geval, toch leuk dat we weer iets meer weten dankzij de uitkomst van OGR24.

[Verwijderd]

Helemaal mee eens. Omdat het praktische nut van dit project niet 1-2-3 naar voren komt, vindt "Jan met de pet" het onzin. Bedenk echter dat we de wetenschappelijke en daaruit voortvloeiende technologische vooruitgang voor een belangrijk deel te danken hebben aan fundamenteel onderzoek!

[Verwijderd]

Om er zeker van te zijn dat dit inderdaad de beste ogr is. De voorgestelde is op basis van inzicht en intuitie tot stand gekomen. Door consequent alle mogelijkheden af te gaan, kan pas bewezen worden dat dit inderdaad het geval is.

Dus dat is waarom. Dat de aarde rond was wisten sommigen egyptenaren al, maar pas tijdens de eeuw der ontdekkingen werd dit bewezen. Eigenlijk is dit hetzelfde geval.

[Proxy]

Eerlijk gezegd vind ik het energieverbruik van al de PC's die gebruikt zijn voor dit project, alleen maar om iets te bewijzen wat al bekend was

Het was juist niet bekend of 24/9-24-4-1-59-25-7-11-2-10-39-14-3-44-26-8-40-6-21-15-16-19-22 de kortste liniaal was bij OGR-24, dat is nu echter bewezen.

[Verwijderd]

het was wel bekend, niet bewezen,

het is bekend dat het heelal oneindig groot is, maar nog niemand heeft het bewezen (lijkt me trouwens ook erg lastig)

[Fireshade]

Later bewezen de eerste computers hun nut; in 1972 al werden met behulp van een computer OGR's met negen tot en met elf merktekens bewezen.

en even verder ...

Maar pas toen Sebastian "Pax" Schmitz op 13 oktober 2004 de allerlaatste mogelijkheid had ingeleverd was duidelijk dat het echt de kortste OGR-24 was. De liniaal is dezelfde als die in 1967 werd voorspeld.

dan vraag ik mij af, waarmee toen in 1967 de OGR-24 werd voorspeld. wow voor degenen die dat toen al deden!

[Verwijderd]

OGRs vormen subsets uit andere mathematische reeksen. Sommige van deze reeksen laten zich een stuk makkelijker doorrekenen dan OGRs. Daarnaast is de verwachte lengte van een OGR redelijk gokbaar. De truc is dan met wat geluk en slimheid een reeks te vinden via een minder rekenintensief algorithme met de voorspelde lengte.

In 1967 hadden ze zo een mogelijke GR-24 gevonden, maar er was niet bewezen dat deze Optimaal was en ook niet dat dit de enige OGR-24 was. Dat is nu wel gebeurd.

[Joske Pauwels]

Dus eigenlijk is dit experiment een (heel omslachtige) methode om te bewijzen dat de gok uit 1967 klopte: alle andere mogelijkheden zijn getest en vergeleken. Maar wat als er iemand met zijn cliënt geknoeid heeft, waardoor hij aan d.net rapporteert dat hij x keys heeft gecheckt, maar in werkelijkheid heeft hij ze niet gecontroleerd... En wat als daar toenvallig een nog efficiëntere tussen zat?

Het is natuurlijk een kleine kans, maar als je heel het project dan toch enkel doet om empirisch bewijs te hebben, mag je toch niet zo'n onvolkomenheden hebben?

[Verwijderd]

Die onvolkomenheden zijn er ook niet. Elk te controleren deel is minimaal door 2 verschillende deelnemers gecontroleerd. Dus zelfs als hetzelfde stukje toevallig voor een 2e keer bij dezelfde persoon is komen te liggen, is dat deel voor extra controle weer uitgestuurd totdat het door een andere deelnemer is ingeleverd.

Daarnaast wordt uiteraard nagelopen of beide uitkomsten van de verschillende deelnemers overeenkomen. Zo niet (wat in totaal minder dan 10x is voorgekomen door een fout in een testclient), dan wordt dat stuk ook weer opnieuw uitgegeven.

[Verwijderd]

Daarnaast wordt uiteraard nagelopen of beide uitkomsten van de verschillende deelnemers overeenkomen. Zo niet (wat in totaal minder dan 10x is voorgekomen door een fout in een testclient), dan wordt dat stuk ook weer opnieuw uitgegeven

Voor de volledigheid : de resultaten worden met elkaar vergeleken, en indien er kleine afwijkingen bestaan wordt er een consensus gemaakt. Het kan nl voorvallen dat 2 verschillende architecturen andere resultaten geven die te wijten zijn aan bvb afrondingsfouten/floating point terwijl ze op zich toch correct zijn. (Sommige frameworks voor distributed/grid computing geven dan ook de mogelijkheid de identieke data te verspreiden onder systemen die op het zelfde platform draaien)

[Verwijderd]

Bij andere grid-projecten zou dit inderdaad het geval kunnen zijn; hier is dat echter niet mogelijk aangezien OGR geen gebruik maakt van floating point berekeningen. (Net als het andere d.net project, RC5-72, overigens).
De teruggestuurde berekeningen zijn niet architectuurafhankelijk zolang er geen fouten gemaakt worden in de client

In dit geval hoefde dus ook alleen uitgegaan te worden van 2 identieke resultaten uit 2 verschillende bronnen.

[aTmosh]

Dus eigenlijk is dit experiment een (heel omslachtige) methode om te bewijzen dat de gok uit 1967 klopte

Zo omslachtig is het niet, er is gebruik gemaakt van vrij beschikbare rekencapaciteit. De daarmee gepaard gaande (extra) kosten zijn vrij insignificant als je het over stroomverbruik of voor mijn part broeikaseffecten hebt, de wagenpark van een middelgroot bedrijf om maar wat te noemen weegt daar al tegenop.

En als je het dan over het nut hebt, ja die wagens kunnen een hoop vervoeren, maar de besparing die een optimalere Golomb ruler op kan brengen kan bij toepassing ook in de miljoenen lopen, of net zo goed een berg stroom besparen die weer beter is voor het milieu etc. Eveneens is de kleine investering die je voor zoiets maakt (hoewel in dit geval de echte investering, d.w.z. thuis een PC, al gemaakt is) de zekerheid waard dat je b.v. niet een telescoop park neerzet die X investering en jarenlang Y stroom/ruimte/etc. meer kost dan het had kunnen kosten.

Alleen omdat de meesten het niet interesseert vinden of het niet snappen betekent niet dat dit soort projecten totaal geen nut hebben.

Een interessantere vraag is of dit project meer of minder nut heeft dan een ander, maar dat is soms moeilijk te bepalen omdat veel projecten grondleggend wetenschapelijk werk verrichten die je pas later en veelal indirect (niet duidelijk voor de meesten in ieder geval) terugziet als toepassing.

Je kan ook zeggen dat een bewezen (of betere) OGR straks het menselijke ras redt omdat regering Z op basis van de besparing zich een project kon veroorloven die op den duur (of eerder) een effectieve verdediging tegen catastrofale asteroïde inslagen mogelijk maakte. Voor hetzelfde geld kan als je (al dan niet i.p.v. dit project) aan THINK/Ligandfit meedoet kanker misschien jaren eerder genezen worden. Dan is het moeilijk afwegen, maar je kan in ieder geval niet zeggen dat dit soort projecten nutteloos zijn.

[Adm.Spock]

OGR heeft zeker wel nut. Het is gewoon basaal wetenschappelijk onderzoek. Het directe nut hiervan ligt in specifiek wetenschappelijk onderzoek. Hiervan profiteren dus ook andere DC projecten. Best grappig niet?

[abeker]

Als ik het goed begrijp is een afstand met een OGR ook maar op 1 manier te meten. Lijkt me een welkome aanvulling op de uitleg over OGR.

[Verwijderd]

Als alle maatstrepen op een andere afstand van elkaar staan, dan komt iedere afstand maar één keer voor. Logisch gevolg

Wat betreft OGR's zelf; er zijn vaak meerdere verschillende OGR's met dezelfde lengte.

En een OGR is nooit "alleen"; als alternatief is er altijd nog het spiegelbeeld.

[abeker]

hmmm ja, ik zat te denken aan de afstand tussen twee opeenvolgende meetpunten.

[Verwijderd]

De afstanden van een OGR hoeven niet een sluitende serie te zijn. Rulers waar dit wel het geval is heten Sparse Rulers en zijn in het algemeen langer dan OGR's

[Verwijderd]

Niet juist

Stel ik heb de volgende punten

0,2,5,10

De afstanden tussen 2 punten zijn dan verschillend
(2,3,5) maar de afstand 5 kan ik op twee manieren meten, 0-5 en 5-10.

[Verwijderd]

Jouw voorbeeld is dan ook geen Goulomb Ruler. De afstand tussen 0-5 en 5-10 zijn gelijk.

Het is een voorwaarde voor een goulomb ruler dat alle afstanden onderling verschillen.

[Proxy]

In jouw voorbeeld staan dan ook niet alle maatstrepen op een andere afstand van elkaar. Je geeft het zelf al aan van 0 naar 5 is de afstand hetzelfde als van 5 naar 10.

[satriani]

Het voorbeeld boven klopt gewoon niet, de andere oplossing: 0,3,4,9,11 is wel goed en daar wordt ook niet 2*3 gebruikt voor 6

[Freakertje]

Mag jij mij uitleggen waar je de afstand 10 uithaalt.

Ze missen beide 1 afstand, dus voor mij zijn ze gelijk aan elkaar

[Verwijderd]

Eenvoudiger gezegd is het de kortst mogelijke liniaal met een bepaald aantal punten, waarbij alle maatstrepen op verschillende afstand van elkaar zitten.

Dat is duidelijk. Maar wat kunnen we nu met dit resultaat? In welke sectoren kan deze uitkomst handig zijn? Ik snap het nut van deze jarenlange berekeningen niet, misschien kan iemand dit verduidelijken?

[Verwijderd]

Er staan wat voorbeelden genoemd als radiotechnologie en röntgen-sensor plaatsing.

Eigenlijk komt het erop neer dat het overal interessant kan zijn waar gewerkt wordt met dure apparatuur. Door volgens een OGR opstelling te werken kan het aantal meetpunten (sensoren) geminimaliseerd worden.

Inderdaad niet interessant voor het meetlint in je gereedschapskit waar je maatstreepje nog geen cent kost, maar als je het hebt over tonnen per meetpunt, dan wil je wel minimaliseren!

[gielius]

Dankjewel voor deze uitleg!
Ik vroeg me om 13:39 hetzelfde af maar werd echt heel erg snel weggemodereerd! Het lijkt wel een soort heiligschennis als je bij dit soort projecten vraagt wat het nut ervan is!

[WVL_KsZeN]

Ik mis de 6 in de voorbeeld OGR, of ben ik blind?

[Verwijderd]

Die staat er niet, maar dat hoeft ook niet:

OGR's maken het mogelijk zo veel mogelijk afstanden te meten met een minimum aan meetpunten

(dus niet perse alle tussenliggende waardes ook te meten)

[TranceSetter]

Je kunt er geen 6 uit halen. Die is niet te meten met deze liniaal.

Omdat hij doorgaat tot 11, kunnen er toch 10 afstanden mee gemeten worden

[the_stickie]

schitterend! we maken dus een latje van 11 cm lang en kunnen niet eens meten of iets 6 cm lang is .

Ik heb nog een voorstel voor een optimale lat:
0-1-2-3-4-5-6-7-8-9-10
deze is slechts 10 cm lang, en we kunnen er 10 afstanden mee meten, 6cm incluis
lijkt mij een btere lat toch

btw: weet er eigenlijk iemand wat het nut is van deze incomplete optimale latten?

[pstalman]

0 - 4 = 4?
en 9-11 = 2 en samen 6 of begrijp ik helemaal niet het doel van dit gedoe... ? lijkt me wat ik vroeger had met logistiek lessen.

[gielius]

hieperdepiep ! echt Kikkuh! kei gaaf!

eeeuummm maar wat is het directe nut hiervan?

[CowArt]

eeeuummm maar wat is het directe nut hiervan?

[quote]Juist de eigenschap dat met zo min mogelijk meetpunten zo veel mogelijk afstanden gemeten kunnen worden, maken OGR's interessant voor toepassing in bijvoorbeeld radiotechnologie, sensorplaatsing en röntgenapparatuur.[quote]

[gielius]

Hoe dan? want dat had ik ook al gelezen...

[wdelange]

Even wat zoeken met Google: http://encyclopedia.thefreedictionary.com/Optimal%20Golomb%20ruler
Als je met de muis over de Phased Array gaat, krijg je een redelijk duidelijk antwoord.
In de radiotelescopie is het soms handig om twee schotelantennes op verschillende afstanden te combineren om signalen te vesterken of te onderdrukken. Als je een OGR gebruikt, krijg je met een zo weinig mogelijk aantal antennes ( en die zijn duur ) een zo groot aantal mogelijk afstanden die je voor signaal vergelijking kunt gebruiken. Denk maar aan het plaatje bij dit artikel.

[the_stickie]

dat hadden we zelf ook kunnen lezen natuurlijk... misshien dat je dan ook nog ff kan uiteggen waarom dat dan zoveel handiger is?

Ik zie de voordelen niet nl

[Verwijderd]

Ik zie het nut ook niet echt, je hebt toch een bepaalde lengte nodig om bepaalde afstanden te meten. (in dit geval 11)

Als je die afstand toch al hebt maakt het niet veel meer uit of je er 10 of 4 meetpunten op zet.

Maar wel stoer dat de nederlandse kracht koetjes het zo goed hebben gedaan ^_^.

[Kevinp]

de mensen die daar aan gewerkt hebben kunnen mooi meehelpen met RC5-72 die hebben het hard nodig.

[surfrider]

Zo ver ik het begrijp kan dit vooral worden gebruikt om antennes te maken die optimaal een aantal verschillende frequenties kunnen ontvangen.
Normaal moet je dat met een antenne adaptation doen, en dat geeft verlies en kost stroom.

[DMP.cc]

uhm waar staat in het bovenstaande voorbeeld de 6? of is dat gewoon 2*3?

[Verwijderd]

Het is niet nodig dat een OGR een sluitende serie afstanden kan meten. Het is voldoende dat alle afstanden verschillend zijn.

[ThunderNet]

0,3,4,9,11
je start bij 3, 6 verder, en je zit op 9
oftewel 9-3 = 6