Consensus and leader election are fundamental problems in distributed systems. Consensus is the problem in which all processes in a distributed computation must agree on some value. Average consensus is a popular form of consensus, where the agreed upon value is the average of the initial values of all the processes. In a typical solution for consensus, each process learns the value of others' to determine the final decision. However, this is undesirable if processes want to keep their values secret from others. With this motivation, we present a solution to privacy-preserving average consensus, where no process can learn the initial value of any other process. Additionally, we augment our approach to provide outlier resistance, where extreme values are not included in the average calculation. Privacy is fully preserved at every stage, including preventing any process from learning the identities of processes that hold outlier values. To our knowledge, this is the first privacy-preserving average consensus algorithm featuring outlier resistance. In the context of leader election, each process votes for the one that it wants to be the leader. The goal is to ensure that the leader is elected in such a way that each vote remains secret and the sum of votes remain secret during the election. Only the final vote tally is available to all processes. This ensures that processes that vote early are not able to influence the votes of other processes. We augment our approach with shallow ranked voting by allowing processes to not only vote for a single process, but to designate a secondary process to vote towards in the event that their primary vote's candidate does not win the election.
翻译:在分布式系统中,共识和领导人选举是根本问题。 共识是所有在分配式计算中的所有进程都必须就某种价值达成一致的问题。 平均共识是一个问题。 平均共识是流行的共识形式,其中商定的价值是所有进程最初价值的平均值。 在典型的共识解决方案中,每个进程都学习他人的价值,以决定最后的决定。 但是,如果进程想要保持其价值观与他人之间的秘密,这是不可取的。 有了这种动机,我们提出了一个隐私保护平均共识的解决办法,没有任何进程能够了解任何其他进程的初步价值。 此外,我们加大了我们的方法,以提供更强烈的抵制,即极端价值没有包括在平均计算中。 在每个阶段都充分保持了隐私,包括防止任何进程学习持有超值的进程特性。 据我们所知,这是第一个隐私保留平均共识的算法,这种算法是超越他人的抵制。 在领导人选举中,每个进程都投票支持它想要成为领导者。 目标是确保领导人当选的方式是保密的,而在选举过程中,绝对的票数仍然是秘密的。 在选举过程中,只有最后的投票方式才能增加选举过程。