Homotopy in concurrent processes

• Autorzy: Sokołowski S.

Warianty tytułu

PL

Homotopie w badaniu procesów współbieżnych

• Języki publikacji: EN

Abstrakty

EN

In theories of job scheduling and of distributed computing, there have been many attempts to introduce tools originating from algebraic and combinatorial topology, such as homotopy groups. Informally, the fundamental (or first homotopy) group gives an account of the nature of 'holes' in a topological space. In the realm of processes, such holes may correspond to forbidden configurations; e.g. where more than one process is within the same critical region. However, many topological properties, technically necessary for the construction of the fundamental group, have no counterparts, or only artificial ones, in concurrent processes. The path corresponding to process executions are not cyclic, because time only flows forwards, and they cannot be as naturally composed as looping paths in topological spaces. The fundamental 'group' lacks therefore its group operations. This paper puts forward a simple remedy for the shortcomings: if you cannot find a useful group operation on your homotopy classes, settle for a less requiring structure, e.g. homotopy cpo-s (explained in this paper). As will be shown, the transition from vectors of processes to their homotopy cpo-s is functorial, preserves information about the 'holes' and abstracts from inessential details. This renders the approach a potentially useful tool for investigating admissible runs of concurrent processes.

PL

W teoriach szeregowania zadań oraz obliczeń rozproszonych wielokrotnie próbowano stosować narzędzia pochodzące z topologii algebraicznej i kombinatorycznej, takie jak grupy homotopii. Mówiąc nieformalnie grupa podstawowa (czyli pierwsza grupa homotopii) oddaje naturę 'dziur' w przestrzeni topologicznej. W kontekście procesów takie dziury mogą odpowiadać zabronionym konfiguracjom; np. takim, w których więcej niż jeden proces znajduje się wewnątrz regionu krytycznego. Jednak szereg własności topologicznych niezbędnych technicznie dla konstrukcji grupy podstawowej nie ma naturalnych odpowiedników w procesach współbieżnych. Ścieżki odpowiadające wykonaniom procesów nie są cykliczne, bo czas płynie tylko w jedną stronę, więc nie mogą być składane w taki sam sposób jak zamknięte ścieżki w przestrzeniach topologicznych. Takiej 'grupie' podstawowej brakuje więc operacji grupowych. Niniejsza praca przedstawia prostą drogę wyjścia z tej trudności. Jeśli nie da się znaleźć użytecznej operacji grupowej, należy się zadowolić strukturą mniej wymagającą niż grupa; np. homotopijnym cpo (wyjaśnione dokładniej w tej pracy. Pokazujemy, że przejście od wektorów procesów do ich homotopijnych cpo jest funktorialne, zachowuje informację o 'dziurach' i abstrahuje od nieistotnych procesów. W wyniku tego przedstawione podejście może się stać użytecznym narzędziem do badania dopuszczalnych wykonań procesów współbieżnych.

Słowa kluczowe

EN

homotopy; concurrent processes

PL

homotopia; procesy współbieżne

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 1998
• Tom: nr 854
• Strony: 3--49
• Opis fizyczny: .

Twórcy

autor

Sokołowski S.

• Institut of Computer Science Polish Academy of Science Gdańsk Division ul. Abrahama 18 81-825 Sopot, Poland