Leader election in synchronous networks

[1] Y. Afek, E. Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, SIAM J. Comp., 20 (1981), 376-394.10.1137/0220023Search in Google Scholar

[2] Y. Afek, E. Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, in: Principles of Dist. Comp., ACM, 1985, 186-195.10.1145/323596.323613Search in Google Scholar

[3] P. Alimonti, P. Flocchini, N. Santoro, Finding the extrema of a distributed multiset, J. Parallel Dist. Comp., 37 (1996), 23-33.Search in Google Scholar

[4] I. Arrieta, F. Fari˜na, J. R. G. de Mendl, M. Raynal, Leader election: From Higham-Przytyckas algorithm to a gracefully degrading algorithm, Publications Internes de l’IRISA, inria-00605799, version 1, July 2011, 9 pages.10.1109/CISIS.2012.65Search in Google Scholar

[5] H. Attiya, J. van Leeuwen, N. Santoro, S. Zaks, Efficient elections in chordal ring networks, Algorithmica, 4 (1989), 437-446.10.1007/BF01553900Search in Google Scholar

[6] H. Attiya, M. Snir, M. K. Warmuth, Computing on an anonymous ring, J. ACM, 35 (1988), 845-875.10.1145/48014.48247Search in Google Scholar

[7] J. Augustine, T. Kulkarni, P. Nakhe, P. Robinson, Robust leader election in a fast-changing world, arXive arXiv:1310.4908v1 [cs.DC], 2013, 12 pages.10.4204/EPTCS.132.4Search in Google Scholar

[8] H. L. Bodlaender, Some lower bound results for decentralized extremafinding in rings of processors, J. Comp. System Sci., 42 (1991), 97-118.10.1016/0022-0000(91)90041-3Search in Google Scholar

[9] H. L. Bodlaender, New lower bound techniques for distributed leader finding and other problems on rings of processors, Theor. Comp. Sci., 81 (1991), 237-256.10.1016/0304-3975(91)90193-6Search in Google Scholar

[10] B. Bollob´as, Random Graphs (Cambridge Studies in Advanced Mathematics 73). Cambridge University Press, Cambridge, United Kingdom, 2001, XVIII + 498 pages.Search in Google Scholar

[11] E. D. Burkhard, D. Kowalski, G. Malewicz, A. A. Shwartsman, Distributed algorithms, in: (ed. A. Iv´anyi) Algorithms of Informatics, Vol. 2, mondAt Kiad´o, Budapest, 2007, 591-642. Electronic version: AnTon- Com, Budapest, 2011, http://progmat.hu/tananyagok/.Search in Google Scholar

[12] J. E. Burns, A formal model for message passing systems. Tech. Rep. 91, Computer Science Dep., Indiana Univ., Bloomington, IN, May 1980, 21 pages.Search in Google Scholar

[13] E. Chang, R. Roberts, An improved algorithm for decentralized extremafinding in circular configurations of processes, Comm. ACM, 22 (1979), 281-283.10.1145/359104.359108Search in Google Scholar

[14] W.-M.Chen, Cost distribution of the ChangRoberts leader election algorithm, Theoret. Comp. Sci., 369 (2006), 442-447. 10.1016/j.tcs.2006.08.019Search in Google Scholar

[15] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (3rd edition), The MIT Press Hill, Cambridge/New York, 2009, 1312 pages.Search in Google Scholar

[16] G. Coulouris, J. Dollimore, T. Kindberg, G. Blair, Distributed Systems: Concepts and Design (5th edition), Addison-Wesley, 2011, 1008 pages.Search in Google Scholar

[17] G. Critzer, A recursive formula for the number of labeled simple digraphs. OEIS (ed. N. J. A. Sloane), 2012, Sequence A003027.Search in Google Scholar

[18] S. Das, P. Flocchini, A. Nayak, N. Santoro, Effective elections for anonymous mobile agents, in: Algorithms and Computation, LNCS 4288, 2006, 732-743.10.1007/11940128_73Search in Google Scholar

[19] R. Dinitz, S. Moran, S. Rajsbaum, Bit complexity of breaking and acheaving symmetry in chains and rings, J. ACM, 55 (2008), 1-28.10.1145/1326554.1326557Search in Google Scholar

[20] D. Dolev, M. Klawe, M. Rodeh, An O(n log n) unidirectional distributed algorithm for extrema finding in a circle, J. Alg., 3 (1982) 245-260.10.1016/0196-6774(82)90023-2Search in Google Scholar

[21] L. Euler, Methodus generalis summandi progressiones. Commentarii Academiae Scientarum Imperialis Petropolitanae, 6 (1738), 68-97, Euler Archiv E025, and Opera Omnia, 1 (1911), 42-72.Search in Google Scholar

[22] L. Euler, De progressionibus harmonicus observationes, Commentarii Academiae Scientarum Imperialis Petropolitanae, 7 1740, Euler Archiv E043, 150-161 and Opera Omnia, 1 (1911), 87-100.Search in Google Scholar

[23] J. Faulhaber, Academia Algebrae, Johann Remelins Verlag, Ulm, 1631, 52 pages.Search in Google Scholar

[24] G. M. Fichtengolz, The Lecture on Differential and Integral Calculations, Vol. 1, 2, 3 (Russian), Nauka, Moskow, 1969, 607, 807, and 656 pages.Search in Google Scholar

[25] P. Flocchini, B. Mans, Optimal elections in hypercube, J. Parallel Dist. Comp., 33 1996, 76-83.10.1006/jpdc.1996.0026Search in Google Scholar

[26] G. N. Frederickson, N. A. Lynch, Electing a leader in a synchronous ring, J. ACM, 34 1987, 98-115.10.1145/7531.7919Search in Google Scholar

[27] J. García-López, C. Marijuán, Minimal strong digraphs, Discrete Math. 312 (2012), 737-744. Also arXiv, arXiv:1004.4827v1 [math.CO] 27 Apr 2010. Search in Google Scholar

[28] H. Garcia-Molina, Election in a distributed computing system, IEEE Trans. Comp., C-31 1982, 48-59.10.1109/TC.1982.1675885Search in Google Scholar

[29] C. Gavoille, Routing in distributed networks: Overview and open problems, ACM SIGACT News, 32 (2001), 36-52.10.1145/568438.568451Search in Google Scholar

[30] C. Georgiou, A. A. Shvartsman, N. A. Lynch, Cooperative Task-Oriented Computing: Algorithms and Complexity (Synthesis Lectures on Distributed Computing Theory), Morgan & Claypool Publishers, 2011, 168 pages.10.2200/S00376ED1V01Y201108DCT007Search in Google Scholar

[31] M. Ghaffni, N. A. Lynch, S. Sastry, Leader election using loneliness detection, in: Distributed Computing, LNCS 6950, 2011, Springer, Heidelberg, 2011, 268-282.10.1007/978-3-642-24100-0_26Search in Google Scholar

[32] F. Harary, Unsolved problems in the enumeration of graphs, Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl. 5 (1960), 63-95.Search in Google Scholar

[33] L. Higham, T. Przytycka, A simple, efficient algorithm for finding in rings, in: (ed. A. Schiper) Distributed Algorithms (7th Int. Workshp, WDAG’93, Lausanne, 1993), LNCS 725, Springer-Verlag, Berlin, 1993, 249-263.10.1007/3-540-57271-6_40Search in Google Scholar

[34] L. Higham, T. Przytycka, A simple, efficient algorithm for maximum finding on rings, Inf. Proc. Letters, 58 (1996), 319-324.10.1016/0020-0190(96)00069-5Search in Google Scholar

[35] D. S. Hirschberg, J. B. Sinclair, Decentralized extrema-finding in circular configuration of processes, Comm. ACM, 23 (1980), 627-628.10.1145/359024.359029Search in Google Scholar

[36] R. Ingram, T. Radeva, P. Shields, S. Viqar, J. E. Walter, J. L. Welch, A leader election algorithm for dynamic networks with clausal clocks, Distrib. Computing, 26 (2013), 75-97.10.1007/s00446-013-0184-1Search in Google Scholar

[37] R. Ingram, P. Shields, J. E. Walter, J. L. Welch, An asynchronous leader election algorithm for dynamic networks, IEEE International Symposium on Parallel & Distributed Processing (IPDPS 2009, Rome, 23-29 May 2009), 1-12.10.1109/IPDPS.2009.5161028Search in Google Scholar

[38] A. Itai, On the computational power needed to elect a leader, in: LNCS, 486, Springer-Verlag, Berlin, 1991, 29-40.10.1007/3-540-54099-7_3Search in Google Scholar

[39] A. Itai, M. Rodeh, Symmetry breaking in distributed networks, Inf. Comp. 88 (1990), 60-87. 10.1016/0890-5401(90)90004-2Search in Google Scholar

[40] A. Iványi, Parallel Algorithms (Hungarian), ELTE E¨otv¨os Kiad´o, Budapest, 2005.Search in Google Scholar

[41] T. Z. Kalamboukis, S. L. Mantzaris, Towards optimal distributed election on chordal rings, Information Proc. Letters, 38 (1991), 265-270.10.1016/0020-0190(91)90069-TSearch in Google Scholar

[42] M. Kalpathi, H. M. Mahmoud, M. D. Ward, Asymptotic properties of a leader election algorithm, J. Appl. Probab., 48 (2011), 569-575.10.1239/jap/1308662645Search in Google Scholar

[43] A. D. Kshemkalyani, M. Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, Cambridge, 2011, 756 pages.Search in Google Scholar

[44] G. Kim, G. Belford, A distributed election protocol for unreliable networks, J. Parallel Distr. Comp., 35 (1996), 35-42.10.1006/jpdc.1996.0065Search in Google Scholar

[45] C.-T. King, T. B. Gendreau, L. M. Ni, Reliable election in broadcast networks, J. Parallel Distr. Computing, 7 (1989), 521-540.10.1016/0743-7315(89)90034-8Search in Google Scholar

[46] D. E. Knuth, Concrete Mathematics (2nd edition), Addison-Wesley Publishing Co., 1994, 672 pages (1st edition: 1988).Search in Google Scholar

[47] E. S. Korach, S. Moran, S. Zaks, Optimal lower bounds for some distributed algorithms for a complete network of processors, Theoretical Comp. Sci., 64 (1989), 125-132.10.1016/0304-3975(89)90103-5Search in Google Scholar

[48] A. Kovács, Sums of the kth powers for the first twenty positive integers. Manuscript, Budapest, 2012.Search in Google Scholar

[49] S. Kovács, Zur Berechnung der Potenzsummen. Manuscript. Budapest, 2013, 11 pages.Search in Google Scholar

[50] E. Kranakis, D. Krizanc, Distributed computing on anonymous hypercube networks, J. Alg., 23 (1997), 32-50.10.1006/jagm.1996.0817Search in Google Scholar

[51] G. Le Lann, Distributed systems-towards a formal approach, in: (ed. B. Gilricst) Information Processing 77 (Toronto, 1977).Vol. 7. of Proc. of IFIP Congress, North Holland, Amsterdam, 1977, 155-160.Search in Google Scholar

[52] V. A. Liskovets, On a recurrent method for enumeration of graphs with labeled vertices (Russian), Dokl. AN SSSR, 184 (1969), 1284-1287.Search in Google Scholar

[53] V. A. Liskovets, The number of strongly connected oriented graphs (Russian), Mat. Zametki, 8 (1970), 721-732. Search in Google Scholar

[54] V. A. Liskovets, A contribution to the enumeration of strongly connected digraphs (Russian), Dokl. AN BSSR, 17 (1973), 1077-1080, 1163.Search in Google Scholar

[55] V. A. Liskovets, On a general enumerative scheme for labeled graphs (Russian), Dokl. AN BSSR, 21 (1977), 496-499.Search in Google Scholar

[56] V. A. Liskovets, Some easily derivable integer sequences. J. Int. Sequences, 3 (2000), Article 00.2.2.Search in Google Scholar

[57] V. A. Liskovets, Exact enumeration of acyclic deterministic automata. Discrete Appl. Math., 154, (2006), 537-551.10.1016/j.dam.2005.06.009Search in Google Scholar

[58] M. C. Loui, T. A. Matsushita, D. B. West, Election in a complete network with a sense of direction, Inform. Proc. Letters, 22 (1985), 185-187.10.1016/0020-0190(86)90025-6Search in Google Scholar

[59] N. A. Lynch, Distributed Algorithms (5th edition, The Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers, 2003, XIII + 873 pages (1st edition: 1996).Search in Google Scholar

[60] C. MacLaurin, A Treatise of Fluxions, Vol. 1. and 2, T. W. Ruddimans and T. Ruddimans, Edinburgh, 1742, 763 pages.Search in Google Scholar

[61] B. Mans, Optimal distributed algorithms in unlabeled tori and chordal rings, J. Parallel Distributed Comp., 46 (1997), 80-90.10.1006/jpdc.1997.1389Search in Google Scholar

[62] G. H. Masapati, H. Ural, Electing a leader in a synchronous recursively scalable network, in ICCI90, LNCS 468, Springer-Verlag, Berlin, 1990, 463-472.10.1007/3-540-53504-7_104Search in Google Scholar

[63] L. Mascheroni, Ad notationes ad calculum integralem Euleri, Vol. 1 and 2. Ticino, Italy, 1790 and 1792. Reprinted in Euler, L. Leonhardi Euleri Opera Omnia, Ser. 1, Vol. 12, Teubner, Leipzig, Germany, 415-542.Search in Google Scholar

[64] Yu. V. Matiyasevich, Alternatives to the Euler-Maclaurin formula for calculating infinite sums, Math. Notes, 88 (2010), 524-529.10.1134/S0001434610090245Search in Google Scholar

[65] T. D. Noe, Number of labeled weakly connected digraphs with n nodes for n = 1, . . . , 35. In OEIS (ed. N. J. A. Sloane), May 11, 2007. http://oeis.org/A053763/b053763.txt.Search in Google Scholar

[66] T. D. Noe, Number of labeled simple connected digraphs with n nodes for n = 1, . . . , 30. In OEIS (ed. N. J. A. Sloane), January 9, 2009. http://oeis.org/A003027/b003027.txt. Search in Google Scholar

[67] Y. Pan, A near-optimal multistage distributed algorithm for finding leaders in clustered chordal rings, Information Sci., 76 (1994), 131-140.10.1016/0020-0255(94)90071-XSearch in Google Scholar

[68] B. Pascal, Ouvres de Blaise Pascal, Vol. 3 (ed L. Brunschvicg, P. Bourroux), Nabu Press, Charleston, SC, 2010, 341-367. 1st edition: Blaise Pascal, Ouvres, 1640.Search in Google Scholar

[69] D. Peleg, Time-optimal leader election in general networks, J. Parallel Distr. Comp., 8 (1990), 96-99.10.1016/0743-7315(90)90074-YSearch in Google Scholar

[70] G. L. Peterson, An O(n log n) unidirectional distributed algorithm for the circular extremal problem, ACM Trans. Lang. Systems, 4 (1982), 758-762.10.1145/69622.357194Search in Google Scholar

[71] G. L. Peterson, Efficient algorithms for elections in meshes and complete networks, TR 140, Dept. of Computer Science, Univ. of Rochester, 1985, 5 pages.Search in Google Scholar

[72] Gy. Pólya, Mathematical Discovery on Understanding, Learning and Teaching Problem Solving. John Wiley & Sons, Inc, New York, NY, 1962, 216 pages.Search in Google Scholar

[73] R. W. Robinson, Counting labeled acyclic digraphs, in: New Directions in the Theory of Graphs (F. Harary, ed.), Academic Press, New York, 1973, 239-273.Search in Google Scholar

[74] R. W. Robinson, Counting unlabeled acyclic digraphs, Combinatorial Mathematics V. Lecture Notes in Math., 622 (1977), 28-43.10.1007/BFb0069178Search in Google Scholar

[75] R. W. Robinson, Table of n, a(n) for n = 1, . . . , 18, in OEIS (ed. N. J. A. Sloane), 2012. Sequence A003030.10.1002/dhe.20058Search in Google Scholar

[76] D. Rotem, E. Korach, N. Santoro, Analysis of a distributed algorithm for extrema finding in a ring, J. Parallel Distr. Comp., 4 (1987), 575-591.10.1016/0743-7315(87)90031-1Search in Google Scholar

[77] N. Santoro, M. Scheutzow, J. B. Sidney, On the expected complexity of distributed selection, J. Parallel Distr. Comp., 5 (1988), 194-203.10.1016/0743-7315(88)90029-9Search in Google Scholar

[78] A. Schrijver, Combinatorial Optimization. Vol. A, B, C (Algorithms and Combinatorics, Vol. 24, Springer-Verlag, Berlin, 2003, 1800 pages.Search in Google Scholar

[79] M. Seperhi, M. Godarzi, Leader election algorithm using heap structure, in: 12th WSEAS Int.l Conf. on Computers (Heraklion, Greece, July 23-25, 2008), 2008, 668-672. Search in Google Scholar

[80] W. Shi, K. Srimani, Leader election in hierarchical star network, J. Parallel Distr. Comp., 65 (2005), 1435-1442.10.1016/j.jpdc.2005.05.005Search in Google Scholar

[81] G. Singh, Leader election in complete networks, in: Proc. of the Eleventh Annual ACM Symp. on Principles of Distributed Computing, ACM Press, 1992, 179-190.10.1145/135419.135457Search in Google Scholar

[82] N. J. A. Sloane, Number of directed graphs (or digraphs) with n nodes. OEIS (ed. N. J. A. Sloane), 2013, Sequence A000273.Search in Google Scholar

[83] N. J. A. Sloane, Number of strongly connected digraphs with n labeled nodes, OEIS (ed. N. J. A. Sloane), 2013, Sequence A003030.Search in Google Scholar

[84] N. J. A. Sloane, Numerator of Bernoulli number Bn. OEIS (ed. N. J. A. Sloane), 2013, Sequence A027641.Search in Google Scholar

[85] N. J. A. Sloane, Denominator of Bernoulli number Bn., OEIS (ed. N. J. A. Sloane), 2013, Sequence A027642.Search in Google Scholar

[86] N. J. A. Sloane, The number of directed graphs on n vertices, OEIS (ed. N. J. A. Sloane), 2013, Sequence A003085.Search in Google Scholar

[87] N. J. A. Sloane, Jacobi (or Knonecker) symbol, OEIS (ed. N. J. A. Sloane), 2013, Sequence A034947.Search in Google Scholar

[88] N. J. A. Sloane, Bernoulli Numbers B2n/2n, in OEIS (ed. N. J. A. Sloane), 2013, Sequence A006953.Search in Google Scholar

[89] A. R. Smith, Cellular automata complexity trade-offs, Inf. Control., 18 (1971), 466-482.10.1016/S0019-9958(71)90501-8Search in Google Scholar

[90] P. Srimani, S. Lafiti, Some bounded degree communication networks and optimal leader election, in: Combinatorial Optimization in Communication Networks (Combinatorial Optimization), 18 (2006), 467-501.Search in Google Scholar

[91] G. Tel, Linear election in hypercubes, Parallel Proc. Letters, 5 (1995), 357-366.10.1142/S0129626495000333Search in Google Scholar

[92] G. Tel, Introduction to Distributed Systems (Second edition), Cambridge University Press, Cambridge, 2000, 612 pages (1st edition appeared in 1984).Search in Google Scholar

[93] P. Vitányi, Distributed elections in archimedean ring of processors, in Proc. 16th Ann. ACM Symp. on Theory of Computing, 1984, 542-547. 10.1145/800057.808725Search in Google Scholar

[94] E. W. Weisstein, Double Sum, From Mathworld-A Wolfram Web Resource, 2013, http://mathworld.wolfram.com/PowerSum.html.Search in Google Scholar

[95] E. W. Weisstein, Euler-Maclaurin Integration Formulas, 2013, http://mathworld.wolfram.com/Euler-MaclaurinIntegrationFormulas.html.Search in Google Scholar

[96] E. W. Weisstein, Euler-Mascheroni Constant, From Mathworld-A Wolfram Web Resource, 2013, http://mathworld.wolfram.com/Euler-MascheroniConstant.html.Search in Google Scholar

[97] E. W. Weisstein, Power Sum, From Mathworld-A Wolfram Web Resource, 2013, http://mathworld.wolfram.com/PowerSum.html.Search in Google Scholar

[98] S. Wolfram, Wolframalpha, 2013. http://www.wolframalpha.com.Search in Google Scholar

[99] E. M. Wright, Asymptotic enumeration of connected graphs. Proc. Roy. Soc. Edinburgh Sect. A, 68 (1968/1970), 298-308.10.1017/S0080454100008451Search in Google Scholar

[100] E. M. Wright, The number of strong digraphs, Bull. London Math. Soc., 3 (1971), 348-350.10.1112/blms/3.3.348Search in Google Scholar

[101] M. Yamashita, T. Kameda, Computing on anonymous networks: Parts I and II, IEEE Trans. Par. Dist. Syst., 7 (1996), 69-96. 10.1109/71.481599Search in Google Scholar