Vi föreslår och analyserar en kvasirandom analog av den klassiska push modellen för att sprida information i nätverk ("randomized rykte sprider"). I den klassiska modellen, i varje runda, väljer varje informerad vertex en granne slumpmässigt och informerar den, om det inte informerades tidigare. Det är känt att detta enkla protokoll lyckas sprida ett rykte från en vertex till alla andra inom O(log n) rundor på kompletta grafer, hyperkuber, slumpmässiga regelbundna grafer, Erdős-Rényi slumpmässiga grafer, och Ramanujan grafer med sannolikhet 1 - o(1). I kvasirandom modellen antar vi att varje vertex har en (cyklisk) lista över sina grannar. När det väl informerats, börjar det på en slumpmässig position på listan, men från och med då informerar sina grannar i ordningen på listan. Förvånansvärt nog håller de ovan nämnda gränserna fortfarande, oberoende av order från listorna. I vissa fall kan man visa ännu bättre gränser än för den klassiska modellen.
För modellen kvasirandom har det visat sig att sändningstiden där är av ordning (log n) REF med sannolikhet 1 – o(1).
Quasirandom Rumor Spreading
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}