Algorytm rozproszony
Algorytm rozproszony to algorytm przeznaczony do działania na sprzęcie komputerowym zbudowanym z połączonych ze sobą procesorów . Algorytmy rozproszone są wykorzystywane w różnych obszarach zastosowań przetwarzania rozproszonego , takich jak telekomunikacja , obliczenia naukowe , rozproszone przetwarzanie informacji i sterowanie procesami w czasie rzeczywistym . Standardowe problemy rozwiązywane przez algorytmy rozproszone obejmują wybór lidera , konsensus , wyszukiwanie rozproszone , generowanie drzewa opinającego , wzajemne wykluczanie i alokację zasobów .
Algorytmy rozproszone są podtypem algorytmu równoległego , zwykle wykonywanego współbieżnie , z oddzielnymi częściami algorytmu uruchamianymi jednocześnie na niezależnych procesorach i posiadającymi ograniczone informacje o tym, co robią inne części algorytmu. Jednym z głównych wyzwań przy opracowywaniu i wdrażaniu algorytmów rozproszonych jest skuteczna koordynacja zachowania niezależnych części algorytmu w obliczu awarii procesora i zawodnych łączy komunikacyjnych. Wybór odpowiedniego algorytmu rozproszonego do rozwiązania danego problemu zależy zarówno od charakterystyki problemu, jak i cech systemu, na którym algorytm będzie działał, takich jak rodzaj i prawdopodobieństwo awarii procesora lub łącza, rodzaj komunikacji między procesami które można wykonać, oraz poziom synchronizacji taktowania między oddzielnymi procesami.
Standardowe problemy
- Zatwierdzenie atomowe
- Zatwierdzenie atomowe to operacja, w której zestaw odrębnych zmian jest stosowany jako pojedyncza operacja. Jeśli zatwierdzenie atomowe powiedzie się, oznacza to, że wszystkie zmiany zostały zastosowane. Jeśli wystąpi błąd przed ukończeniem zatwierdzenia atomowego, „zatwierdzenie” zostanie przerwane i żadne zmiany nie zostaną zastosowane.
- Algorytmy rozwiązywania problemu zatwierdzania atomowego obejmują protokół zatwierdzania dwufazowego i protokół zatwierdzania trójfazowego . Algorytmy
- konsensusu
- próbują rozwiązać problem uzgadniania się wielu procesów w sprawie wspólnej decyzji.
- Dokładniej, protokół konsensusu musi spełniać cztery poniższe właściwości formalne.
- Zakończenie : każdy poprawny proces decyduje o jakiejś wartości.
- Ważność jeśli wszystkie procesy proponują tę samą wartość każdy poprawny proces .
- Integralność : decyduje co najwyżej o jednej wartości, a jeśli decyduje , to musiał zostać zaproponowany przez jakiś proces
- Zgoda proces , to każdy prawidłowy proces .
- Powszechnymi algorytmami rozwiązywania konsensusu są algorytm Paxos i algorytm Raft .
- Wyszukiwanie rozproszone
- Wybór lidera
- 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 nie wiedzą, który węzeł będzie pełnił rolę „lidera” lub koordynatora zadania. Jednak po uruchomieniu algorytmu wyboru lidera każdy węzeł w sieci rozpoznaje konkretny, unikalny węzeł jako lidera zadania.
- Wzajemne wykluczanie
- Nieblokujące struktury danych
- Niezawodna transmisja
- Niezawodna transmisja jest prymitywną komunikacją w systemach rozproszonych. Niezawodna transmisja jest definiowana przez następujące właściwości:
- Ważność - jeśli poprawny proces wysyła wiadomość, to jakiś poprawny proces ostatecznie dostarczy tę wiadomość.
- Umowa — jeśli prawidłowy proces dostarcza komunikat, wszystkie poprawne procesy ostatecznie dostarczają ten komunikat.
- Integralność - każdy poprawny proces dostarcza ten sam komunikat co najwyżej raz i tylko wtedy, gdy ten komunikat został wysłany przez proces.
- Niezawodna transmisja może mieć uporządkowanie sekwencyjne, przyczynowe lub całkowite.
- Replikacja
- Alokacja zasobów
- Generowanie drzewa
- rozpinającego Łamanie symetrii, np. kolorowanie wierzchołków
Dalsza lektura
- Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Wprowadzenie do niezawodnego i bezpiecznego programowania rozproszonego (wyd. 2), Springer, Bibcode : 2011itra.book.....C , ISBN 978-3-642-15259-7
- C. Rodríguez, M. Villagra i B. Barán, Asynchroniczne algorytmy zespołowe dla Boolean Satisfiability , Bionetics2007, s. 66–69, 2007.
Linki zewnętrzne
-
Media związane z algorytmami rozproszonymi w Wikimedia Commons - Otwarte oprogramowanie szkoleniowe MIT — algorytmy rozproszone
