Technika více pokusů - Multi-trials technique

The technika více pokusů Schneider a kol. je zaměstnán pro distribuované algoritmy a umožňuje efektivní rozdělení symetrie. Prolomení symetrie je nutné například při problémech s alokací prostředků, kdy mnoho entit chce přistupovat ke stejnému prostředku souběžně. Mnoho předávání zpráv algoritmy obvykle používají jeden pokus o přerušení symetrie na výměnu zpráv. The technika více pokusů překračuje tento přístup tím, že při každé výměně zpráv využívá více pokusů.[1]

Například v jednoduchém algoritmu pro výpočet O (Δ) vrchol zbarvení, kde Δ označuje maximální stupeň v grafu, každý nezbarvený uzel náhodně vybere dostupnou barvu a ponechá ji, pokud žádný soused (souběžně) nezvolí stejnou barvu. U techniky více pokusů uzel postupně zvyšuje počet vybraných barev v každém kole komunikace. Tato technika může přinést více než exponenciální snížení požadovaných komunikačních kol. Pokud je však maximální stupeň Δ malý, existují účinnější techniky, např. (rozšířená) technika házení mincí od Richarda Colea a Uzi Vishkin.[2]

Poznámky

  1. ^ Schneider (2010)
  2. ^ Schneider (2008)

Reference

  • Schneider, J. (2010), „Nová technika pro rozdělení distribuované symetrie“ (PDF), Sborník řízení Symposium on Principles of Distributed Computing
  • Schneider, J. (2008), „Log-star distribuovaný maximální nezávislý množinový algoritmus pro grafy ohraničené růstem“ (PDF), Sborník řízení Symposium on Principles of Distributed Computing