Co oznacza „prawdziwa współbieżność”?

28

Często słyszę wyrażenia takie jak „semantyka prawdziwej współbieżności” i „równoważność prawdziwej współbieżności” bez żadnych odniesień. Co oznaczają te terminy i dlaczego są ważne?

Jakie są przykłady prawdziwych odpowiedników współbieżności i jaka jest ich potrzeba? Np. W jakich przypadkach mają one większe zastosowanie niż więcej standardowych równoważników (bisimulacja, równoważność śladowa itp.)?

Daniil
źródło

Odpowiedzi:

23

Termin „prawdziwa współbieżność” pojawia się w teoretycznym badaniu obliczeń współbieżnych i równoległych. Jest to przeciwieństwo współbieżności przeplatania. Prawdziwa współbieżność to współbieżność, której nie można sprowadzić do przeplatania. Współbieżność jest przeplatana, jeżeli na każdym etapie obliczeń może mieć miejsce tylko jedna akcja obliczeń atomowych (np. Wymiana wiadomości między nadawcą a odbiorcą). Współbieżność jest prawdą, jeśli więcej niż jedno takie działanie atomowe ma miejsce w jednym kroku.

Najprostszym sposobem na rozróżnienie obu jest przyjrzenie się regule dla kompozycji równoległej. W ustawieniach opartych na przeplataniu wyglądałoby to mniej więcej tak:

PPP|QP|Q

Ta reguła wymusza, że ​​tylko jeden proces w składzie równoległym może wykonać akcję atomową. W przypadku prawdziwej współbieżności bardziej odpowiednia byłaby reguła taka jak poniżej.

PPQQP|QP|Q

Ta reguła pozwala obu uczestnikom w równoległym składzie wykonywać działania atomowe.

Dlaczego ktoś interesuje się przeplataną współbieżnością, skoro teoria współbieżności jest tak naprawdę badaniem systemów, które wykonują kroki obliczeniowe równolegle? Odpowiedź brzmi: i to świetny wgląd, że w przypadku prostych form współbieżności przekazywania wiadomości, prawdziwa współbieżność i współbieżność oparta na przeplataniu nie są rozróżnialne kontekstowo. Innymi słowy, przeplatana współbieżność zachowuje się jak prawdziwa współbieżność, o ile obserwatorzy mogą to zobaczyć. Przeplatanie to dobry rozkład prawdziwej współbieżności. Ponieważ przeplatanie jest łatwiejsze w dowodach, ludzie często studiują tylko prostszą współbieżność opartą na przeplataniu (np. CCS iπ-calculi). Jednak ta prostota znika w obliczeniach współbieżnych z bogatszymi formami obserwacji (np. Obliczenia czasowe): różnica między prawdziwą współbieżnością a współbieżnością przeplataną staje się zauważalna.

Standardowe równoważniki, takie jak bisimulacje i ślady, mają te same definicje dla współbieżności opartej na prawdzie i przeplataniu. Ale mogą, ale nie muszą równać różnych procesów, w zależności od rachunku różniczkowego.

Pozwólcie, że przedstawię nieformalne wyjaśnienie, dlaczego przeplatanie i prawdziwie współbieżne interakcje są nierozróżnialne w prostych obliczeniach procesowych. Ustawienie jest rachunkiem podobnym do CCS lub . Powiedzmy, że mamy programπ

P=x¯ | y¯ | x.y.a¯ | y.b¯
Następnie mamy następującą naprawdę równoczesną redukcję: Ten krok redukcji można uzupełnić następującymi przeplatanymi krokami: Jedyna różnica między nimi polega na tym, że pierwszy robi jeden krok, a drugi dwa. Ale proste kalkulatory nie mogą wykryć liczby kroków użytych do osiągnięcia procesu.
Py.a¯ | b¯
Px¯ | x.y.a¯ | b¯y.a¯ | b¯

Jednocześnie ma następującą drugą przeplecioną sekwencję redukcji: Ale jest to również sekwencja redukcji w naprawdę współbieżnych ustawieniach, o ile prawdziwa współbieżność nie jest wymuszona (tj. wykonania z przeplotem są dozwolone, nawet jeśli istnieje możliwość więcej niż jednej interakcji na raz).P

Py¯ | y.a¯ | y.b¯a¯ | y.b¯
Martin Berger
źródło
Dzięki, świetna odpowiedź! Czy możesz podać mi referencje do dalszej lektury?
Daniil
@Daniil Obawiam się, że nie mam pod ręką żadnych dobrych referencji. Po części jest to folklor, po części badany we wczesnych dniach teorii współbieżności, zanim zacząłem. Jeśli lubisz robić matematykę, możesz samodzielnie ustalić podstawowe wyniki. Weź prosty rachunek procesowy, np. Asynchroniczny -calculus, wyposażyć go w naprawdę równoczesne redukcje i pokaż, że dwa procesy w nowym rachunku są zrównane z twoim ulubionym (słabym) pojęciem równoważności dokładnie wtedy, gdy są one zrównane w rachunku przeplatania. π
Martin Berger,
0

Prawdę mówiąc, sam szukałem odpowiedzi w Google. Jaka jest tutaj semantyka? Przypisujemy znaczenie „system przejściowy” opisowi „algebra procesu”; tzn. znaczenie to system przejściowy, który jest generowany z początkowego opisu systemu przy użyciu zdefiniowanych reguł SOS. Tak więc, stosując semantykę przeplatania, tracimy całą współbieżną strukturę w uzyskanym układzie przejściowym.

Inną odpowiedzią może być to, że nie jest to „zauważalna różnica”, ale różnica w „obserwowalności”. Stosując semantykę przeplatania, możemy obserwować tylko przebiegi liniowe; natomiast stosując prawdziwą współbieżność możemy zaobserwować „równoczesne przebiegi” (por. W.Reisig'13 książka sieci Petriego).

Mimo to mam wątpliwości co do tego, co powiedziałem powyżej, i byłoby interesujące usłyszeć głębsze spostrzeżenia. Tj. Przy użyciu zegarów wektorowych Lamporta ile teorii względności można przenieść na teorię współbieżności.

Leonid Dworzański
źródło
1
Już na wczesnym etapie zaobserwowano, że przejście ze współbieżnego programu do systemu przejściowego może przynieść straty. John Reynolds sformułował to, co jest obecnie znane jako kryterium Reynoldsa, aby scharakteryzować, kiedy semantyka przeplatania jest dokładna dla programów współbieżnych ze zmiennymi współdzielonymi. Vaughan Pratt zbadał prawdziwą współbieżność jako model P 1986 i wraz z Gordonem Plotkinem wykazał, kiedy można zaobserwować stronniczość kolejności działań P&P, 1987 .
Kai
@Kai, referencje są bardzo mile widziane! Spiszę je na wypadek, gdyby linki zostały zerwane: Vaughan Pratt, Modelowanie współbieżności z częściowymi zamówieniami; G. Plotkin V. Pratt, Teams Can See Pomset. > można stworzyć w sposób stratny Z pewnością chciałem po prostu wyjaśnić osobne pojęcia w „opisie składniowym / semantyce / znaczeniu”.
Leonid Dworzański