5.CONCLUSIONS [8]R.G.Gallager,P.A.Humblet,and P.M.Spira.A We have described an asynchronous distributed algorithm distributed algorithm for minimum-weight spanning for quickly converting the nodes in a weakly-connected pointer trees.ACM Trans.Program.Lang.Syst.,5(1):66-77 graph into the leaves of a Patricia tree with depth bounded 1983. by the length of node identifiers.Applications of this pro- [9]M.T.Goodrich and S.R.Kosaraju.Sorting on a tocol include solving resource discovery or leader election parallel pointer machine with applications to set subject to contention,message-size,or memory constraints expression evaluation.J.ACM.43(2):331-361.1996. that limit how many identifiers can be transmitted in a sin- 10 M.Harchol-Balter,T.Leighton,and D.Lewin gle message or stored in a single node;and the construction Resource discovery in distributed networks.In of sorted lists as a foundation for more sophisticated peer-to- Proceedings of the eighteenth annual ACM symposium peer data structures.The application to peer-to-peer data on Principles of distributed computing,pages 229-237. structures is of interest not only for building such structures ACM Press,1999. quickly ab initio,but also as a repair mechanism for dam- [11]A.Israeli and A.Itai.A fast and simple randomized aged structures;our protocol is fast enough that it is would parallel algorithm for maximal matching.Information not be unreasonable to use it to repair damaged structures Processing Letters,22(2):77-80,1986. by periodically rebuilding them from scratch. [12]T.Johnson and P.Krishna.Lazy updates for Our analysis assumes that no failures occur during its ex- distributed search structure.In P.Buneman and ecution,an assumption unlikely to hold in practice despite S.Jajodia,editors,Proceedings of the 1993 ACM the speed of the algorithm.Handling failures is an interest- SIGMOD International Conference on Management of ing avenue for future work. Data,Washington,D.C.,May 26-28,1993,pages Finally,the optimal running time of self-sorting starting 337-346.ACM Press,1993. from a weakly-connected knowledge graph remains open. [13]S.Kutten and D.Peleg.Asynchronous resource Our upper bound of O((d+W)logn)for the synchronous discovery in peer to peer networks.In 21st IEEE model is tantalizingly close to our lower bound of (d+ Sumposium on Reliable Distributed Systems logn),and it would not be surprising if the extra near- (SRDS'02),pages224-231,October13-16,2002 logarithmic factor of W could be eliminated by pipelining [14]S.Kutten,D.Peleg,and U.Vishkin.Deterministic the effectively sequential phases of the pairing algorithm. resource discovery in distributed networks.In The key difficulty is that until a merge reaches them,it is Proceedings of the thirteenth annual ACM symposium difficult for the nodes deep in a newly-combined component on Parallel algorithms and architectures,pages 77-83. to distinguish between external edges and edges that are now ACM Press.2001. internal to the component.Such an improvement would re- quire either a mechanism for discarding internal edges from [15]R.E.Ladner and M.J.Fischer.Parallel prefix each component quickly,or for choosing candidate external computation.J.ACM,27(4):831-838,1980. edges in a way that produced good pairings with high prob- [16 C.Law and K.-Y.Siu.An O(log n)randomized ability.We plan to pursue such possibilities in future work. resource discovery algorithm.In Brief Announcements of the 14th International Symposium on Distributed Computing,Technical University of Madrid,Technical 6.REFERENCES Report FIM/110.1/DLSIIS/2000,pages 5-8,Oct. 2000. [1]K.Aberer.P-Grid:A self-organizing access structure [17]D.R.Morrison.Patricia-practical algorithm to for P2P information systems.Lecture Notes in retrieve information coded in alphanumeric.J.ACM. Computer Science,2172:179-194.2001. 15(4):514-534,1968. [2]I.Abraham and D.Dolev.Asynchronous resource [18]C.Okasaki and A.Gill.Fast mergeable integer maps. discovery.In Proceedings of the twenty-second annual In Workshop on ML,pages 77-86,1998. symposium on Principles of distributed computing, [19]I.Stoica,R.Morris,D.Liben-Nowell,D.R.Karger, pages 143-150.ACM Press,2003. M.F.Kaashoek,F.Dabek.and H.Balakrishnan. [3]J.Aspnes and G.Shah.Skip Graphs.In Proceedings Chord:A Scalable Peer-to-peer Lookup Service for of the Fourteenth Annual ACM-SIAM Symposium on Internet Applications.IEEE/ACM Transactions on Discrete Algorithms (SODA),pages 384-393, Networking,11(1):17-32,Feb.2003. Baltimore,MD,USA,Jan.2003.Submitted to a 20R.Uehara and Z.-Z.Chen.Parallel approximation special issue of Journal of Algorithms dedicated to algorithms for maximum weighted matching in general select papers of SODA 2003. graphs.In Proceedings of IFIP TCS 2000,pages [4]I.Cidon,I.Gopal,and S.Kutten.New models and 84-98.Springer-Verlag,LNCS 1872,2000. algorithms for future networks.IEEE Transactions on 21 H.Yokota,Y.Kanemasa,and J.Miyazaki.Fat-btree: Information Theory,41(3):769-780,May 1995. An update-conscious parallel directory structure.In [5]R.de la Briandais.File searching using variable length Proceedings of the 15th International Conference on keys.In Proceedings of the Western Joint Computer Data Engineering,23-26 March 1999,Sydney, Conference,volume 15,pages 295-298,Montvale,NJ. Austrialia,pages 448-457.IEEE Computer Society, USA.1959 1999. [6]E.Fredkin.Trie Memory.Communications of the ACM,3(9):490-499,Sept.1960. [7]M.J.Freedman and R.Vingralek.Efficient peer-to-peer lookup based on a distributed trie.In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02),Cambridge,MA March 2002.5. CONCLUSIONS We have described an asynchronous distributed algorithm for quickly converting the nodes in a weakly-connected pointer graph into the leaves of a Patricia tree with depth bounded by the length of node identifiers. Applications of this pro￾tocol include solving resource discovery or leader election subject to contention, message-size, or memory constraints that limit how many identifiers can be transmitted in a sin￾gle message or stored in a single node; and the construction of sorted lists as a foundation for more sophisticated peer-to￾peer data structures. The application to peer-to-peer data structures is of interest not only for building such structures quickly ab initio, but also as a repair mechanism for dam￾aged structures; our protocol is fast enough that it is would not be unreasonable to use it to repair damaged structures by periodically rebuilding them from scratch. Our analysis assumes that no failures occur during its ex￾ecution, an assumption unlikely to hold in practice despite the speed of the algorithm. Handling failures is an interest￾ing avenue for future work. Finally, the optimal running time of self-sorting starting from a weakly-connected knowledge graph remains open. Our upper bound of O((d + W) log n) for the synchronous model is tantalizingly close to our lower bound of Ω(d + log n), and it would not be surprising if the extra near￾logarithmic factor of W could be eliminated by pipelining the effectively sequential phases of the pairing algorithm. The key difficulty is that until a merge reaches them, it is difficult for the nodes deep in a newly-combined component to distinguish between external edges and edges that are now internal to the component. Such an improvement would re￾quire either a mechanism for discarding internal edges from each component quickly, or for choosing candidate external edges in a way that produced good pairings with high prob￾ability. We plan to pursue such possibilities in future work. 6. REFERENCES [1] K. Aberer. P-Grid: A self-organizing access structure for P2P information systems. Lecture Notes in Computer Science, 2172:179–194, 2001. [2] I. Abraham and D. Dolev. Asynchronous resource discovery. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 143–150. ACM Press, 2003. [3] J. Aspnes and G. Shah. Skip Graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 384–393, Baltimore, MD, USA, Jan. 2003. Submitted to a special issue of Journal of Algorithms dedicated to select papers of SODA 2003. [4] I. Cidon, I. Gopal, and S. Kutten. New models and algorithms for future networks. IEEE Transactions on Information Theory, 41(3):769–780, May 1995. [5] R. de la Briandais. File searching using variable length keys. In Proceedings of the Western Joint Computer Conference, volume 15, pages 295–298, Montvale, NJ, USA, 1959. [6] E. Fredkin. Trie Memory. Communications of the ACM, 3(9):490–499, Sept. 1960. [7] M. J. Freedman and R. Vingralek. Efficient peer-to-peer lookup based on a distributed trie. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02), Cambridge, MA, March 2002. [8] R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(1):66–77, 1983. [9] M. T. Goodrich and S. R. Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. J. ACM, 43(2):331–361, 1996. [10] M. Harchol-Balter, T. Leighton, and D. Lewin. Resource discovery in distributed networks. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, pages 229–237. ACM Press, 1999. [11] A. Israeli and A. Itai. A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters, 22(2):77–80, 1986. [12] T. Johnson and P. Krishna. Lazy updates for distributed search structure. In P. Buneman and S. Jajodia, editors, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993, pages 337–346. ACM Press, 1993. [13] S. Kutten and D. Peleg. Asynchronous resource discovery in peer to peer networks. In 21st IEEE Symposium on Reliable Distributed Systems (SRDS’02), pages 224–231, October 13–16, 2002. [14] S. Kutten, D. Peleg, and U. Vishkin. Deterministic resource discovery in distributed networks. In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 77–83. ACM Press, 2001. [15] R. E. Ladner and M. J. Fischer. Parallel prefix computation. J. ACM, 27(4):831–838, 1980. [16] C. Law and K.-Y. Siu. An O(log n) randomized resource discovery algorithm. In Brief Announcements of the 14th International Symposium on Distributed Computing, Technical University of Madrid, Technical Report FIM/110.1/DLSIIS/2000, pages 5–8, Oct. 2000. [17] D. R. Morrison. Patricia—practical algorithm to retrieve information coded in alphanumeric. J. ACM, 15(4):514–534, 1968. [18] C. Okasaki and A. Gill. Fast mergeable integer maps. In Workshop on ML, pages 77–86, 1998. [19] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. IEEE/ACM Transactions on Networking, 11(1):17–32, Feb. 2003. [20] R. Uehara and Z.-Z. Chen. Parallel approximation algorithms for maximum weighted matching in general graphs. In Proceedings of IFIP TCS 2000, pages 84–98. Springer-Verlag, LNCS 1872, 2000. [21] H. Yokota, Y. Kanemasa, and J. Miyazaki. Fat-btree: An update-conscious parallel directory structure. In Proceedings of the 15th International Conference on Data Engineering, 23-26 March 1999, Sydney, Austrialia, pages 448–457. IEEE Computer Society, 1999