We study the deterministic binary majority process which is defined as follows. We are given a graph G = (V, E) where each node has one out of two opinions. The process runs in discrete rounds where in every round each node computes and adopts the majority opinion among all of its neighbors. It was proved independently by Goles and Olivos, and Poljak and Sura with the same potential function argument that the process always converges to a two-periodic state. Their proof was popularized in the Puzzled columns of Communications of the ACM. Let the convergence time of a given graph, for a given initial opinion assignment, be the time it takes until the two-periodic state is reached. In this work we give bounds on the voting time, which is the maximum convergence time over all possible initial opinion assignments. Prischknecht et al. note that the potential argument by Goles et al. can be used to prove an O (|E|) upper bound on the voting time which is also shown to be tight.
展开▼
机译：我们研究确定性二进制多数过程，其定义如下。我们给定一个图G =（V，E），其中每个节点有两个意见中的一个。该过程在不连续的轮次中运行，在每个轮次中，每个节点都进行计算并采用其所有邻居中的多数意见。 Goles和Olivos以及Poljak和Sura分别用相同的势函数论证证明了这一过程，它总是收敛于两个周期的状态。他们的证明在ACM通讯的困惑栏目中得到了普及。对于给定的初始意见分配，给定图的收敛时间为直到达到两个周期状态所花费的时间。在这项工作中，我们对投票时间设定了界限，投票时间是所有可能的初始意见分配中的最大收敛时间。 Prischknecht等。注意，Goles等人的潜在论点。可以用来证明投票时间的O（| E |）上限，该上限也很严格。
展开▼
