Obliczenia rozproszone - Distributed computing
Obliczenia rozproszone to dziedzina informatyki zajmująca się badaniem systemów rozproszonych. System rozproszony to system, którego komponenty znajdują się na różnych komputerach w sieci , które komunikują się i koordynują swoje działania poprzez przekazywanie sobie nawzajem wiadomości z dowolnego systemu. Komponenty współdziałają ze sobą, aby osiągnąć wspólny cel. Trzy istotne cechy systemów rozproszonych to: współbieżność komponentów, brak zegara globalnego oraz niezależna awaria komponentów. Zajmuje się centralnym wyzwaniem polegającym na tym, że awaria elementów systemu nie oznacza awarii całego systemu. Przykłady systemów rozproszonych różnią się od systemów opartych na architekturze SOA do gier Massively Multiplayer Online do sieci peer-to-peer .
Program komputerowy działający w systemie rozproszonym nazywany jest programem rozproszonym (a programowanie rozproszone to proces pisania takich programów). Istnieje wiele różnych typów implementacji mechanizmu przekazywania komunikatów, w tym czysty HTTP, łączniki typu RPC i kolejki komunikatów .
Przetwarzanie rozproszone odnosi się również do wykorzystania systemów rozproszonych do rozwiązywania problemów obliczeniowych. W obliczeniach rozproszonych problem jest podzielony na wiele zadań, z których każde jest rozwiązywane przez jeden lub więcej komputerów, które komunikują się ze sobą poprzez przekazywanie wiadomości.
Wstęp
Słowo „ rozproszony” w terminach takich jak „system rozproszony”, „programowanie rozproszone” i „ algorytm rozproszony ” pierwotnie odnosiło się do sieci komputerowych, w których poszczególne komputery były fizycznie rozmieszczone na pewnym obszarze geograficznym. Terminy te są obecnie używane w znacznie szerszym sensie, odnosząc się nawet do autonomicznych procesów, które działają na tym samym fizycznym komputerze i współdziałają ze sobą poprzez przekazywanie wiadomości.
Chociaż nie ma jednej definicji systemu rozproszonego, następujące właściwości definiujące są powszechnie używane jako:
- Istnieje kilka autonomicznych jednostek obliczeniowych ( komputerów lub węzłów ), z których każda ma własną pamięć lokalną .
- Jednostki komunikują się ze sobą poprzez przekazywanie wiadomości .
System rozproszony może mieć wspólny cel, taki jak rozwiązanie dużego problemu obliczeniowego; użytkownik postrzega wówczas zbiór autonomicznych procesorów jako całość. Alternatywnie, każdy komputer może mieć własnego użytkownika z indywidualnymi potrzebami, a celem systemu rozproszonego jest koordynacja wykorzystania współdzielonych zasobów lub świadczenie usług komunikacyjnych dla użytkowników.
Inne typowe właściwości systemów rozproszonych to:
- System musi tolerować awarie poszczególnych komputerów.
- Struktura systemu (topologia sieci, opóźnienie sieci, liczba komputerów) nie jest z góry znana, system może składać się z różnych rodzajów komputerów i łączy sieciowych, a system może się zmieniać podczas wykonywania rozproszonego programu.
- Każdy komputer ma tylko ograniczony, niepełny widok systemu. Każdy komputer może znać tylko jedną część danych wejściowych.
Obliczenia równoległe i rozproszone
Systemy rozproszone to grupy komputerów połączonych w sieć, które mają wspólny cel swojej pracy. Terminy „ przetwarzanie współbieżne ”, „ przetwarzanie równoległe ” i „przetwarzanie rozproszone” w dużym stopniu się pokrywają i nie ma między nimi wyraźnego rozróżnienia. Ten sam system można scharakteryzować zarówno jako „równoległy”, jak i „rozproszony”; procesory w typowym systemie rozproszonym działają równolegle. Przetwarzanie równoległe może być postrzegane jako szczególnie ściśle powiązana forma przetwarzania rozproszonego, a przetwarzanie rozproszone może być postrzegane jako luźno powiązana forma przetwarzania równoległego. Niemniej jednak można z grubsza sklasyfikować systemy współbieżne jako „równoległe” lub „rozproszone” przy użyciu następujących kryteriów:
- W obliczeniach równoległych wszystkie procesory mogą mieć dostęp do pamięci współdzielonej w celu wymiany informacji między procesorami.
- W obliczeniach rozproszonych każdy procesor ma swoją własną pamięć prywatną ( pamięć rozproszona ). Wymiana informacji odbywa się poprzez przekazywanie komunikatów między procesorami.
Rysunek po prawej ilustruje różnicę między systemami rozproszonymi i równoległymi. Rysunek (a) jest schematycznym widokiem typowego systemu rozproszonego; system jest reprezentowany jako topologia sieci, w której każdy węzeł jest komputerem, a każda linia łącząca węzły jest łączem komunikacyjnym. Rysunek (b) przedstawia bardziej szczegółowo ten sam system rozproszony: każdy komputer ma własną pamięć lokalną, a wymiana informacji może odbywać się tylko poprzez przekazywanie komunikatów z jednego węzła do drugiego przy użyciu dostępnych łączy komunikacyjnych. Rysunek (c) przedstawia system równoległy, w którym każdy procesor ma bezpośredni dostęp do pamięci współdzielonej.
Sytuacja komplikuje się jeszcze bardziej tradycyjnych zastosowań warunków równoległych i rozproszonych algorytm , który nie dość dopasować powyższe definicje rozmieszczonych równolegle i systemów (patrz poniżej na bardziej szczegółowe omówienie). Niemniej jednak, z reguły, obliczenia równoległe o wysokiej wydajności w wieloprocesorach ze współużytkowaną pamięcią wykorzystują algorytmy równoległe, podczas gdy koordynacja wielkoskalowego systemu rozproszonego wykorzystuje algorytmy rozproszone.
Historia
Wykorzystanie procesów współbieżnych, które komunikują się poprzez przekazywanie komunikatów, ma swoje korzenie w architekturach systemów operacyjnych badanych w latach 60. XX wieku. Pierwszymi rozpowszechnionymi systemami rozproszonymi były sieci lokalne, takie jak Ethernet , który został wynaleziony w latach 70. XX wieku.
ARPANET , jeden z poprzedników Internetu , został wprowadzony pod koniec lat sześćdziesiątych, a poczta e-mail ARPANET została wynaleziona na początku lat siedemdziesiątych. Poczta elektroniczna stała się najbardziej udaną aplikacją ARPANET i jest prawdopodobnie najwcześniejszym przykładem aplikacji rozproszonej na dużą skalę . Oprócz ARPANET (i jego następcy, globalnego Internetu), inne wczesne światowe sieci komputerowe obejmowały Usenet i FidoNet z lat 80., które były używane do obsługi rozproszonych systemów dyskusyjnych.
Badania nad przetwarzaniem rozproszonym stały się osobną gałęzią informatyki na przełomie lat 70. i 80. XX wieku. Pierwsza konferencja w tej dziedzinie, Symposium on Principles of Distributed Computing (PODC), rozpoczęła się w 1982 roku, a jej odpowiednik International Symposium on Distributed Computing (DISC) po raz pierwszy odbyło się w Ottawie w 1985 roku jako Międzynarodowe Warsztaty Algorytmów Rozproszonych na Grafach.
Architektury
Do przetwarzania rozproszonego wykorzystywane są różne architektury sprzętowe i programowe. Na niższym poziomie konieczne jest połączenie wielu procesorów z jakimś rodzajem sieci, niezależnie od tego, czy ta sieć jest wydrukowana na płytce drukowanej, czy składa się z luźno połączonych urządzeń i kabli. Na wyższym poziomie konieczne jest połączenie procesów działających na tych procesorach z jakimś systemem komunikacyjnym .
Programowanie rozproszone zwykle należy do jednej z kilku podstawowych architektur: klient-serwer , trójwarstwowa , n- warstwowa lub równorzędna ; lub kategorie: luźne sprzężenie lub ciasne sprzężenie .
- Klient–serwer : architektury, w których inteligentni klienci kontaktują się z serwerem w celu uzyskania danych, a następnie formatują je i wyświetlają użytkownikom. Dane wejściowe na kliencie są przekazywane z powrotem do serwera, gdy stanowią trwałą zmianę.
- Trójwarstwowa : architektury, które przenoszą inteligencję klienta do warstwy środkowej, aby można było używać klientów bezstanowych . Upraszcza to wdrażanie aplikacji. Większość aplikacji internetowych jest trójwarstwowych.
- n -tier : architektury, które zwykle odnoszą się do aplikacji internetowych, które dalej przekazują swoje żądania do innych usług korporacyjnych. Ten typ aplikacji jest najbardziej odpowiedzialny za sukces serwerów aplikacji .
- Peer-to-peer : architektury, w których nie ma specjalnych maszyn, które świadczą usługi lub zarządzają zasobami sieciowymi. Zamiast tego wszystkie obowiązki są jednolicie podzielone między wszystkie maszyny, znane jako peery. Peery mogą służyć zarówno jako klienci, jak i jako serwery. Przykładami tej architektury są BitTorrent i sieć bitcoin .
Kolejnym podstawowym aspektem rozproszonej architektury obliczeniowej jest sposób komunikowania się i koordynowania pracy pomiędzy współbieżnymi procesami. Poprzez różne protokoły przekazywania wiadomości procesy mogą komunikować się bezpośrednio ze sobą, zwykle w relacji master/slave . Alternatywnie, architektura „zorientowana na bazę danych” może umożliwiać przetwarzanie rozproszone bez jakiejkolwiek formy bezpośredniej komunikacji między procesami , dzięki wykorzystaniu wspólnej bazy danych . Architektura zorientowana na bazę danych zapewnia w szczególności analizę przetwarzania relacyjnego w architekturze schematycznej, która pozwala na przekazywanie na żywo środowiska. Umożliwia to wykonywanie funkcji przetwarzania rozproszonego zarówno w obrębie, jak i poza parametrami sieciowej bazy danych.
Aplikacje
Przyczyny korzystania z systemów rozproszonych i przetwarzania rozproszonego mogą obejmować:
- Sam charakter aplikacji może wymagać użycia sieci komunikacyjnej, która łączy kilka komputerów: na przykład dane wytwarzane w jednej fizycznej lokalizacji i wymagane w innej lokalizacji.
- Istnieje wiele przypadków, w których użycie jednego komputera byłoby w zasadzie możliwe, ale wykorzystanie systemu rozproszonego jest korzystne ze względów praktycznych. Na przykład bardziej opłacalne może być uzyskanie pożądanego poziomu wydajności przy użyciu klastra kilku komputerów o niższej klasie w porównaniu z jednym komputerem klasy wyższej. System rozproszony może zapewnić większą niezawodność niż system nierozproszony, ponieważ nie ma pojedynczego punktu awarii . Co więcej, system rozproszony może być łatwiejszy w rozbudowie i zarządzaniu niż monolityczny system jednoprocesorowy.
Przykłady
Przykłady systemów rozproszonych i zastosowań przetwarzania rozproszonego obejmują:
-
sieci telekomunikacyjne :
- sieci telefoniczne i komórkowe ,
- sieci komputerowe takie jak Internet ,
- bezprzewodowe sieci czujników ,
- algorytmy routingu ;
- aplikacje sieciowe:
- World Wide Web i sieci peer-to-peer ,
- gry online masowo wieloosobowe i społeczności wirtualnej rzeczywistości ,
- rozproszone bazy danych i rozproszone systemy zarządzania bazami danych ,
- sieciowe systemy plików ,
- rozproszona pamięć podręczna, taka jak bufory burst ,
- rozproszone systemy przetwarzania informacji, takie jak systemy bankowe i systemy rezerwacji linii lotniczych;
- kontrola procesu w czasie rzeczywistym:
- systemy sterowania samolotami ,
- przemysłowe systemy sterowania ;
-
obliczenia równoległe :
- obliczenia naukowe , w tym klastrów obliczeniowych , sieci komputerowych , cloud computing i różnych wolontariat obliczeniowy projektów (zobacz listę projektów rozproszonych komputerowych ),
- renderowanie rozproszone w grafice komputerowej.
Podstawy teoretyczne
Modele
Wiele zadań, które chcielibyśmy zautomatyzować za pomocą komputera, ma charakter typu pytanie–odpowiedź: chcielibyśmy zadać pytanie, a komputer powinien udzielić odpowiedzi. W informatyce teoretycznej takie zadania nazywa się problemami obliczeniowymi . Formalnie problem obliczeniowy składa się z instancji wraz z rozwiązaniem dla każdej instancji. Instancje to pytania, które możemy zadać, a rozwiązania są pożądanymi odpowiedziami na te pytania.
Informatyka teoretyczna stara się zrozumieć, które problemy obliczeniowe można rozwiązać za pomocą komputera ( teoria obliczalności ) i jak wydajnie ( teoria złożoności obliczeniowej ). Tradycyjnie mówi się, że problem można rozwiązać za pomocą komputera, jeśli potrafimy zaprojektować algorytm, który zapewni prawidłowe rozwiązanie dla dowolnej instancji. Taki algorytm może być zaimplementowany jako program komputerowy działający na komputerze ogólnego przeznaczenia: program odczytuje instancję problemu z input , wykonuje pewne obliczenia i generuje rozwiązanie jako wyjście . Formalizmy, takie jak maszyny o swobodnym dostępie lub uniwersalne maszyny Turinga, mogą być wykorzystane jako abstrakcyjne modele sekwencyjnego komputera ogólnego przeznaczenia wykonującego taki algorytm.
W dziedzinie obliczeń współbieżnych i rozproszonych podobne pytania dotyczą albo wielu komputerów, albo komputera realizującego sieć współdziałających ze sobą procesów: jakie problemy obliczeniowe można rozwiązać w takiej sieci i jak wydajnie? Nie jest jednak wcale oczywiste, co należy rozumieć przez „rozwiązywanie problemu” w przypadku systemu współbieżnego lub rozproszonego: na przykład, jakie jest zadanie projektanta algorytmu, a co jest równoczesnym lub rozproszonym odpowiednikiem sekwencyjnego komputer ogólnego przeznaczenia?
Poniższa dyskusja koncentruje się na przypadku wielu komputerów, chociaż wiele problemów jest takich samych dla procesów współbieżnych działających na jednym komputerze.
Powszechnie stosowane są trzy punkty widzenia:
- Algorytmy równoległe w modelu pamięci współdzielonej
- Wszystkie procesory mają dostęp do pamięci współdzielonej. Projektant algorytmu wybiera program wykonywany przez każdy procesor.
- Jednym z modeli teoretycznych są używane równoległe maszyny o dostępie swobodnym (PRAM). Jednak klasyczny model PRAM zakłada synchroniczny dostęp do pamięci współdzielonej.
- Programy z pamięcią współdzieloną można rozszerzyć na systemy rozproszone, jeśli bazowy system operacyjny hermetyzuje komunikację między węzłami i wirtualnie ujednolica pamięć we wszystkich indywidualnych systemach.
- Model, który jest bliższy zachowaniu rzeczywistych maszyn wieloprocesorowych i uwzględnia użycie instrukcji maszynowych, takich jak Porównaj i zamień (CAS), to asynchroniczna pamięć współdzielona . Istnieje wiele prac nad tym modelem, których podsumowanie można znaleźć w literaturze.
- Algorytmy równoległe w modelu przekazywania wiadomości
- Projektant algorytmu wybiera strukturę sieci, a także program wykonywany przez każdy komputer.
- Wykorzystywane są modele takie jak obwody logiczne i sieci sortujące . Obwód logiczny może być postrzegany jako sieć komputerowa: każda bramka to komputer, który uruchamia niezwykle prosty program komputerowy. Podobnie sieć sortującą może być postrzegana jako sieć komputerowa: każdy komparator to komputer.
- Algorytmy rozproszone w modelu przekazywania wiadomości
- Projektant algorytmu wybiera tylko program komputerowy. Wszystkie komputery uruchamiają ten sam program. System musi działać poprawnie niezależnie od struktury sieci.
- Powszechnie używanym modelem jest graf z jedną maszyną skończoną na węzeł.
W przypadku algorytmów rozproszonych problemy obliczeniowe są zazwyczaj związane z grafami. Często instancją problemu jest graf opisujący strukturę sieci komputerowej . Ilustruje to poniższy przykład.
Przykład
Rozważmy obliczeniowy problem znalezienia kolorowania danego grafu G . Różne pola mogą przyjmować następujące podejścia:
- Scentralizowane algorytmy
- Wykres G jest zakodowany jako ciąg, a ciąg jest podawany jako dane wejściowe do komputera. Program komputerowy znajduje kolor wykresu, koduje kolorowanie jako łańcuch i wyświetla wynik.
- Algorytmy równoległe
- Ponownie, wykres G jest zakodowany jako łańcuch. Jednak wiele komputerów może równolegle uzyskiwać dostęp do tego samego ciągu. Każdy komputer może skupić się na jednej części wykresu i stworzyć dla niej kolorowanie.
- Główny nacisk kładziony jest na obliczenia o wysokiej wydajności, które wykorzystują moc przetwarzania wielu komputerów równolegle.
- Algorytmy rozproszone
- Wykres G to struktura sieci komputerowej. Istnieje jeden komputer dla każdego węzła G i jedno łącze komunikacyjne dla każdej krawędzi G . Początkowo każdy komputer zna tylko swoich najbliższych sąsiadów na grafie G ; komputery muszą wymieniać między sobą wiadomości, aby dowiedzieć się więcej o strukturze G . Każdy komputer musi wyprodukować własny kolor jako wynik.
- Główny nacisk kładziony jest na koordynację działania dowolnego systemu rozproszonego.
Chociaż dziedzina algorytmów równoległych ma inny cel niż dziedzina algorytmów rozproszonych, istnieje wiele interakcji między tymi dwoma polami. Na przykład algorytm Cole-Vishkina do kolorowania grafów został pierwotnie przedstawiony jako algorytm równoległy, ale ta sama technika może być również używana bezpośrednio jako algorytm rozproszony.
Co więcej, algorytm równoległy może być zaimplementowany w systemie równoległym (przy użyciu pamięci współdzielonej) lub w systemie rozproszonym (przy użyciu przekazywania komunikatów). Tradycyjna granica między algorytmami równoległymi i rozproszonymi (wybierz odpowiednią sieć vs. uruchamianie w dowolnej sieci) nie leży w tym samym miejscu, co granica między systemami równoległymi i rozproszonymi (pamięć współdzielona vs. przekazywanie wiadomości).
Miary złożoności
W algorytmach równoległych, kolejnym zasobem oprócz czasu i przestrzeni jest liczba komputerów. Rzeczywiście, często istnieje kompromis między czasem działania a liczbą komputerów: problem można rozwiązać szybciej, jeśli więcej komputerów działa równolegle (patrz przyspieszenie ). Jeśli problem decyzyjny można rozwiązać w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, mówi się, że problem należy do klasy NC . Klasę NC można równie dobrze zdefiniować za pomocą formalizmu PRAM lub obwodów logicznych — maszyny PRAM mogą wydajnie symulować obwody logiczne i vice versa.
W analizie algorytmów rozproszonych zwykle więcej uwagi poświęca się operacjom komunikacyjnym niż krokom obliczeniowym. Być może najprostszym modelem przetwarzania rozproszonego jest system synchroniczny, w którym wszystkie węzły działają w sposób blokujący. Model ten jest powszechnie znany jako model LOKALNY. Podczas każdej rundy komunikacji wszystkie węzły równolegle (1) odbierają najnowsze wiadomości od swoich sąsiadów, (2) wykonują dowolne lokalne obliczenia i (3) wysyłają nowe wiadomości do swoich sąsiadów. W takich systemach centralną miarą złożoności jest liczba rund komunikacji synchronicznej wymaganych do wykonania zadania.
Ta miara złożoności jest ściśle związana z średnicą sieci. Niech D będzie średnicą sieci. Z jednej strony, każde obliczeniowy problem może być rozwiązany trywialny synchronicznie systemie rozproszonym w ciągu około 2 D rund komutacyjnych prostu zebrać wszystkie informacje w jednym miejscu ( D naboi), rozwiązania problemu, oraz informować węzeł o rozwiązanie ( D rund ).
Z drugiej strony, jeśli czas działania algorytmu jest znacznie krótszy niż D rund komunikacyjnych, to węzły w sieci muszą generować swoje dane wyjściowe bez możliwości uzyskania informacji o odległych częściach sieci. Innymi słowy, węzły muszą podejmować globalnie spójne decyzje w oparciu o informacje dostępne w ich lokalnym sąsiedztwie D . Znanych jest wiele algorytmów rozproszonych o czasie działania znacznie krótszym niż rundy D , a zrozumienie, jakie problemy można rozwiązać za pomocą takich algorytmów, jest jednym z głównych pytań badawczych w tej dziedzinie. Zazwyczaj algorytm, który rozwiązuje problem w czasie polilogarytmicznym w rozmiarze sieci, jest uważany za wydajny w tym modelu.
Inną powszechnie stosowaną miarą jest całkowita liczba bitów przesyłanych w sieci (por. złożoność komunikacji ). Cechy tej koncepcji są zazwyczaj uchwycone w modelu CONGEST(B), który jest podobnie definiowany jako model LOCAL, ale w którym pojedyncze komunikaty mogą zawierać tylko B bitów.
Inne problemy
Tradycyjne problemy obliczeniowe przyjmują perspektywę, w której użytkownik zadaje pytanie, komputer (lub system rozproszony) przetwarza pytanie, a następnie wytwarza odpowiedź i zatrzymuje się. Istnieją jednak również problemy, w których system musi się nie zatrzymywać, w tym problem filozofów jedzenia i inne podobne problemy wzajemnego wykluczania . W tych problemach system rozproszony powinien stale koordynować wykorzystanie współdzielonych zasobów, aby nie dochodziło do konfliktów ani zakleszczeń .
Istnieją również fundamentalne wyzwania, które są specyficzne dla przetwarzania rozproszonego, na przykład te związane z odpornością na awarie . Przykłady powiązanych problemów obejmują problemy z konsensusem , bizantyjską tolerancję błędów i samostabilizację .
Wiele badań koncentruje się również na zrozumieniu asynchronicznej natury systemów rozproszonych:
- Synchronizatory mogą służyć do uruchamiania algorytmów synchronicznych w systemach asynchronicznych.
- Zegary logiczne zapewniają przyczynę, która miała miejsce przed uporządkowaniem wydarzeń.
- Algorytmy synchronizacji zegara zapewniają globalnie spójne fizyczne znaczniki czasu.
Wybór
Wybór koordynatora (lub wybór lidera ) to proces wyznaczania pojedynczego procesu jako organizatora jakiegoś zadania rozłożonego na kilka komputerów (węzłów). Przed rozpoczęciem zadania wszystkie węzły sieci albo nie wiedzą, który węzeł będzie pełnił rolę „koordynatora” (lub lidera) zadania, albo nie są w stanie komunikować się z obecnym koordynatorem. Jednak po uruchomieniu algorytmu wyboru koordynatora każdy węzeł w sieci rozpoznaje określony, unikalny węzeł jako koordynator zadania.
Węzły sieci komunikują się między sobą, aby zdecydować, który z nich przejdzie w stan „koordynatora”. W tym celu potrzebują jakiejś metody, aby przełamać symetrię między nimi. Na przykład, jeśli każdy węzeł ma unikalne i porównywalne tożsamości, węzły mogą porównać swoje tożsamości i zdecydować, że węzeł o najwyższej tożsamości jest koordynatorem.
Definicja tego problemu jest często przypisywana LeLannowi, który sformalizował go jako metodę tworzenia nowego tokena w sieci Token Ring, w której token został utracony.
Algorytmy wyboru koordynatora są zaprojektowane tak, aby były ekonomiczne pod względem łącznej liczby przesłanych bajtów i czasu. Algorytm zaproponowany przez Gallagera, Humbleta i Spirę dla ogólnych grafów nieskierowanych wywarł duży wpływ na ogólne projektowanie algorytmów rozproszonych i zdobył nagrodę Dijkstry za wpływowy artykuł dotyczący obliczeń rozproszonych.
Zaproponowano wiele innych algorytmów dla różnego rodzaju grafów sieciowych , takich jak pierścienie nieskierowane, pierścienie jednokierunkowe, pełne grafy, siatki, skierowane grafy Eulera i inne. Korach, Kutten i Moran zaproponowali ogólną metodę, która oddziela kwestię rodziny grafów od projektu algorytmu wyboru koordynatora.
W celu realizacji koordynacji systemy rozproszone wykorzystują koncepcję koordynatorów. Problem wyboru koordynatora polega na wyborze procesu spośród grupy procesów na różnych procesorach w systemie rozproszonym, który będzie pełnił rolę centralnego koordynatora. Istnieje kilka algorytmów wyboru centralnego koordynatora.
Właściwości systemów rozproszonych
Do tej pory koncentrowano się na projektowaniu systemu rozproszonego, który rozwiązuje dany problem. Uzupełniającym problemem badawczym jest badanie właściwości danego systemu rozproszonego.
Zatrzymanie problemem jest analogiczny przykład z zakresu scentralizowanej obliczeń: daje nam program komputerowy, a zadaniem jest podjęcie decyzji, czy zatrzymuje lub uruchamia zawsze. W ogólnym przypadku problem zatrzymania jest nierozstrzygnięty i naturalnie zrozumienie zachowania sieci komputerowej jest co najmniej tak trudne, jak zrozumienie zachowania jednego komputera.
Istnieje jednak wiele interesujących przypadków szczególnych, które są rozstrzygalne. W szczególności można wnioskować o zachowaniu sieci maszyn skończonych. Jednym z przykładów jest stwierdzenie, czy dana sieć współdziałających (asynchronicznych i niedeterministycznych) maszyn skończonych może osiągnąć zakleszczenie. Problem ten jest PSPACE-kompletny , tj. jest rozstrzygalny, ale nie jest prawdopodobne, że istnieje wydajny (scentralizowany, równoległy lub rozproszony) algorytm, który rozwiązuje problem w przypadku dużych sieci.
Zobacz też
- Rozproszona sieć
- Zdecentralizowane przetwarzanie
- Federacja (technologia informacyjna)
- Skala aplikacji
- BOINC
- Mobilność kodu
- Algorytm rozproszony
- Rozproszony projekt mechanizmu algorytmicznego
- Rozproszona pamięć podręczna
- Rozproszony system operacyjny
- Nagroda Edsgera W. Dijkstry w dziedzinie obliczeń rozproszonych
- Obliczanie mgły
- Składanie@dom
- Obliczenia sieciowe
- Piekło
- Komputery w dżungli
- Warstwowa sieć kolejkowania
- Architektura zorientowana na bibliotekę (LOA)
- Lista konferencji poświęconych informatyce rozproszonej
- Lista projektów przetwarzania rozproszonego
- Lista ważnych publikacji z zakresu obliczeń współbieżnych, równoległych i rozproszonych
- Sprawdzanie modelu
- Równoległe przetwarzanie rozproszone
- Model programowania równoległego
- Plan 9 z Bell Labs
- Architektura nic współdzielonego
Uwagi
Bibliografia
- Książki
- Andrews, Gregory R. (2000), Podstawy programowania wielowątkowego, równoległego i rozproszonego , Addison-Wesley , ISBN 978-0-201-35752-3.
- Arora, Sanjeev ; Barak, Boaz (2009), Złożoność obliczeniowa – nowoczesne podejście , Cambridge , ISBN 978-0-521-42426-4.
- Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L. (1990), Wprowadzenie do algorytmów (1st ed.), MIT Press , ISBN 978-0-262-03141-7.
- Dolev, Shlomi (2000), Samostabilizacja , MIT Press , ISBN 978-0-262-04178-2.
- Elmasri, Ramez; Navathe, Shamkant B. (2000), Podstawy systemów baz danych (3rd ed.), Addison-Wesley , ISBN 978-0-201-54263-9.
- Ghosh, Sukumar (2007), Systemy rozproszone – podejście algorytmiczne , Chapman & Hall/CRC, ISBN 978-1-58488-564-1.
- Lynch, Nancy A. (1996), Algorytmy rozproszone , Morgan Kaufmann , ISBN 978-1-55860-348-6.
- Herlihy, Maurice P .; Shavit, Nir N. (2008), Sztuka programowania wieloprocesorowego , Morgan Kaufmann , ISBN 978-0-12-370591-4.
- Papadimitriou, Christos H. (1994), Złożoność obliczeniowa , Addison-Wesley , ISBN 978-0-201-53082-7.
- Peleg, David (2000), Przetwarzanie rozproszone: podejście uwzględniające lokalizację , SIAM , ISBN 978-0-89871-464-7, zarchiwizowane z oryginału dnia 2009-08-06 , pobrane 2009-07-16.
- Artykuły
- Cole'a, Richarda; Vishkin, Uzi (1986), "Deterministyczne rzucanie monetą z aplikacjami do optymalnego rankingu listy równoległej", Information and Control , 70 (1): 32-53, doi : 10.1016/S0019-9958 (86) 80023-7.
- Keidar, Idit (2008), „Distributed computing column 32 – The year in review” , ACM SIGACT News , 39 (4): 53–54, CiteSeerX 10.1.1.116.1285 , doi : 10.1145/1466390.1466402.
- Linial, Nathan (1992), " Lokalność w algorytmach grafów rozproszonych", SIAM Journal on Computing , 21 (1): 193-201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015.
- Naor, Moni ; Stockmeyer, Larry (1995), „Co można obliczyć lokalnie?” (PDF) , SIAM Journal on Computing , 24 (6): 1259–1277, CiteSeerX 10.1.1.29.669 , doi : 10.1137/S0097539793254571.
- Strony internetowe
- Godfrey, Bill (2002). „Pierwszy element informatyki rozproszonej” .
- Piotr, Ian (2004). „Historia Internetu Iana Petera” . Źródło 2009-08-04 .
Dalsza lektura
- Książki
- Attiya, Hagit i Jennifer Welch (2004), Przetwarzanie rozproszone: podstawy, symulacje i tematy zaawansowane , Wiley-Interscience ISBN 0-471-45324-2 .
- Chrześcijański Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Wprowadzenie do niezawodnego i bezpiecznego programowania rozproszonego (2. ed.), Springer, Bibcode : 2011itra.book.....C , ISBN 978-3-642-15259-7
- Coulouris, George; i in. (2011), Systemy rozproszone: koncepcje i projektowanie (wydanie 5) , Addison-Wesley ISBN 0-132-14301-1 .
- Faber, Jim (1998), Java Distributed Computing , O'Reilly: Java Distributed Computing, Jim Faber, 1998
- Garg, Vijay K. (2002), Elementy przetwarzania rozproszonego , Wiley-IEEE Press ISBN 0-471-03600-5 .
- Tel, Gerard (1994), Wprowadzenie do algorytmów rozproszonych , Cambridge University Press
- Chandy, Mani ; et al., Projektowanie programów równoległych
- Dusseau, Remzi H.; Dusseau, Andrea (2016). Systemy operacyjne: Trzy proste elementy, rozdział 48 Systemy rozproszone (PDF) . Zarchiwizowane z oryginału (PDF) w dniu 31 sierpnia 2021 r . Pobrano 8 października 2021 .
- Artykuły
- Keidar, Idit; Rajsbaum, Sergio, wyd. (2000-2009), "Rozproszona kolumna obliczeniowa" , ACM SIGACT News.
- Birrell, AD; Levin, R.; Schroedera, MD; Needham, RM (kwiecień 1982). „Grapevine: Ćwiczenie z informatyki rozproszonej” (PDF) . Komunikaty ACM . 25 (4): 260–274. doi : 10.1145/358468.358487 . S2CID 16066616 .
- Materiały konferencyjne
- Rodrigueza, Carlosa; Villagra, Marcos; Baran, Benjamin (2007). „Asynchroniczne algorytmy zespołu dla Boolean Satisfiability”. 2007 2. Bio-inspirowane modele sieci, systemów informatycznych i komputerowych . s. 66-69. doi : 10.1109/BIMNICS.2007.4610083 . S2CID 15185219 .