Obsah

IN-POS . Modely distribuovaných systémů

IN-POS . Modely distribuovaných systémů

Zadání

Základní pojmy a principy, synchronní a asynchronní komunikace.
Synchronizace.
Detekce ukončení.
Problém vzájemného vyloučení a problém uváznutí a jejich řešení.
Problém volby vedoucího prvku.
Vliv topologie a její znalosti/neznalosti na složitost řešení problému.

PA150, IV100

Vypracování

Základní pojmy a principy, synchronní a asynchronní komunikace.

Distribuovaný systém

Systém jehož hardwarové nebo softwarové komponenty počítačů mohou komunikovat a koordinovat svou činnost pouze předáváním zpráv.

DS:

umožňují souběžné řešení programů
každá komponenta (včetně propojovací sítě) může selhávat a obnovovat činnost nezávisle na okolí.
- ostatní se o stavu nedozvídají

Middleware

Softwarová vrstva ležící mezi aplikacemi a OS poskytující aplikacím aplikacím programovací abstrakci a maskování heterogenity podpůrných sítí, počítačů, operačních systému, programovacích jazyků,…

Režimy DS
- Synchronní výměna zpráv
  - výpočty probíhají v synchronních krocích (řízených globálními hodinami)
  - v každém běhu komponenty vyšlou a přijmou zprávy a provedou výpočet
  - přenos zprávy je kratší než jeden tik globálních hodin
- Asynchronní výměna zpráv
  - globální čas neexistuje
  - komponenty řízeny lokálními hodinami
  - délka přenosu zpráv je neomezena

Synchronizace

Cristianův algoritmus synchronizace hodin

Klient pošle dotaz časovému serveru a od získaného času přičte polovinu obrátky dotazu.

Berkeley algoritmus synchronizace hodin

MASTER uzel se periodicky ptá na čas SLAVE uzlů.
Přičte polovinu obrátky.
Zprůměruje a odešle aktuální hodnotu SLAVE uzlům.

Network Time Protocol

Možnost přesné synchronizace s UTC v Internetu.
Časové servery tvoří hierarchickou strukturu.
Módy synchronizace:
- Multicast: jeden server odesílá informace o čase skupině.
- Procedure-call: server vrací časové razítko na žádost (de facto Cristianův alg.)
- Symmetric: mezi 2 servery v různých úrovních; servery si opakovaně posílají časová razítka a opravují chyby

příčinné pořadí = „stalo-se-před“

Lokální čas
- budován na relaci „stalo-se-před“
  - pro události A, B v jednom procesu, kde A nastala před B: A→B
  - je-li A zaslání a B přijetí zprávy: A→B
  - platí transitivita: A→B,B→C ⇒ A→C
- pužíván místo fyzického času

Lamportovy hodiny

S každou událostí se sváže časové razítko.
Každý proces si udržuje logické (Lamportovy) hodiny. (Mapují částečné uspořádání.)
Odeslání zprávy:
- Odešleme aktuální časové razítko.
- Lokální čas zvýšíme o jedna.
Příjem zprávy:
- Porovnáme přijaté časové razítko s lokálními hodinami.
- Vezmeme větší z nich, zvýšíme o jedna a nastavíme jako lokální čas.
Vztah událostí:
- A→B ⇒ TS(A) < TS(B)

Ze vztahu TS(A)<TS(B) nevyplývá A→B.

Vektorové časové razítko

Řeší problém s opačnou implikací u Lamprotových hodin.
Místo jednoho razítka pro lokální čas použijeme vektor časových razítek. (velikost = počet procesů)
- iniciálně vyplněn nulami
Před odesláním proces zvýší „svůj“ prvek vektoru o jedna. Pouze toto časové razítko se odesílá se zprávou.
Při přijetí zprávy zaktualizujeme odesilatelům prvek vektoru na maximum z lokální a přijaté hodnoty.
Vztah vektorových razítek:
- V = V' iff všechny členy vektoru jsou si rovny
- V < V' iff V[j] < V'[j] pro j=1,…|V|

Detekce ukončení

Algoritmus synchronizace ukončení má za úkol zabezpečit následující:
V případě, že všechny procesy jsou ve stavu ukončen, pak se v konečném čase tuto skutečnost všechny procesy dozví.

Dijkstra-Scholten (DS)

Jestliže graf procesů je strom, pak každý listový proces při přechodu do stavu ukončen pošle signál svému otci.
Jakmile proces dostane signály od všech svých synů, pošle signál svému otci.
Jestliže všechny signály dostane iniciační proces, je distribuovaný výpočet ukončen.

Global State Recording Algorithm Candy & Lamport

iniciátor = proces iniciující zjištění globálního stavu
- zaznamená momentku svého lokálního stavu a odešle MARKER všem sousedům v DS
MARKER získal proces, který dosud nevypracoval momentku
- zaznamená momentku svého lokálního stavu a pošle ji iniciátorovi
- označí vstupní kanál, ze kterého přijal MARKER„, jako prázdný
- všem ostatním sousedům pošle MARKER
MARKER získal proces, který již momentku vypracoval
- zaznamená události od poslední momentky a pošle iniciátorovi
Iniciátor nakonec sestaví globální stav
- zná lokální momentky všech procesů
- zná zprávy v „éteru“
- Kanály jsou FIFO, tedy je globální momentka smysluplná ((ne)zahrnuté zprávy jsou odděleny v kanálech MARKERy).

Commit protokoly

Řeší atomicitu distribuované transakce.

2-fázový commit protokol

Distribuovaná dohoda, zda transakci končit řádně, či krachovat v prostředí s výpadky uzlů.

➕ řeší problém atomického ukončení
- jestli jedna subtransakce krachuje, krachuje celá transakce
- jestli se ukončí řádně všechny subtransakce, ukončí se řádně i celá transakce

2 fáze:

Hlasovací fáze
- koordinátor žádá o závazek k rozhodnutí, že subtransakci řádně ukončí
- participant ověří subtransakci na konzistenci dat a odpoví
Fáze vydání rozhodnutí
- Koordinátor vydává na základě získaných odpovědí rozhodnutí zda řádně ukončit, nebo krachovat.
  - Zprávy commit/abort.

Problém vzájemného vyloučení

Dva nebo více procesů obsahují kritické sekce sdružené s jistým sdíleným objektem, které se musí za běhu procesu vzájemně vyloučit.
privilegovaný proces = proces v kritické sekci

Podmínka bezpečnosti = v každé konfiguraci existuje nejvýš jeden privilegovaný proces.
Podmínka živosti = Jestliže se proces snaží dostat do KS, stane se privilegovaným v konečném čase.
- zamezuje uváznutí/stárnutí procesů
Podmínka spravedlnosti (jedna z uvedených)
- pořadí vstupů do KS = pořadí vydání žádosti o vstup
- každý ostatní proces DS smí žádající proces předběhnout nejvýše 1x

Řešení vzájemného vyloučení

Centralizované řešení
- klient-server (jeden KOORDINÁTOR řeší vzájemné vylučování libovolného počtu procesů)
- konstantní složitost
- request, reply+release zprávy

Distribuované řešení založené na regularitě komunikačních cest

Token ring

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolující vstup do kritické sekce.

lineární složitost

➕ Splněna podmínka bezpečnosti.
➕ Splněna podmínka živosti.
➕ Podmínka spravedlnosti splněna zajištěním maximálně jednoho předběhnutí od jiného procesu.
➖ Ztrátu příznaku je nutné řešit distribuovanou volbou procesu, který jej vygeneruje.
➖ Výpadek jednoho uzlu nutné řešit rekonstrukcí kruhu.

Raymond (tree)

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává po kostře grafu tak, aby se dodržela podmínka spravedlnosti na bázi časového pořadí vzniků žádostí.

Uzel držící příznak je kořenem stromu.
Uzel žádá o vstup do KS svého rodiče, ten jej předává po cestě ke kořeni.
Při předání příznaku se konfigurace stromu aktualizuje.

➕ Vzájemná výlučnost splněna trvale.
➕ Nemůže dojít ani k uváznutí ani ke stárnutí.

Distribuované řešení založené na získání souhlasu partnerských procesů

Suzuki-Kasami (token-passing)

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává na bázi cykličnosti uspokojování žádosti procesů.

Přehled nově generovaných a dosud nesplněných žádostí se udržuje distribuovaně v uzlech a v příznaku.

Proces pro žádost o vstup do KS odesílá všem uzlům REQUEST zprávu.
Uzel držící příznak po výstupu z KS odešle vybranému z procesů příznak.
Procesy si drží čísla žádostí od ostatních, token obsahuje pole s vyhověnými žádostmi.
Postupuje se cyklicky, přes procesy, které mají zájem.

➖ Procesy se musí navzájem znát.

Ricard-Agrawala (distribuovaná fronta)

Proces požadující vstoupit do kritické sekce pošle žádost o vstup s časovým razítkem všem ostatním.

Jestliže je příjemce v KS, neodpovídá a zařadí požadavek do fronty.
Jestliže příjemce není v KS a ani do ní nechce vstoupit, pak pošle zpět potvrzení práva vstupu do KS.
Jestliže příjemce není v KS, ale chce do ní vstoupit (sám vyslal žádost), porovná časovou značku své a přijaté žádosti.
- Pokud byla vlastní žádost odeslána dříve, neodpovídá a uloží žádost do fronty.
- Pokud byla přijatá žádost odeslána dříve, pošle zpět potvrzení práva vstupu do KS.

Až získá proces souhlas od všech, vstupuje do KS.
Po opuštění KS proces odešle potvrzení všem procesům, které má ve frontě.

➕ Je splněna podmínka bezpečnosti.
➕ Je splněna podmínka živosti.
➕ Komunikační složitost je lineární.
➖ Proces musí znát ostatní.
➖ Výpadek jednoho procesu způsobí kolaps celého systému. ⇒ Vhodné pro malé a stabilní množiny procesů.

Maekawa (hlasovací kvórum)

Každý proces obdrží jeden příznak (hlas).

Proces požadující vstup do KS žádá o příznak procesy ve svém kvóru.

kvůrum = podmnožina procesů, navzájem se protínají
Oslovený jej pošlu pokud jej ještě vlastní a sám se v KS nenachází.

Proces s hlasy od procesů v jeho kvóru vstupuje do KS. Po vystoupení hlasy vrací původním majitelům.

Podmínky kvóra:

bezpečnost:
- Každá dvojice volebních okrsků má alespoň jeden společný prvek.
- Každý má pouze jeden hlas. ⇒ Nemohou být současně zvoleny dva procesy.
spravedlnost
- Velikost okrsků je konstantní a každý proces je ve stejném počtu okrsků.
- Všechny procesy potřebují pro vstup do KS stejný počet hlasů

Uváznutí

Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P.

Stárnutí = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase

z důvodů vyšších priorit jiného procesu
z důvodů prevence uváznutí apod.

Nutná a postačující podmínka uváznutí

Nutné podmínky uváznutí:
1. vzájemné vyloučení (Mutual exclusion)
  - se sdíleným zdrojem může v jednom okamžiku pracovat právě jeden proces
2. inkrementálnost požadavků (též postupné uplatňování požadavků, Hold-and-Wait)
  - proces vlastnící nějaký zdroj potřebuje ke své činnosti zdroj další, který je však držen jiným procesem
3. nepředbíhatelnost (No preemption)
  - zdroje lze uvolnit pouze procesem, který tyto vlastní a to pouze dobrovolně, až je nebude potřebovat

Postačující podmínka:
- cyklické čekání (též zacyklení pořadí, Circular Wait)
  - důsledek prvních tří nutných podmínek
  - existuje množina n procesů (P₀…P_n), kde proces P₀ čeká na uvolnění zdroje drženého procesem P₁, P₁ čeká na uvolnění zdroje drženého P₂ atd. až P_n čeká na uvolnění zdroje drženého P₀

Metody ochrany proti uváznutí

Ochrana před uváznutím prevencí

zajistíme, že se systém nikdy nedostane do stavu uváznutí
zrušíme platnost některé nutné podmínky

nepřímé metody (zneplatnění nutné podmínky)
- Virtualizací prostředků zrušíme Mutual exclusion.
- Požadováním všech prostředků najednou zrušíme Hold-and-Wait.
  - ➕ nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností
  - ➖ neefektivní, možná prodleva při zahájení procesu
- Odebíráním prostředků zrušíme No preemption
  - Proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu.
  - ➕ vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor)
  - ➖ režijní ztráty, možnost cyklického restartu
přímé metody (nepřipuštění planosti postačující podmínky)
- uspořádáním prostředků zrušíme možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí
  - ➕ lze kontrolovat při kompilaci, nic se neřeší za běhu
  - ➖ neefektivní

Obcházení uváznutí

detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu
zamezujeme současné platnosti všech nutných podmínek
prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí)

Bankéřův algoritmus

Algoritmus používaný u zdrojů, kterých se přiděluje určité množství.
Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány.
Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury:
- Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj.
- Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj.
- Alokace: matice typu (n,m) definujici pocet zdroju kazde tridy aktualne alokovany kazdemu procesu. Jestlize Alokace(i,j) = k, potom proces Pi ma momentalne alokovano k instanci zdroje tridy Rj.
- Potreba: matice typu (n,m) definujici zbyly pocet instanci zdroje kazde tridy nutny k dokonceni ulohy. Jestlize Potreba(i,j) = k, potom proces Pi potrebuje k dokonceni sve ulohy dalsich k instanci tridy Rj.
Uvedene datove struktury se v case meni jak co do velikosti, tak co do hodnoty. Pro zjednoduseni prezentace Bankerova algoritmu definujme nasledujici vztah: Necht X a Y jsou vektory delky n. Potom X < = Y tehdy a jen tehdy, jestlize X(i) < = Y(i) pro vsechna i = 1, .. ,n. Napriklad jestlize X = (1, 7, 3, 2) a Y = (0, 3, 2, 1), potom Y < = X. Dale X < Y tehdy, jestlize X < = Y a zaroven X < > Y.
Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni.

Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C.

Zdroj typu A ma 10 instanci
zdroj typu B ma 5 instanci
zdroj typu C 7 instanci

Necht v case t0 je system v nasledujicim stavu:

	Alokace			Max			Volny
	A	B	C	A	B	C	A	B	C
P0	0	1	0	7	5	3	3	3	2
P1	2	0	0	3	2	2
P2	3	0	2	9	0	2
P3	2	1	1	2	2	2
P4	0	0	2	4	3	3

Obsah matice Potreba je definovan rozdilem Max - Alokace a je tedy:

	Potreba
	A	B	C
P0	7	4	3
P1	1	2	2
P2	6	0	0
P3	0	1	1
P4	4	3	1

V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence.

Detekce a obnova po uváznutí

Uváznutí povolíme, ale jeho vznik detekujeme a řešíme.
OS periodicky testuje existenci uváznutí (detekce cyklu v grafu).
➕ žádný prostoj při zahájení
➖ nutnost řešit uváznutí

Způsoby řešení uváznutí:

zrušit všechny uváznuté procesy (nejčastěji používaná metoda)
návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace)
postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků)
postupně předbíhat uváznuté procesy
zamezit současné platnosti nutných podmínek

Ignorování hrozby uváznutí

uváznutí je věc aplikace ne systému
způsob řešení zvolený většinou OS

Uváznutí v distribuovaném prostředí

Distribuovaná transakce

transakce zahrnující operace prováděné ve více uzle DS formou dílčích subtransakcí.

koordinátor
- registruje spuštění transakce
- registruje participanty (příp. dělí transakci na subtransakce)
- řeší akce při ukončování
správce
- udržuje deník pro obnovu transakcí
- participuje na schématu řízení souběžnosti
participant
- může kdykoliv volat koordinátora požadavkem abort-transaction, pokud není schopen pokračovat v řešení subtransakce.

Problém volby vedoucího prvku

Problém volby vůdce

Každý výpočet podle volebního algoritmu ve skupině procesů DS musí v konečném čase končit konfigurací, ve které je jeden jediný uzel v roli vůdce.

Každý proces se během existence může nacházet ve třech stavech:

nerozhodnutý (ve skupině běží volba)
vůdce (volba skončila)
není vůdce (volba skončila)

skupina anonymních procesů = procesy nemají ve skupině jedinečné id
- nelze řešit problém volby vůdce za splnění podmínky bezpečnosti (v každém kroku všichni dostávají shodné zprávy)
skupina neanonymních procesů = procesy mají ve skupině jedinečné id

uniformní algoritmus = procesy neznají počet procesů
- stejný algoritmus pro jakýkoliv rozměr skupiny
neuniformní algoritmus = procesy znají počet procesů ve skupině
- algoritmy pro různé rozměry skupiny se liší

volební běh
- Každý proces může najednou vyvolat pouze jeden běh.
- Může probíhat několik (N) paralelních běhů.
- Každý proces má právo i povinnost volit.
- Volba končí ukončením všech běhů.

Podmínka bezpečnosti
- Rozhodnutí volby je zvoleným procesem nezměnitelné.
- Vedoucím procesem je nejvýše jeden proces.
- Každý účastník volby má nastaveno elected na id zvoleného procesu.
Podmínka živosti
- Na volbě participují všechny procesy a nakonec nastaví elected na nějakou hodnotu.
- Jeden uzel se nakonec stává vůdcem.

Ring algorithm (LeLann)

Každý proces posílá své ID po kruhu.

Kruh je jednosměrný, každý proces má jednoho souseda a komunikace probíhá ve FIFO režimu.
Z příchozích zpráv si uzel postupně zapamatovává ID ostatních a zprávy přeposílá dál po kruhu.
Po přijetí zprávy s vlastním ID zná proces všechny procesy v kruhu a za vodce zvolí proces s nejmenším/největším ID.

Ring algorithm (Chang, Roberts)

Využitelnou topologií je obousměrný kruh. Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected.

Každý proces je ve stavu participant, nebo non-participant.
- Iniciálně jsou všichni non-participant.
Proces zahajující volební běh se označí za participant a pošle volící zprávu následníkovi.
Následník se rozhoduje:
- $P_i > P_{i+1}$ : přepošle
- $P_i < P_{i+1}$ a není účastníkem volby: přepošle $election(P_{i+1})$ a označí se za účastníka volby
- $P_i < P_{i+1}$ a je účastníkem volby: přijatou zprávu nepřeposílá = ruší volební běh ; volební běh $P_{i+1}$ běží
- $P_i = P_{i+1}$ : $P_{i+1}$ získal volící zprávu, kterou vyslal
  - přepne se do stavu vůdce
  - označí se za non-participant
  - pošle po kruhu ukončovací zprávu (ostatní si označí vůdce a zruší účast)

➕ sledování stavu participant/non-participant umožňujue likvidovat zbytečné násobné běhy.
➖ výpadek uzlu značí výpadek celé úlohy

nejhorší případ: O(n*n) zpráv
očekávaný počet zpráv: O(n log n) zpráv

Ring algorithm (Hirschberg-Sinclair)

Využitelnou topologií je obousměrný kruh.

Iniciátor v jednotlivých fázích r=0,1,.. posílá svou identitu do vzdálenosti nesoucí průzkumovou zprávu.
Identity cestující po kruhu jsou likvidovány jako u algoritmu Chang-Roberts.
Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti )
- Ostatní pouze přeposílají zprávy.

složitost: O(n log n)

Bully algorithm (Garcia-Molina)

Proces s nejvyšším ID si vynucuje svou vůdcovskou roli.

Použitelnost:

Proces může poslat zprávu každému z ostatních procesů.
Mohou se vyskytovat výpadky uzlů.
- Poznán na základě timeoutu.
Komunikační systém je spolehlivý (neztrácí se zprávy).

Když se proces rozhodne volit, zvolí sebe a zašle o tom zprávu všem procesům s vyšší prioritou.

Pokud proces přijme zprávu o volebním běhu:

má určitě vyšší prioritu ⇒ vrátí zamítavou odpověď
sám spouští volební běh → zašle zprávu všem procesům s vyšší prioritou

Odpovědi:

Když proces dostane zamítavou odpověď, existuje proces s vyšší prioritou ⇒ proces ukončí svůj volební běh.
Když nedostane zamítavou odpověď, volbu vyhrál.
- Nastaví se jako nový vůdce a pošle o tom všem ostatním procesům zprávu.

Pokud proces obnoví svůj běh, okamžitě zahajuje volební běh a nastane jedna ze dvou možností:

Stane se vůdcem.
Dozví se, kdo je vůdcem.

Vliv topologie a její znalosti/neznalosti na složitost řešení problému

: nejsem si 100% jistý, co se zde očekává (resp. z čeho čerpat)

Efektivita algoritmu velmi závisí na topologii sítě.
Zajímá nás komunikační složitost, případně časová složitost.

Horní odhad pro problém

Existuje algoritmus, který pro všechny topologie, vstupy, časování,… pracuje správně a vymění nejvíc f(n) zpráv.

Dolní odhad pro problém

Pro každý algoritmus existuje kombinace topologie, vstupu, časování,… že buď nepracuje správně, nebo vymění alespoň f(n) zpráv.

Časté topologie:
- úplný graf
  - každý komunikuje přímo s každým
- kruh
  - každý má levého a pravého souseda
  - všichni jsou uspořádání do kruhu
- jednosměrný kruh
  - každý má jen jednoho souseda
  - po N přeposláních se zpráva dostane zpět k původci
- 2D/3D mřížka
- strom

Pro tyto topologie existují často efektivnější algoritmy, protože lze spoléhat na jejich vlastnosti.
Pro globální algoritmy se může efektivita lišit na základě grafových vlastností:
- hustota grafu
- orientovanost
- poloměr

Pro tvorbu paralelních algoritmů je nejprve potřebné zvládnout několik principielních úloh:
- prohledávání uzlů
  - shout-and-echo (4m zpráv, 2diam(G) čas)
  - DFS (2m zpráv, 2m čas)
  - Awerbuch (4m zpráv, 4n−2 čas)
  - BFS:
    - Cheung’83 ( zpráv, m čas)
    - Cheung,Zhu’87 ( zpráv, čas)
- komunikace mezi uzly
- volba vůdce
  - globální algoritmus ( $\Omega (n \log n)$ zpráv)

Další důležité parametry:
- jednosměrnost/obousměrnost hran
- (ne)znalost sítě/sousedů
- existuje globální čas
- očíslování hran
- identifikace jednotlivých uzlů

Zdroje

slidy pa150 (podzim 2017)
http://statnice.dqd.cz/mgr-szz:in-pos:1-pos
http://statnice.dqd.cz/mgr-szz:in-tei:8-tei

mgr-szz/in-pos/4-pos.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru