J 2006

Different time solutions for the firing squad synchronization problem on basic grid networks

GRUSKA, Jozef; Salvatore LA TORRE; Margherita NAPOLI a Mimmo PARENTE

Základní údaje

Originální název

Different time solutions for the firing squad synchronization problem on basic grid networks

Název česky

Různá časová řešení pro FSSP v základních gridových sítích

Autoři

GRUSKA, Jozef (703 Slovensko, garant); Salvatore LA TORRE (380 Itálie); Margherita NAPOLI (380 Itálie) a Mimmo PARENTE (380 Itálie)

Vydání

RAIRO - Theoretical Informatics and Applications, EDP, 2006, 0988-3754

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.692

Kód RIV

RIV/00216224:14330/06:00016166

Organizační jednotka

Fakulta informatiky

UT WoS

000239790500007

Klíčová slova anglicky

Firing Squad Synchronization Problems

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 29. 6. 2009 21:49, RNDr. Lukáš Boháč

Anotace

ORIG CZ

V originále

We present several solutions to the Firing Squad Synchronization Problem on grid networks of different shapes. The nodes are finite state processors that work in unison with other processors and in synchronized discrete steps. The networks we deal with are: the line, the ring and the square. For all of these models we consider one- and two-way communication modes and we also constrain the quantity of information that adjacent processors can exchange at each step. We first present synchronization algorithms that work in time $n^2$, $n \log n$, $n\sqrt n$, $2^n$, where n is a total number of processors. Synchronization methods are described through so called signals that are then used as building blocks to compose synchronization solutions for the cases that synchronization times are expressed by polynomials with nonnegative coefficients.

Česky

Je prezentováno několik řešení problému FSSP v gridových sítích různých tvarů. Uzly jsou konečně stavové procesory, které pracují v souladu s ostatními procesory a v synchronizovaných diskrétních krocích.

Návaznosti

GA201/04/1153, projekt VaV
Název: Kvantové zdroje a primitiva
Investor: Grantová agentura ČR, Kvantové zdroje a primitiva
MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy