D.net (lub DCTI) to często używane pośród osób zainteresowanych, skrótowe określenie odnoszące się do organizacji o pełnej nazwie Distributed Computing Technologies Incorporated. DCTI to amerykańska organizacja typu non-profit, co oznacza, że wszelkie pozyskane środki przeznaczane są na realizację nadrzędnego celu, nie są zaś gromadzone i dzielone w ramach generowanego zysku. Nadrzędnym celem istnienia D.net'u (w zgodzie z zamieszczoną przez nich na stronie misją) jest badanie, rozwój, promowanie i wykorzystywanie techniki obliczeń rozproszonych. Określenie obliczenia rozproszone odnosi się do procesu rozkładu złożonych operacji obliczeniowych na mniejsze fragmenty, które to wykonywane są przez odrębne procesory/rdzenie procesora jednego komputera, bądź poprzez wiele komputerów komunikujących się ze sobą za pośrednictwem sieci. Technika ta stosowana jest szczególnie wtedy, gdy obliczenia mają bardzo złożony charakter, a co za tym idzie ich zrealizowanie za pomocą jednego komputera było by bardzo czasochłonne. W rzeczywistości ideę tą wykorzystują wszystkie istniejące superkomputery, które zbudowane są z wielu mniejszych jednostek, połączonych w sieć i rozpoznawanych przez system operacyjny jako jedna wirtualna maszyna. Sieć Internet stworzyła możliwość wykorzystania wielu komputerów, oddalonych od siebie często nawet o setki kilometrów, analogicznie do jednego, zlokalizowanego na miejscu superkomputera. Biorąc pod uwagę fakt, że przeciętny użytkownik komputera na co dzień wykorzystuje znikomy procent mocy obliczeniowej zainstalowanego procesora, istnieje możliwość przeznaczenia części tej mocy w ramach "dotacji", tak aby wspomagała realizację jakiegoś celu. W praktyce wygląda to tak, iż użytkownik pobiera aplikację, która wykorzystuje czas bezczynności procesora na wykonywanie fragmentu zadanych obliczeń. Ponieważ jest to czas bezczynności, to użytkownik nie zauważa żadnej różnicy w wydajności sprzętu - przykładowo powiedzmy, że uruchomiony jedynie odtwarzacz muzyki zużywa zaledwie 1 % mocy obliczeniowej procesora, co oznacza, że 99 % jest niewykorzystywane i użyte zostanie przez program do obliczeń rozproszonych, kiedy jednak zostanie uruchomiona gra wymagająca aż 95 % mocy obliczeniowej procesora, to dla obliczeń rozproszonych pozostanie jedynie 5 % możliwości procesora.

Aktualnie w Internecie prowadzony jest szereg przeróżnych projektów wykorzystujących tę ideę. Najpopularniejsze z nich to z pewnością SETI@home - analiza kosmicznego szumu radiowego pozyskiwanego z radiotelekopu w poszukiwaniu sygnałów mogących pochodzić od pozaziemskich cywilizacji, oraz Folding@home - badający na drodze symulacji procesy zwijania białek, co może prowadzić do opracowania sposobów zapobiegania i leczenia różnych chorób jak np. choroba Alzheimera, choroba Parkinsona czy BSE. Ilość projektów jest naprawdę duża, stąd zainteresowanych odsyłam tutaj. No i jest oczywiście jeszcze D.net... D.net to najstarsza działająca organizacja tego typu. Różnorakie projekty wykorzystujące obliczenia rozproszone prowadzone są przez nich już od 1997 roku. Jednak tradycja to nie wszystko, liczę że być może po przeczytaniu tego tekstu zainteresuje Cię jeden z prowadzonych przez nich obecnie projektów, opisanych przeze mnie poniżej. A jeśli nawet nie, to być może zainteresowany samą ideę obliczeń rozproszonych i "dotacji" części mocy obliczeniowej własnego sprzętu, dołączysz do innego z projektów, np. jednego z tych, które wymieniałem wcześniej. A jeśli i to Cię nie skusi, to z pewnością powiększysz swoją wiedzę komputerową o kolejne zagadnienie. Słowem - i tak przeczytanie tego artykułu powinno ostatecznie skutkować jakąś korzyścią dla Ciebie :).

Obecnie D.net organizuje i koordynuje dwa opisane poniżej projekty. Przedsięwzięcie to składa się z szeregu mniejszych projektów realizowanych kolejno. Miejsce xx w nazwie projektu stanowią dwie cyfry nawiązujące do długości klucza, ale o tym za chwilę. Obecnie trwa projekt RC5-72.

RC5 jest jednym z algorytmów wykorzystywanych do szyfrowania poufnych danych. Aby zrozumieć jego znaczenie należy przyjrzeć się nieco historii. W roku 1976 Agencja Bezpieczeństwa Wewnętrznego Stanów Zjednoczonych Ameryki uznała za wystarczająco bezpieczny do szyfrowania istotnych danych (w tym danych osobowych), które mają być przechowywane przez lata, inny algorytm szyfrujący nazywany DES (Data Encryption Standard). Algorytm ten wykorzystywany był przez wiele lat, jednak jak się okazało, ze zwiększającą się mocą obliczeniową dostępną dla typowych użytkowników, dane zaszyfrowane z użyciem algorytmu DES stawały się coraz łatwiejsze do odszyfrowania przez niepowołane osoby. W roku 1999 zdecydowano się na zaprzestanie stosowania algorytmu DES i zastąpienie go bezpieczniejszym algorytmem. Do konkursu mającego wyłonić najlepszy z nich stanęła między innymi firma RSA Security. Posiada ona patent na algorytm RC5. Aby udowodnić jego bezpieczeństwo ogłosiła ona własny konkurs, którego celem było odszyfrowanie wiadomości zaszyfrowanej tym algorytmem. Znając długość zastosowanego klucza (swojego rodzaju "hasła" użytego podczas szyfrowania) należało pokonać zabezpieczenie używając metody brute-force. Metoda ta polega na sprawdzeniu kolejno wszystkich możliwych kombinacji kluczy. Zakładając dla uproszczenia, że klucz ma postać trzech liter, najpierw sprawdzane jest hasło "aaa", potem "aba", "aca" i tak dalej, aż do znalezienia właściwego. D.net podjął to wyzwanie i w efekcie nie tylko złamał zabezpieczenie wykorzystujące algorytm RC5-56 (wykorzystujący klucz 56-bitowy, takiej samej długości jak długość klucza algorytmu DES) w 212 dni, ale także używające algorytmu DESII-56 mającego być udoskonaloną wersją algorytmu DES (w 8 dni). Zgodnie z obietnicą firma RSA Security wypłaciła 10000 $ nagrody dla D.net'u, z czego w zgodzie ze wcześniejszymi ustaleniami 8000 $ przeznaczone zostało na cele charytatywne. Jak skończyła się historia algorytmu RC5? Otóż RSA Security uznając go za zbyt mało skuteczny opracowała jego udoskonaloną wersję nazwaną RC6, którą to ostatecznie zgłoszono jako kandydata do rządowego konkursu. Ostatecznie jednak wygrał inny algorytm nazywany roboczo Rijndael, a po zatwierdzeniu w 2001 przez agencje rządowe USA nazwany wreszcie AES (Advanced Encryption Standard).

D.net nie zakończył jednak walki. RSA Security zaplanowało bowiem oryginalnie szereg wyzwań wiążących się ze stosowaniem coraz to dłuższego klucza używanego w algorytmie RC5, w tym m.in. RC5-64 (klucz 64-bitowy, złamany po 1757 dniach) oraz RC5-72. Warto zauważyć, że algorytm RC5-64 posiada aż 256 razy większą liczbę dostępnych kombinacji kluczy, a mimo to jego pokonanie zajęło jedynie 8 razy więcej czasu niż algorytmu RC5-56. Wyraźnie pokazuje to ogromny wzrost możliwości obliczeniowej dostępnych w tym okresie komputerów. Obecnie D.net mierzy się z algorytmem RC5-72, który to posiada aż 4722366482869645213696 kombinacji możliwych kluczy. Jest więc teoretycznie 65536 razy trudniejszy do złamania metodą brute-force niż RC5-56. Niestety RSA Security po zmianie zarządu, w roku 2007 zrezygnowała z organizacji konkursu związanego z algorytmem RC5, a co za tym idzie nawet w przypadku odnalezienia właściwego klucza obiecana nagroda (10000 $) nie zostanie wypłacona jak to miało w przypadku RC5-56 i RC5-64. Niemniej D.net nie poddał się i uznając to za sprawę honoru sam zasponsorował nagrodę ze zgromadzonych wcześniej środków. W zgodzie ze wcześniejszymi ustaleniami, ponownie 8000 $ otrzyma organizacja charytatywna wybrana w drodze głosowania, 1000 $ osoba odnajdująca właściwy klucz i ostatnie 1000 $ jej drużyna (o tym więcej w nieco dalszej części).

Nasuwa się jednak pytanie: skąd właściwie wiadomo, że znaleziono właściwy klucz? Otóż RSA Security w zgodzie z pierwotnym zamiarem wykorzystania algorytmu RC5 założyło, że pewna część deszyfrowanego fragmentu tekstu będzie znana. Założenie to wynika z faktu, iż gdyby stosowano go do szyfrowania np. danych osobowych, to pewna znana część tekstu zawsze powtarzała by się w zaszyfrowanym tekście, np. słowo "nazwisko". Stąd osoba łamiąca zabezpieczenie, zakładając istnie pewnego znanego fragmentu tekstu mogła by rozpoznać odnalezienie właściwego klucza metodą brute-force. W przypadku konkursu organizowanego przez RSA Security zapowiedziano, że poprawnie zdeszyfrowany fragment teksu rozpocznie się ciągiem znaków "The unknown message is:". Stąd, aplikacja sprawdzająca po stronie użytkownika klucze, testuje czy pierwsza litera odszyfrowanego danym kluczem tekstu to "T", a jeśli tak to czy druga to "h" itd. W rzeczywistości deszyfrowane jest jedynie zawsze 8 pierwszych liter tekstu, ponieważ specyfika algorytmu RC5 sprawia, że litery te w wynikowych, zaszyfrowanych wcześniej danych są w pewien sposób powiązane ze sobą (to tak naprawdę nieco bardziej skomplikowane: nie da się odszyfrować litery numer 1 bez znajomości litery numer 2, litery numer 2 bez znajomości litery numer 3 itd. aż do litery na miejscu numer 8 - choć jest to nadal uproszczenie, chodzi tak naprawdę o wzajemną zależność kolejnych bitów w paczce wielkości 64 bitów, tzw. bloku szyfru - każde z 8 bitów daje 256 możliwych kombinacji co może oznaczać jeden z 256 predefiniowanych w standardzie ASCII znaków, w tym liter). I rzeczywiście wiadomość zaszyfrowana kluczem o długości 56 bitów brzmiała "The unknown message is: It's time to move to a longer key length", zaś kluczem 64-bitowym - "The unknown message is: Some things are better left unread". Ponadto klucze nie mają postaci alfanumerycznej, są to po prostu kolejne kombinacje bitów (określonej długości, w zależności od wariantu algorytmu) zapisywane dla zaoszczędzenia miejsca w formie szesnastkowej. Przykładowo zwycięski klucz dla projektu RC5-64 miał postać "63DE7DC154F4D039" co daje rzeczywistą kombinację bitów "0110001111011110011111011100000101010100111101001101000000111001" (jak widać faktycznie jest ich 64, a więc łączna ilość dopuszczalnych kombinacji wynosiła 2 do potęgi 64, czyli 18446744073709551616). Można by również określić go mianem klucza numer 7196327523892121657, ale jak widać zapis heksadecymalny jest o wiele krótszy. Projekt OGR ma zdecydowanie inny charakter. Jego celem jest odnajdywanie tzw. optymalnych miar Golomba. Miara Golomba to specyficzny twór matematyczny nazwany na cześć amerykańskiego matematyka Solomona Golomba. Drobną ciekawostkę stanowi fakt, iż jest to także autor układanki logicznej Polyomino stanowiącej inspirację dla twórcy gry Tetris, ale to już zupełnie inna historia... Czym jest cała ta miara Golomba? Matematyczna definicja jest dosyć zawiła i w uproszczeniu określa ją jako zbiór liczb całkowitych, które umieszczone na wyimaginowanej skali utworzą miarę, na której odległość pomiędzy każdą dowolnie wybraną parą spośród umieszczonych na skali liczb będzie unikalna. Łatwiej pokazać to na rysunku. Powyższy rysunek ilustruje miarę Golomba utworzoną z liczb: 0, 1, 4 i 6. Jeśli obliczymy różnicę każdej kombinacji dwóch liczb użytych do stworzenia tej miary to otrzymana zostanie unikalna wartość jaką można nią "zmierzyć". Oznacza to, że liczby te rzeczywiście tworzą miarę Golomba. Jeżeli byśmy utworzyli linijkę z oznaczoną działką na 0, 1, 4 i 6 cm to udało by się nam nią zmierzyć odległość wynoszącą: 1, 2, 3, 4, 5 i 6 cm, co ilustruje rysunek. Miara Golomba określana jest ponadto dwiema liczbami. Rząd (tutaj 4) informuje o ilości liczb użytych do jej stworzenia, zaś długość (tutaj 6) to różnica między ostatnią i pierwszą liczbą. Użyte liczby nie mają żadnego znaczenia - jeśli dodamy do każdej z nich tą samą wielkość, np. 1000 i uzyskamy 1000, 1001, 1004 i 1006 to nadal otrzymamy miarę Golomba rzędu 4 o długości 6. Z tego względu najczęściej operuje się odległością pomiędzy kolejnymi "działkami", stąd w obydwu przypadkach miarę tę można określić jako 1-3-2 (można to szybko przeliczyć: 1 - 0 = 1, 4 - 1 = 3 oraz 6 - 4 = 2).

Wiemy czym jest już miara Golomba. Istnieją jednak także miary optymalne i doskonałe. Miara optymalna to taka, która jest najkrótsza dla danego rzędu - przykładowo dla rzędu 4 (czyli przy użyciu 4 liczb) nie da się utworzyć miary Golomba krótszej niż 6 (czyli gdzie różnica między ostatnią i pierwszą liczbą wynosi 6). Miara doskonała to taka, którą można "zmierzyć" wszystkie możliwe odległości, aż do jej długości. Tak więc miara 1-3-2 jest i doskonała i optymalna. Okazuje się, że istnieją miary doskonałe, które są jednocześnie optymalnymi tylko do rzędu 4. Obecnie znane są miary różnego rzędu, do około 150.

D.net stara się odnaleźć optymalne miary Golomba danego rzędu. Tak więc projekt OGR-xx stanowi edycję poszukującą optymalnej miary Golomba (OGR - Optimal Golomb Ruler) rzędu xx. D.net pomyślnie zakończył projekty: OGR-20, OGR-21, OGR-22, OGR-23, OGR-24, OGR-25 i OGR-26. Obecnie trwają poszukiwania optymalnej miary Golomba rzędu 27 (czyli projekt OGR-27).

Po co to wszystko? Otóż miary Golomba znajdują szerokie zastosowanie w technice, w tym w informatyce (w kodach wykrywania i korekcji błędów ECC), inżynierii materiałowej (krystalografia z wykorzystaniem promieniowania X) czy telekomunikacji (kształt i rozmieszczenie anten radiowych). Słowem, pomagając w poszukiwaniu takich tworów jak OGR przyczynami się dla dobra nauki :).

A więc zdecydowałeś dołączyć do jednego z projektów D.net'u? Nic prostszego. Wystarczy pobrać mały program, tzw. klienta, który będzie komunikował się z serwerami D.net'u i wymieniał okresowo dane na temat zakresu prac, jakie ma realizować w tle. Adres do pobrania poniżej. Jeżeli decydujesz się tylko na udział w projekcie RC5-72 lepszy będzie klient GPU - wykorzystujący do swoich celów procesor karty graficznej, co daje w tym przypadku o wiele lepsze rezultaty. Jeśli chcesz brać udział zarówno w projekcie RC5-72 jak i OGR-27 (albo tylko w OGR-27) to pobierz klienta CPU - wykorzystującego główny procesor komputera, co daje możliwość wykorzystania go do obliczeń na potrzeby projektu OGR. Instalacja nie powinna sprawić nikomu problemu. Odbywa się ona automatycznie. Podczas tego procesu należy podać adres e-mail, który używany będzie w systemie statystyk (o tym nieco później). Klient uruchamia się automatycznie podczas każdego startu systemu operacyjnego, a jego obecność sygnalizuje ikonka krowiej głowy (symbol D.net'u) znajdująca się w Zasobniku systemowym. Dwuklik na niej otwiera główne okno programu. Poniżej przedstawiony został interfejs aplikacji (kliknij aby powiększyć, zrzuty ekranu pochodzą bezpośrednio z mojego głównego sprzętu, stąd specyficzna - odmienna od typowej - czcionka i  kolorystyka okien). Wybierając z menu pozycję Client > Configure przechodzi się do dialogu konfiguracji aplikacji (patrz pierwszy z powyższych zrzutów ekranu). Wpisując liczbę znajdującą się obok danej pozycji menu, przechodzi się do kolejnego podmenu. Wpisując liczbę 0, powraca się do poprzedniego menu. Najważniejsze opcje, które warto zmodyfikować opisałem w poniższych podpunktach.

• General client options > Your email address - tutaj należy podać własny adres e-mail o ile nie zrobiliśmy tego przy instalacji.
• General client options > Crunch-o-meter - metoda prezentacji przetwarzania danego bloku, dla projektu RC5 najlepiej wybrać Relative (pasek postępu), zaś dla projektu OGR lub obydwu Live-rate (aktualna prędkość obliczeń).
• Buffer and buffer update options > Work-load precedence - umożliwia wybór projektu w jakim chcemy uczestniczyć, przykładowo aby wyłączyć pobieranie pakietów przeznaczonych dla RC5-72 należy wpisać RC5-72=0.
• Buffer and buffer update options > Fetch work threshold - pobierane do obrobienia dane podzielone są na bloki. Przykładowo dla projektu RC5-72 każdy blok to porcja kluczy jakie przetestuje klient w ilości 2 do potęgi 32, czyli 4294967296 sztuki. Ponieważ aktualnie procesory są bardzo szybkie i potrafią w ciągu sekundy przetestować nawet kilka miliardów kluczy, bloki łączone są w większą ilość zwaną pakietami. W to pole należy wpisać ilość bloków po ukończeniu której klient poinformuje serwer D.net'u o ukończeniu pracy i otrzyma kolejne bloki. Dla szybkiej karty graficznej polecam tu wpisać np. RC5-72=1000.
• Buffer and buffer update options > Preffered packet size - preferowana wielkość pakietu. Od tej wartości zależy ilość danych wymienianych z serwerami D.net'u. Dla przytaczanej wcześniej szybkiej karty graficznej polecam RC5-72=100, taka kombinacja oznacza, że klient łącząc się z serwerem postara się pobrać 1000 bloków podzielone na 10 pakietów, z których każdy zawiera 100 bloków. Im większy rozmiar pakietów, tym mniej musi zostać ich pobranych z serwera - najlepiej dobrać tą wartość eksperymentalnie, tak aby łączność z serwerem następowała rzadko, np. raz, dwa razy na dzień. Czasem serwer przydziela pakiety o innej ilości bloków niż przez nas wybrana, tak więc przy przytaczanej konfiguracji czasem otrzymać można np. nadal 1000 bloków ale w postaci 70 pakietów po 10 bloków i 3 po 100 bloków. Wynika to z faktu, że serwer spodziewa się po pewnym czasie od wysłania bloków do klienta otrzymać informację zwrotną o ich przetestowaniu. Jeśli tak się nie stanie, bloki te otrzymuje ponownie inny klient. Składając pakiety z nowych, niesprawdzonych jeszcze bloków kluczy tworzone są jak największe pakiety (nieprzekraczające jednak zawierające 100 bloków), kiedy zaś serwer przesyła ponownie niesprawdzone bloki składa z nich mniejsze pakiety aby jak najszybciej otrzymać je z powrotem i oznaczyć jako sprawdzone.
• Performance related options > Number of crunchers to run simultaneously - ilość rdzeni procesora/ilość procesorów jakie mają być jednocześnie wykorzystywane przez klienta.

Dostępne są dwa tryby pracy klienta - tekstowy i graficzny. Tryb tekstowy jest domyślnym trybem pracy znanym ze starszych wersji klienta. W oknie (parz drugi z powyższych zrzutów ekranu) prezentowany jest szereg, stale zmieniających się komunikatów. Kolejno od góry są to: wersja klienta, identyfikator użytkownika; a następnie cyklicznie powtarzają się: numer aktualnego pakietu, ilość bloków zawartych w danym pakiecie, ilość pakietów (i w nawiasie bloków) ukończona od czasie uruchomienie klienta, czas od uruchomienia klienta, średnia prędkość podawana w milionach kluczy na sekundę dla RC5 lub miliardach gałęzi drzewa dostępnych kombinacji działek na sekundę dla OGR, ilość pakietów (i w nawiasie bloków) pozostałych do obrobienia od ostatniego kontaktu z serwerem, ilość pakietów (i w nawiasie bloków) przetworzonych od ostatniego kontaktu z serwerem i wreszcie na samym końcu uaktualniany na bieżąco pasek postępu symbolizujący postęp przetwarzania aktualnego pakietu (dla RC5) lub prędkość obliczeń (dla OGR) - w przypadku projektów z serii OGR zawartość poszczególnych bloków jest zmienna i trudno wyświetlić liniowy postęp operacji ich przetwarzania.

W trybie graficznym (patrz trzeci zrzut ekranu powyżej) wyświetlane są te same dane co w trybie tekstowym, a oprócz tego wykres informujący o zmieniającej się w czasie prędkości przetwarzania pakietów. W tryb graficzny przechodzi się wybierając z menu polecenie View > Core throughput.

Po około dwóch dniach od odesłania pierwszych przetworzonych pakietów użytkownicy zostają włączeni do systemu statystyk. Łącze znajduje się poniżej. Jak już wspominałem klienty identyfikowane są na podstawie wprowadzonego w konfiguracji adresu e-mail. Przykładowo dla projektu RC5-72 na osobistej podstronie statystyk znaleźć można takie informacje jak kolejno: pozycja w rankingu uczestników, ilość odesłanych bloków, ilość przetwarzanych bloków na sekundę, ilość sprawdzonych kluczy, ilość sprawdzanych kluczy na sekundę, łączny czas pracy oraz prawdopodobieństwo odnalezienia właściwego klucza zanim zrobią to inni uczestnicy. Wszystkie statystki dostępne są zarówno dla dnia poprzedniego jak i łącznego czasu pracy. Dostępna jest także historia obrazująca ilość bloków odsyłanych w kolejnych dniach. Statystyki odświeżane są raz dziennie. Podobno człowiek to zwierze stadne. Być może z tego względu w projektach D.net'u umożliwiona została wzajemna rywalizacja w grupach nazywanych drużynami. Na osobistej podstronie systemu statystyk znajduje się opcja umożliwiająca przesłanie na wskazany w konfiguracji klienta adres e-mail specjalnego hasła. Hasło to umożliwia zalogowanie się do systemu statystyk, a co za tym idzie zmianę kilku opcji związanych m.in. z wyświetlaniem naszego adresu e-mail w statystykach, wyglądu osobistej podstrony statystyk itp. Będąc zalogowanym do systemu statystyk i znajdując się na podstronie jednej z drużyn (łącze poniżej) możliwe jest użycie opcji powodującej dołączenie do danej drużyny. Od tego czasu przetworzone bloki będą wliczane nie tylko do naszych statystyk ale także do statystyk wybranej drużyny.  

• Oficjalna strona D.net'u
• System statystyk
• Statystyki łączne dla projektu RC5-72
• Statystyki uczestników projektu RC5-72
• Statystyki drużyn dla projektu RC5-72
• Moje osobiste statystyki uczestnictwa w projekcie RC5-72
• Więcej informacji dotyczących algorytmu RC5
• Więcej informacji dotyczących optymalnej miary Golomba
• Program mojego autorstwa rozszerzający możliwości klienta D.net'u
• Zestaw tapet związanych z projektami D.net'u