COMP 4001   DISTRIBUTED COMPUTING

ASSIGNMENT 2 

Due date:  October 31, 2011  (BEFORE CLASS)

(see the course announcements for submission instructions)


 

PART   I       (individual)
  • 1. Design a protocol that allows to wake-up all the entities in an oriented mesh using less than 2n messages regardless of the location and the number of initiators.

  • 2. Show how to modify protocol UniAlternate so that, without changing its message cost, it does not require Message Ordering. Discuss the correctness.

  • 3. (Exercise 3.10.70 of textbook)
    Prove that all the inner rings R(2), ... R(k), where messages are sent by protocol Kelect-Stages, do not have links in common.


 

PART   II       (group)

  • 1. Find and read the assigned paper. Select, find and read another related paper.

  • 2. Write a report describing and explaining the context and the content (i.e., the research area, the problems, the techniques, and the solutions) of the two papers.

  • 3. Prepare a 30 minute lecture on the two papers. Give the lecture in class at the scheduled time (to be announced later).

  • The intended audience of your presentation are your fellow students in COMP 4001; so you must use in both the same terminology and language as used in class and in the textbook. Strive for clarity, simplicity and accuracy; when possible use images. Here you can find some hints on report-writing.

  • The paper assigned to you is Paper j in the list below, where j=[your group number].

  • The answers to Part 1 as well as the Report of Part 2 must be written in Latex (reccomended) or HTML. The class presentation can be prepared in Powerpoint.

  • Your assignment will be marked for clarity, accuracy, and completeness in all aspects.


    •  


    ASSIGNED PAPERS

    • Paper 1:
      H. Abu Amara and J. Lockre, "Election in Asynchronous Complete Networks with Intermittent Link Failures", IEEE Transactions on Computers, Vol. 43, No. 7, pp. 778-788, 1994.

    • Paper 2:
      O. Goldreich and L. Shrira, "Electing a Leader with Link Failure", Acta Informatica, Vol. 24, pp. 79-91, 1987.

    • Paper 3:
      B. Mans and N. Santoro, "Optimal Elections in Faulty Loop Networks and Applications", IEEE Transactions on Computers , Vol. 47 , N. 3, pp. 286 - 297, 1998.

    • Paper 4:
      R. Bar_Yehuda, S. Kutten, Y, Wolfstahl, and Shmuel Zaks, "Optimal Distributed t-Resilient Election in Complete Networks", IEEE Transactions on Software Engineering, Vol. 16, N. 4, pp. 415 - 420 , 1990.

    • Paper 5:
      B. Gfeller, N. Santoro, and P. Widmayer A distributed algorithm for finding all best swap edges of a minimum diameter spanning tree. IEEE Transactions on Dependable and Secure Computing, Vol. 8, N. 1, pp. 1-12, 2011

    • Paper 6:
      Singh, "Efficient leader election using sense of direction", Distributed Computing, Vol. 10, pp. 159--165, 1997.