Byzantine-tolerant uniform node sampling service in large-scale networks

References

• Lv Q, Cao P, Cohen E, et al. Search and replication in unstructured peer-to-peer networks. Proceedings of the International Conference on Supercomputing (ICS); Heidelberg, Germany; 2002. p. 84–95.
   Google Scholar
• Bollobás B. Random graphs. 2nd ed. Cambridge Studies in Advanced Mathematics; Cambridge: Cambridge University Press; 2001.
   Google Scholar
• Demers A, Greene D, Hauser C, et al. Epidemic algorithms for replicated database mangement. Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (PODC); Vancouver, British Columbia, Canada; 1987. p. 1–12.
   Google Scholar
• Jelasity M, Voulgaris S, Guerraoui R, et al. Gossip-based peer sampling. ACM Trans Comput Syst. 2007;25(3):1–36.
   Web of Science ®Google Scholar
• Stutzbach D, Rejaie R, Duffield NG, et al. On unbiased sampling for unstructured peer-to-peer networks. IEEE ACM Trans Netw. 2009;17(2):377–390.
   Web of Science ®Google Scholar
• Jesi GP, Montresor A, van Steen M. Secure peer sampling. Comput Netw. 2010;54(12):2086–2098.
   Web of Science ®Google Scholar
• Liu D, Ning P, Du W. Detecting malicious beacon nodes for secure location discovery in wireless sensor networks. Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS); Columbus, OH; 2005. p. 609–619.
   Google Scholar
• Singh A, Ngan TW, Druschel P, et al. Eclipse attacks on overlay networks: threats and defenses. Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM); Barcelona, Spain; 2006. p. 1–12.
   Google Scholar
• Anceaume E, Busnel Y, Gambs S. On the power of the adversary to solve the node sampling problem. In: Hameurlain A, Küng J, Wagner R, et al. editors. Transactions on large-scale data- and knowledge-centered systems XI. Vol. 8290, Lecture notes in computer science. Berlin: Springer; 2013. p. 102–126.
   Google Scholar
• Bortnikov E, Gurevich M, Keidar I, et al. Brahms: byzantine resilient random membership sampling. Comput Netw. 2009;53:2340–2359.
   Web of Science ®Google Scholar
• Sit E, Morris R. Security considerations for peer-to-peer distributed hash tables. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS); Cambridge, MA: Springer-Verlag; 2002. p. 261–269.
   Google Scholar
• Douceur J, Donath J. The sybil attack. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS); Cambridge, MA; 2002. p. 251–260.
   Google Scholar
• Awerbuch B, Scheideler C. Group spreading: a protocol for provably secure distributed name service. Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP); Turku, Finland; 2004. p. 183–195.
   Google Scholar
• Awerbuch B, Scheideler C. Towards a scalable and robust overlay network. Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS); Bellevue, WA; 2007.
   Google Scholar
• Anceaume E, Ludinard R, Sericola B, et al. Modeling and evaluating targeted attacks in large scale dynamic systems. Proceedings of the 41st IEEE/IFIP International Conference on Dependable Systems and Networks (DSN); Hong Kong, China; 2011.
   Google Scholar
• Anceaume E, Busnel Y, Rivetti N, et al. Identifying global icebergs in distributed streams. Proceedings of the 35th IEEE Symposium on Reliable Distributed Systems (SRDS'15); Sep.; Montreal, Canada; 2015.
   Google Scholar
• Rivetti N, Anceaume E, Busnel Y, et al. Online scheduling for shuffle grouping in distributed stream processing systems. Proceedings of the ACM/IFIP/USENIX Middleware 2016; Trento, Italy; 2016.
   Google Scholar
• Muthukrishnan SM. Data streams: algorithms and applications. Now Publishers Inc.; 2005. DOI:10.1561/040000000.
   Google Scholar
• Bar-Yossef Z, Jayram TS, Kumar R, et al. Counting distinct elements in a data stream. Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM); Cambridge, MA. Springer-Verlag; 2002. p. 1–10.
   Google Scholar
• Flajolet P, Martin GN. Probabilistic counting algorithms for data base applications. J Comput Syst Sci. 1985;31(2):182–209.
   Web of Science ®Google Scholar
• Kane DM, Nelson J, Woodruff DP. An optimal algorithm for the distinct element problem. Proceedings of the Symposium on Principles of Databases (PODS); Indianapolis, IN; 2010. p. 41–52.
   Google Scholar
• Alon N, Matias Y, Szegedy M. The space complexity of approximating the frequency moments. Proceedings of the 28th annual ACM symposium on Theory of computing (STOC); Philadelphia, PA; 1996. p. 20–29.
   Google Scholar
• Charikar M, Chen K, Farach-Colton M. Finding frequent items in data streams. Theor Comput Sci. 2004;312(1):3–15.
   Web of Science ®Google Scholar
• Chakrabarti A, Cormode G, McGregor A. A near-optimal algorithm for computing the entropy of a stream. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms; New Orleans, LA; 2007. p. 328–335.
   Google Scholar
• Lall A, Sekar V, Ogihara M, et al. Data streaming algorithms for estimating entropy of network traffic. Proceedings of the joint international conference on Measurement and modeling of computer systems (SIGMETRICS). ACM; Saint Malo, France; 2006. p. 145–156.
   Google Scholar
• Anceaume E, Busnel Y. Lightweight metric computation for distributed massive data streams. In: Herausgeber, Hameurlain A, Küng J, Wagner R, Akbarinia R, Pacitti E, editors. Transactions on Large-Scale Data and Knowledge-Centered Systems. Vol. 33; 2017. p. 1–33.
   Google Scholar
• Anceaume E, Busnel Y. Deviation estimation between distributed data streams. Proceedings of the 10th European Dependable Computing Conference (EDCC); Newcastle upon Tyne, UK; 2014.
   Google Scholar
• Lynch N. Distributed algorithms. San Francisco (CA): Morgan Kaufmann Publishers; 1996.
   Google Scholar
• Godfrey PB, Shenker S, Stoica I. Minimizing churn in distributed systems. Proceedings of the ACM SIGCOMM; Pisa, Italy; 2006; p. 147–158.
   Google Scholar
• Vitter J. Random sampling with a reservoir. ACM Trans Math Softw. 1985;37(57).
   Google Scholar
• Anceaume E, Busnel Y, Sericola B. Uniform node sampling service robust against collusions of malicious nodes. Proceedings of the 43rst IEEE/IFIP International Conference on Dependable Systems and Networks (DSN); Budapest, Hungary. 2013.
   Google Scholar
• Keneny JG, Snell JL. Finite Markov chains. Berlin: Springer-Verlag; 1976.
   Google Scholar
• Rubino G, Sericola B. On weak lumpability in Markov chains. J Appl Probab. 1989;26:446–457.
   Web of Science ®Google Scholar
• Cormode G, Muthukrishnan SM. An improved data stream summary: the count-min sketch and its applications. J Algorithms. 2005;55(1):58–75.
   Web of Science ®Google Scholar
• Archive TIT. Available from: http://ita.ee.lbl.gov/html/traces.html [Lawrence berkeley national laboratory]; Online on Feb. 2016.
   Google Scholar
• Nakamoto S. Bitcoin: a peer-to-peer electronic cash system; 2008. Available from: https://bitcoin.org/bitcoin.pdf
   Google Scholar
• Chaum D. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun ACM. 1988;24(2):84–90.
   Google Scholar
• Kokoris-Kogias E, Jovanovic P, Gasser L, et al. Omniledger: a secure, scale-out, decentralized ledger via sharding. IEEE Symposium on Security and Privacy (SSP); Freiburg, Germany; 2018.
   Google Scholar
• Badertscher C, Gaži P, Kiayias A, et al. Ouroboros genesis: composable proof-of-stake blockchains with dynamic availability. ACM SIGSAC Conference on Computer and Communications Security (CCS); Toronto, Canada; 2018.
   Google Scholar
• Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies. Proceedings of the 26th Symposium on Operating Systems Principles; Shanghai, China. ACM; 2017. p. 51–68.
   Google Scholar
• Daian P, Pass R, Shi E. Snow White: Provably Secure Proofs of Stake [Cryptology eprint archive, report 2016/919]; 2016. Available from: https://eprint.iacr.org/2016/919
   Google Scholar
• Durand A, Hébert G, Toumi K, et al. The stakecube blockchain: instantiation, evaluation and applications. Proceedings of IEEE International Conference on Blockchain Computing and Applications (BCCA); Antalya, Turkey; 2020.
   Google Scholar