Abstrakt. Kollektiv myntflipping är problemet med att producera gemensamma slumpmässiga bitar i en distribuerad datormiljö med kontradiktoriska fel. Vi anser att den perfekta informationsmodellen: all kommunikation sker genom sändning och korrupta spelare beräknas vara obundna. Protokoll i denna modell kan innebära många asynkrona rundor. Vi antar att ärliga spelare kommunicerar endast jämnt slumpmässiga bitar. Vi visar att alla n-player mynt-flipning protokoll som är motståndskraftig mot korrupta koalitioner av linjär storlek måste använda antingen åtminstone [1/2 − o(1)] log * n kommunikationsrundor eller åtminstone [log (2k−1) n] 1−o(1) kommunikationsbitar i kth round, där log (j) betecknar logaritmen itererade j gånger. Särskilt protokoll som använder en bit per runda kräver [1/2 − o(1)] log * n rundor. Dessa gränser gäller också för problemet med valet av ledare. Den primära komponenten i detta resultat är en ny bundet på påverkan av slumpmässiga uppsättningar av variabler på Booleska funktioner. Slutligen, i den ena omgången, med hjälp av andra metoder visar vi en ny gräns för påverkan av uppsättningar av variabler av storlek βn för β > 1/3.
Russell, Saks och Zuckerman REF visade då att alla protokoll som är säkra i närvaro av linjärt många korruption måste antingen ha minst (1/2 − o(1)) · logg * (n) rundor, eller kommunicera många bitar per runda.
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}