I en sammansmältning slumpmässig gång, en uppsättning partiklar gör oberoende diskret-tid slumpmässiga promenader på en graf. När en eller flera partiklar möts på en vertex, de förenas för att bilda en enda partikel, som sedan fortsätter slumpmässiga gå genom grafen. Kolbildning slumpmässiga promenader kan användas för att uppnå samförstånd i distribuerade nätverk, och är grunden för den självstabiliserande ömsesidiga uteslutning algoritmen i Israel och Jalfon [14]. Låt G = (V, E), vara en oriktad, ansluten n vertex graf. Låt C(n) vara den förväntade tiden för alla partiklar att sammansmälta, när initialt en partikel är placerad vid varje vertex. Vi studerar problemet med att begränsa kolescenstiden C(n) för allmänna klasser av grafer. Vårt allmänna resultat är, det är graden av vertex v, d är den genomsnittliga vertex graden, och λ2 är det andra eigenvärdet av övergångsmatrisen av den slumpmässiga promenaden. Parametern v är en indikator på variabiliteten av vertex grader: 1 ≤ v = O(n), med v = 1 för regelbundna grafer. Vår allmänna bundet på C (n) håller förutsatt att den maximala vertex grad är O(m 1− ), där m är antalet kanter i grafen. Detta resultat innebär t.ex. att C(n) = O(n/(1 − λ2)) för d-regelbundna grafer med expansionsparameteriserad av eigenvärdesgapet 1 − λ2. O(n/(ν(1 − λ2))-bindningen är sublinjär för vissa klasser av grafer med skev gradfördelning. Ett system av sammansmältningspartiklar där initialt en partikel är placerad vid varje vertex, motsvarar följande röstmodell. Inledningsvis varje vertex har en distinkt åsikt, och vid varje steg varje vertex ändrar sin åsikt till en slumpmässig granne. Röstningsprocessen kan användas för ledarval i ett distribuerat sammanhang. Låt E(Cv) vara * Arbete som stöds av Royal Society IJP bidrag "Random promenader, interagerande partiklar och snabbare nätverksprospektering." Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. PoDC'12, 16–18 juli 2012, Madeira, Portugal. Copyright 2012 ACM 978-1-4503-1450 förväntade sig att omröstningen skulle slutföras, det vill säga att ett unikt yttrande skulle komma fram. Det är känt att E(Cv) = C(n), så våra resultat innebär att E(Cv) = O(n/(ν(1 − λ2)). Vi undersöker också hur omröstningstiden förbättras när en vertex framkallar mer än ett yttrande i varje steg. I en modell som vi kallar min-voting, har varje vertex initialt en distinkt åsikt hämtad från en linjärt ordnad domän. Vid varje steg varje vertex tar åsikter från två slumpmässiga grannar och håller de mindre. Vi visar att för regelbundna grafer med mycket goda expansionsegenskaper slutförs röstningen i O(log n) tid med hög sannolikhet. Detta resultat kan ses som ett exempel på "makt av två val" i distribuerade omröstningar.
Ett annat relaterat ämne är studien av sammansmältningsprocesser och röstmodeller (se t.ex. REF ).
Coalescing random walks and voting on graphs
{'venue': "PODC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}