Search
Search results for: algorytmy rozproszone
-
Algorytmy równoległe i rozproszone/Parallel and distributed >> algorithms
e-Learning Courses -
Rozproszone kolorowanie grafów
PublicationW pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.
-
Zachłanne algorytmy kolorowania grafów w modelu rozproszonym
PublicationW artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.
-
Track-to-track fusion in tracking of multiple targets in clutter - a comparative study.
PublicationPrzedstawiono i porównano algorytmy rozproszone wyznaczania trajektorii obiektów dynamicznych na podstawie danych z wielu źródeł. Rozważono przypadek, w którym dane dotyczące pozycji obiektów są zakłócone przez dodatkowe fałszywe wykrycia niezwiązane z obserwowanymi obiektami. Algorytmy rozproszone i centralne to dwie podstawowe klasy algorytmów służące do wyznaczania trajektorii obiektów dynamicznych na podstawie danych z wielu...
-
Waldemar Korłub dr inż.
PeopleWaldemar Korłub obtained an Eng. degree in 2011, MSc.Eng. degree in 2012 and PhD in Computer Science in 2017 granted by the Faculty of Electronics, Telecommunications and Informatics at Gdansk University of Technology. His research interests include: distributed systems mainly grid and cloud computing platforms, autonomous systems capable of self-optimization, self-management, self-healing and self-protection, artificial intelligence...
-
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Regulacyjne usługi systemowe w zakresie mocy czynnej. - P. Bićko.
PublicationW pracy poddano krytycznej analizie aktualne zasady funkcjonowania rynku regulacyjnych usług systemowych w Krajowym Systemie Elektroenergetycznym. Badano powiązania procesów bilansowania mocy z bilansowaniem energii elektrycznej. W konsekwencji zidentyfikowano powiązania rynku usług regulacyjnych z Rynkiem Bilansującym. W pracy przedstawiono podstawowe uwarunkowania techniczne świadczenia omawianych regulacyjnych usług systemowych,...
-
Komputerowe systemy automatyki - 2022/2023
e-Learning Coursesmateriały wspierające wykład na studiach II stopnia na kierunku ACR pod tytułem komputerowe systemy automatyki 1. Sprzęganie magistrali systemu komputerowego z obiektem sterowania. Sprzężenie proste i z wzajemnym potwierdzeniem, idea, algorytmy, przekazywania potwierdzenia 2. Warianty realizacji przekazywania potwierdzenia: programowy, z wykorzystaniem systemu przerwań oraz wejścia wymuszającego wyczekiwanie. Kryteria doboru...
-
Komputerowe Systemy Automatyki wykład 2023-2024
e-Learning Coursesmateriały wspierające wykład na studiach II stopnia na kierunku ACR pod tytułem komputerowe systemy automatyki 1. Sprzęganie magistrali systemu komputerowego z obiektem sterowania. Sprzężenie proste i z wzajemnym potwierdzeniem, idea, algorytmy, przekazywania potwierdzenia 2. Warianty realizacji przekazywania potwierdzenia: programowy, z wykorzystaniem systemu przerwań oraz wejścia wymuszającego wyczekiwanie. Kryteria doboru optymalnego...
-
Architektura Systemów Komputerowych
Research TeamsGłówną tematyką badawczą podejmowaną w Katedrze jest rozwój architektury aplikacji i systemów komputerowych, w szczególności aplikacji i systemów równoległych i rozproszonych. "Architecture starts when you carefully put two bricks together" - stwierdza niemiecki architekt Ludwig Mies von der Rohe. W przypadku systemów komputerowych dotyczy to nie cegieł, a modułów sprzętowych lub programowych. Przez architekturę systemu komputerowego...
-
Taking advantage of symmetries: gathering of asynchronous oblivious robots on a ring
PublicationW pracy rozważano problem rendezvous (spotkania, zebrania) dla zbioru bezpamięciowych robotów umieszczonych na wierzchołkach cyklu nieskierowanego, niewyposażonych w urządzenia komunikacyjne. Przyjęto model systemu rozproszonego występujący w literaturze pod nazwą asynchronicznego systemu z cyklami Look-Compute-Move. Problem istnienia rozwiązania rozwiązano dla wszystkich konfiguracji poczatkowych składających się z więcej niż...
-
On the complexity of distributed greedy coloring
PublicationW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
Grid Implementation of a Parallel Multiobjective Genetic Algorithm for Optimized Allocation of Chlorination Stations in Drinking Water Distribution Systems: Chojnice Case Study
PublicationSolving multiobjective optimization problems requires suitable algorithms to find a satisfactory approximation of a globally optimal Pareto front. Furthermore, it is a computationally demanding task. In this paper, the grid implementation of a distributed multiobjective genetic algorithm is presented. The distributed version of the algorithm is based on the island algorithm with forgetting island elitism used instead of a genetic...
-
Constructing a map of an anonymous graph: applications of universal sequences
PublicationWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
PublicationTwo mobile agents, modeled as points starting at differentlocations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and epsilon-RV, when these points have to get at distance less than epsilon in the terrain. In any terrain, each agent chooses its trajectory, but...
-
Universal Augmentation Schemes for Network Navigability
PublicationRozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu...
-
What Can Be Observed Locally? Round based models for quantum distributed computing
PublicationW pracy rozważono zagadnienie lokalności w kontekście informacji kwantowej w obliczeniach rozproszonych. Rozważono dwa kwantowe rozszerzenia modelu LOCAL Liniala, otrzymane poprzez: (1) inicjalizację systemu w kwantowym stanie splątanym, (2) zastosowanie kwantowych kanałów komunikacyjnych. Dla obydwu typów rozszerzeń zaproponowano przykłady problemów, których złożoność rundowa ulega redukcji w porównaniu do oryginalnego modelu...
-
Energy optimisation in resilient self-stabilizing processes
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Distributed largest-first algorithm for graph coloring.
PublicationW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
An experimental study of distributed algorithms for graph coloring.
PublicationW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
A Point Set Connection Problem for Autonomous Mobile Robots in a Grid
PublicationConsider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given...
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublicationWe consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...
-
Bounds on the cover time of parallel rotor walks
PublicationThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...
-
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
PublicationOne of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous...
-
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
PublicationWe study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...
-
Fast collaborative graph exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Bounds on the Cover Time of Parallel Rotor Walks
PublicationThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...
-
On-line Search in Two-Dimensional Environment
PublicationWe consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...
-
Multi-agent graph searching and exploration algorithms
PublicationA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
-
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
On greedy graph coloring in the distributed model
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.