Skip to main content

2018 | OriginalPaper | Buchkapitel

Byzantine Preferential Voting

verfasst von : Darya Melnyk, Yuyi Wang, Roger Wattenhofer

Erschienen in: Web and Internet Economics

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the Byzantine agreement problem, n nodes with possibly different input values aim to reach agreement on a common value in the presence of \(t<n/3\) Byzantine nodes which represent arbitrary failures in the system. This paper introduces a generalization of Byzantine agreement, where the input values of the nodes are preference rankings of three or more candidates. We show that consensus on preferences, which is an important question in social choice theory, complements already known results from Byzantine agreement. In addition, preferential voting raises new questions about how to approximate consensus vectors. We propose a deterministic algorithm to solve Byzantine agreement on rankings under a generalized validity condition, which we call Pareto-Validity. These results are then extended by considering a special voting rule which chooses the Kemeny median as the consensus vector. For this rule, we derive a lower bound on the approximation ratio of the Kemeny median that can be guaranteed by any deterministic algorithm. We then provide an algorithm matching this lower bound. To our knowledge, this is the first non-trivial generalization of multi-valued Byzantine agreement to multiple dimensions which can tolerate a constant fraction of Byzantine nodes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 23:1–23:27 (2008)MathSciNetCrossRef Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 23:1–23:27 (2008)MathSciNetCrossRef
2.
Zurück zum Zitat Arrow, K.J.: Social Choice and Individual Values, 1st edn. Cowles Foundation, New Haven (1951)MATH Arrow, K.J.: Social Choice and Individual Values, 1st edn. Cowles Foundation, New Haven (1951)MATH
3.
Zurück zum Zitat Arrow, K.J.: Social Choice and Individual Values, 2nd edn. Wiley, New York (1963)MATH Arrow, K.J.: Social Choice and Individual Values, 2nd edn. Wiley, New York (1963)MATH
4.
Zurück zum Zitat Bartholdi, J., Tovey, C.A., Trick, M.A.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6(2), 157–165 (1989)MathSciNetCrossRef Bartholdi, J., Tovey, C.A., Trick, M.A.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6(2), 157–165 (1989)MathSciNetCrossRef
5.
Zurück zum Zitat Bartholdi, J.J., Tovey, C.A., Trick, M.A.: The computational difficulty of manipulating an election. Soc. Choice Welfare 6(3), 227–241 (1989)MathSciNetCrossRef Bartholdi, J.J., Tovey, C.A., Trick, M.A.: The computational difficulty of manipulating an election. Soc. Choice Welfare 6(3), 227–241 (1989)MathSciNetCrossRef
6.
Zurück zum Zitat Bassett, G.W., Persky, J.: Robust voting. Public Choice 990(3), 299–310 (1999)CrossRef Bassett, G.W., Persky, J.: Robust voting. Public Choice 990(3), 299–310 (1999)CrossRef
7.
Zurück zum Zitat Ben-Or, M.: Another advantage of free choice (extended abstract): completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC 1983, pp. 27–30 (1983) Ben-Or, M.: Another advantage of free choice (extended abstract): completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC 1983, pp. 27–30 (1983)
9.
Zurück zum Zitat Berman, P., Garay, J.A., Perry, K.J.: Towards optimal distributed consensus. In: 30th Annual Symposium on Foundations of Computer Science, FOCS, October 1989 Berman, P., Garay, J.A., Perry, K.J.: Towards optimal distributed consensus. In: 30th Annual Symposium on Foundations of Computer Science, FOCS, October 1989
10.
Zurück zum Zitat Betzler, N., Niedermeier, R., Woeginger, G.J.: Unweighted coalitional manipulation under the Borda rule is NP-hard. In: IJCAI, vol. 11, pp. 55–60 (2011) Betzler, N., Niedermeier, R., Woeginger, G.J.: Unweighted coalitional manipulation under the Borda rule is NP-hard. In: IJCAI, vol. 11, pp. 55–60 (2011)
12.
Zurück zum Zitat Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of Computational Social Choice, 1st edn. Cambridge University Press, New York (2016)CrossRef Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of Computational Social Choice, 1st edn. Cambridge University Press, New York (2016)CrossRef
14.
Zurück zum Zitat Davies, J., Katsirelos, G., Narodytska, N., Walsh, T.: Complexity of and algorithms for Borda manipulation. In: AAAI, vol. 11, pp. 657–662 (2011) Davies, J., Katsirelos, G., Narodytska, N., Walsh, T.: Complexity of and algorithms for Borda manipulation. In: AAAI, vol. 11, pp. 657–662 (2011)
15.
Zurück zum Zitat Diaconis, P., Graham, R.L.: Spearman’s footrule as a measure of disarray. J. R. Stat. Soc. Ser. B (Methodol.) 39, 262–268 (1977)MathSciNetMATH Diaconis, P., Graham, R.L.: Spearman’s footrule as a measure of disarray. J. R. Stat. Soc. Ser. B (Methodol.) 39, 262–268 (1977)MathSciNetMATH
16.
Zurück zum Zitat Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing consensus with the power of two choices. In: Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA (2011) Doerr, B., Goldberg, L.A., Minder, L., Sauerwald, T., Scheideler, C.: Stabilizing consensus with the power of two choices. In: Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA (2011)
17.
Zurück zum Zitat Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499–516 (1986)MathSciNetCrossRef Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499–516 (1986)MathSciNetCrossRef
18.
Zurück zum Zitat Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International Conference on World Wide Web, WWW 2001, pp. 613–622. ACM, New York (2001) Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International Conference on World Wide Web, WWW 2001, pp. 613–622. ACM, New York (2001)
19.
Zurück zum Zitat Fekete, A.D.: Asymptotically optimal algorithms for approximate agreement. Distrib. Comput. 4(1), 9–29 (1990)MathSciNetCrossRef Fekete, A.D.: Asymptotically optimal algorithms for approximate agreement. Distrib. Comput. 4(1), 9–29 (1990)MathSciNetCrossRef
20.
Zurück zum Zitat Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14(4), 183–186 (1982)MathSciNetCrossRef Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14(4), 183–186 (1982)MathSciNetCrossRef
21.
Zurück zum Zitat Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRef Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRef
22.
Zurück zum Zitat Kemeny, J.G.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959) Kemeny, J.G.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959)
23.
Zurück zum Zitat Kemeny, J.G., Snell, J.L.: Mathematical Models in the Social Sciences. Introductions to Higher Mathematics, Blaisdell, Waltham (Mass.) (1962) Kemeny, J.G., Snell, J.L.: Mathematical Models in the Social Sciences. Introductions to Higher Mathematics, Blaisdell, Waltham (Mass.) (1962)
24.
Zurück zum Zitat Kendall, M.G.: A new measure of rank correlation. Biometrika 30(1/2), 81–93 (1938)CrossRef Kendall, M.G.: A new measure of rank correlation. Biometrika 30(1/2), 81–93 (1938)CrossRef
25.
26.
Zurück zum Zitat Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRef
27.
Zurück zum Zitat May, K.O.: A set of independent necessary and sufficient conditions for simple majority decision. Econometrica 20(4), 680–684 (1952)MathSciNetCrossRef May, K.O.: A set of independent necessary and sufficient conditions for simple majority decision. Econometrica 20(4), 680–684 (1952)MathSciNetCrossRef
28.
Zurück zum Zitat Melnyk, D., Wattenhofer, R.: Byzantine agreement with interval validity. In: 37th Annual IEEE International Symposium on Reliable Distributed Systems, SRDS (2018) Melnyk, D., Wattenhofer, R.: Byzantine agreement with interval validity. In: 37th Annual IEEE International Symposium on Reliable Distributed Systems, SRDS (2018)
29.
Zurück zum Zitat Mendes, H., Herlihy, M.: Multidimensional approximate agreement in Byzantine asynchronous systems. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC (2013) Mendes, H., Herlihy, M.: Multidimensional approximate agreement in Byzantine asynchronous systems. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC (2013)
30.
Zurück zum Zitat Mendes, H., Herlihy, M., Vaidya, N., Garg, V.K.: Multidimensional agreement in Byzantine systems. Distrib. Comput. 28(6), 423–441 (2015)MathSciNetCrossRef Mendes, H., Herlihy, M., Vaidya, N., Garg, V.K.: Multidimensional agreement in Byzantine systems. Distrib. Comput. 28(6), 423–441 (2015)MathSciNetCrossRef
31.
Zurück zum Zitat Pareto, V.: Manuale di Economia Politica con una Introduzione alla Scienza Sociale. Società Editrice Libraria (1919) Pareto, V.: Manuale di Economia Politica con una Introduzione alla Scienza Sociale. Società Editrice Libraria (1919)
32.
Zurück zum Zitat Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)MathSciNetCrossRef Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)MathSciNetCrossRef
33.
Zurück zum Zitat Procaccia, A.D., Rosenschein, J.S., Kaminka, G.A.: On the robustness of preference aggregation in noisy environments. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, p. 66. ACM (2007) Procaccia, A.D., Rosenschein, J.S., Kaminka, G.A.: On the robustness of preference aggregation in noisy environments. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, p. 66. ACM (2007)
34.
Zurück zum Zitat Srikanth, T., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distrib. Comput. 2(2), 80–94 (1987)CrossRef Srikanth, T., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distrib. Comput. 2(2), 80–94 (1987)CrossRef
35.
Zurück zum Zitat Stolz, D., Wattenhofer, R.: Byzantine agreement with median validity. In: 19th International Conference on Principles of Distributed Systems, OPODIS (2015) Stolz, D., Wattenhofer, R.: Byzantine agreement with median validity. In: 19th International Conference on Principles of Distributed Systems, OPODIS (2015)
36.
Zurück zum Zitat Tideman, N.: The single transferable vote. J. Econ. Perspect. 9(1), 27–38 (1995)CrossRef Tideman, N.: The single transferable vote. J. Econ. Perspect. 9(1), 27–38 (1995)CrossRef
37.
Zurück zum Zitat Tseng, L.: Voting in the presence of Byzantine faults. In: 2017 IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC), January 2017 Tseng, L.: Voting in the presence of Byzantine faults. In: 2017 IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC), January 2017
38.
Zurück zum Zitat Vaidya, N.H., Garg, V.K.: Byzantine vector consensus in complete graphs. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC (2013) Vaidya, N.H., Garg, V.K.: Byzantine vector consensus in complete graphs. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC (2013)
39.
Zurück zum Zitat Wattenhofer, R.: Distributed Ledger Technology: The Science of the Blockchain, 2nd edn. CreateSpace Independent Publishing Platform, Scotts Valley (2017) Wattenhofer, R.: Distributed Ledger Technology: The Science of the Blockchain, 2nd edn. CreateSpace Independent Publishing Platform, Scotts Valley (2017)
Metadaten
Titel
Byzantine Preferential Voting
verfasst von
Darya Melnyk
Yuyi Wang
Roger Wattenhofer
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-030-04612-5_22