Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks

1. Awerbuch, B.: Optimal distributed algorithms for minimal weight spanning tree, counting, leader election and related problems. In Proc. ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 230–240.

   Google Scholar 

2. Burns, J.E.: A formal model for message passing systems. Technical Report TR-91, Computer Science Department, Indiana University, Bloominggton, Sept. 1980.

   Google Scholar 

3. Dobrev, S.-Ružička, P.: Linear broadcasting and N log log N election in unoriented hypercubes. In Proc. of SIROCCO’97, Carleton Press, Ascona, Switzerland, 1997, pp. 52–68.

   Google Scholar 

4. Dobrev, S.-Ružička, P.: Yet Another Modular Technique for Efficient Leader Election. Proc. of SOFSEM’98, LNCS 1521, Springer-Verlag, 1998, pp. 312–321.

   Google Scholar 

5. Dobrev, S.: Time and Message Optimal Election in Oriented Hypercubes. Submitted to SWAT’2000.

   Google Scholar 

6. Flocchini, P.-Mans, B.: Optimal Elections in Labeled Hypercubes. Journal of Parallel and Distributed Computing33(1), 1996, pp. 76–83.

   Article  Google Scholar 

7. Flocchini, P.-Mans, B.-Santoro, N.: Sense of direction:definition, properties and classes. Networks 32(3) 1998, pp. 165–180.

   Article  MATH  MathSciNet  Google Scholar 

8. Gallager, R. G.-Humblet, P.A.-Spira, P. M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Programming Languages and Systems 5, 1983, pp. 66–77.

   Google Scholar 

9. Hirschberg, D.S.-Sinclair, J.B.: Decentralized extrema-finding in circular configurations of processes. Communication of the ACM23(11) 1980, pp. 627–628.

   Article  MATH  MathSciNet  Google Scholar 

10. Israeli, A.-Kranakis, E.-Krizanc, D.-Santoro, N.: Time-message Trade-offs for the Weak Unison Problem, Nordic Journal of Computing 4(1997), pp. 317–329.

    MATH  MathSciNet  Google Scholar 

11. Korach, E.-Moran, S.-Zaks, S.: Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors TCS 64(1), 1989, pp. 125–132.

    MATH  MathSciNet  Google Scholar 

12. Loui, M.C.-Matsushita, T.A.-West, D.B.: Election in complete networks with a sense of direction. Inf. Proc. Lett.22, 1986, pp. 185–187. Addendum: Inf. Proc. Lett. 28, 1988, p. 327.

    Article  MathSciNet  Google Scholar 

13. Mans, B.: Optimal Distributed Algorithms in Unlabelled Tori and Chordal Rings. Journal of Parallel and Distributed Computing46(1), 1997, pp. 80–90.

    Article  MATH  MathSciNet  Google Scholar 

14. Peterson, G.L.: Efficient algorithms for elections in meshes and complete neworks. Technical Report TR140 Dept. of Computer Science, Univ. of Rochester, Rochester, NY 14627, 1985.

    Google Scholar 

15. Singh, G.: Leader Election in Complete Networks. SIAM J. COMPUT., 26(3), 1997, pp. 772–785. Preliminary version containing the proof of the lower bound appeared in Proc. of 11th Symposium on Principles of Distributed Computing, 1992

    Article  MATH  MathSciNet  Google Scholar 

16. Singh, G: Leader Election Using Sense of Direction. Distributed Computing, 10(3), 1997, pp. 159–165.

    Article  Google Scholar 

17. Santoro, N.-Widmayer, P.: Distributed function evaluation in presence of transmission faults, in Proc. of SIGAL’90, Tokyo, 1990; LNCS 450, Springer Verlag, 1990, pp. 358–369.

    Google Scholar 

18. Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge, 1994.

    Book  MATH  Google Scholar 

19. Tel, G.: Linear Election in Oriented Hypercubes. Parallel Processing Letters 5, 1995, pp. 357–366.

    Google Scholar 

Download references