{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T05:24:57Z","timestamp":1733289897007,"version":"3.30.1"},"reference-count":68,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3850,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,1]]},"DOI":"10.1016\/s0304-3975(01)00395-4","type":"journal-article","created":{"date-parts":[[2002,11,5]],"date-time":"2002-11-05T08:14:58Z","timestamp":1036484098000},"page":"29-53","source":"Crossref","is-referenced-by-count":27,"title":["Sense of direction in distributed computing"],"prefix":"10.1016","volume":"291","author":[{"given":"Paola","family":"Flocchini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Mans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00395-4_BIB1","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF01553900","article-title":"Efficient elections in chordal ring networks","volume":"4","author":"Attiya","year":"1989","journal-title":"Algorithmica"},{"issue":"4","key":"10.1016\/S0304-3975(01)00395-4_BIB2","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/48014.48247","article-title":"Computing on an anonymous ring","volume":"35","author":"Attiya","year":"1988","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/S0304-3975(01)00395-4_BIB3","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/77600.77618","article-title":"A trade-off between information and communication in broadcast protocols","volume":"37","author":"Awerbuch","year":"1990","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB4","doi-asserted-by":"crossref","unstructured":"G.v. Bochmann, P. Flocchini, D. Ramazani, Distributed objects with sense of direction, Proc. 1st Workshop on Distributed Data and Structures, Orlando, 1998, pp. 1\u201315.","DOI":"10.1007\/BFb0056468"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB5","unstructured":"P. Boldi, B. Codenotti, P. Gemmell, S. Shammah, J. Simon, S. Vigna, Symmetry breaking in anonymous networks: characterizations, Proc. 4th Israeli Symp. on Theory of Computing and Systems, Jerusalem, 1996, pp. 16\u201326."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB6","unstructured":"P. Boldi, S. Vigna, personal communication."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0020-0190(00)00094-6","article-title":"Coverings that preserve sense of direction","volume":"75","author":"Boldi","year":"2000","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB8","unstructured":"P. Boldi, S. Vigna, On some constructions which preserve sense of direction, Proc. 3rd Internat. Colloq. on Structural Information and Communication Complexity, Siena, 1996, pp. 47\u201357."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB9","doi-asserted-by":"crossref","unstructured":"P. Boldi, S. Vigna, Computing vector functions on anonymous networks, Proc. 4th Internat. Colloq. on Structural Information and Communication Complexity, Ascona, 1997, pp. 201\u2013214.","DOI":"10.1145\/259380.259463"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB10","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0020-0190(97)00187-7","article-title":"Minimal sense of direction and decision problems for Cayley graphs","volume":"64","author":"Boldi","year":"1997","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10.1016\/S0304-3975(01)00395-4_BIB11","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1137\/S0097539796310801","article-title":"On the complexity of deciding sense of direction","volume":"29","author":"Boldi","year":"2000","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB12","unstructured":"A. Bui, A.K. Datta, F. Petit, V. Villain, Snap-stabilizing pif algorithm in the tree networks without sense of direction, Proc. 6th Internat. Colloq. on Structural Information and Communication Complexity, Lacanau, 1999, pp. 32\u201346."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB13","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1109\/TSE.1983.234958","article-title":"Graph traversal techniques and the maximum flow problem in distributed computation","volume":"9","author":"Cheung","year":"1983","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB14","unstructured":"A.K. Datta, S. Gurumurthy, F. Petit, V. Villain, Self-stabilizing network orientation algorithms in arbitrary networks, ICDCS 2000, 20th Internat. Conf. on Distributed Computing Systems, 2000, pp. 576\u2013583."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(98)00055-6","article-title":"Broadcasting in unlabeled hypercubes with linear number of messages","volume":"66","author":"Diks","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB16","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1142\/S0129626498000195","article-title":"Broadcasting in unlabeled tori","volume":"8","author":"Diks","year":"1998","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0166-218X(98)00047-X","article-title":"Perfect broadcasting in unlabeled networks","volume":"87","author":"Diks","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB18","unstructured":"S. Dobrev, Leader election using any sense of direction, Proc. 6th Internat. Colloq. on Structural Information and Communication Complexity, Lacanau, 1999, pp. 93\u2013104."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB19","unstructured":"S. Dobrev, P. Ru\u017ei\u010dka, Linear broadcasting and n log log n election in unoriented hypercubes, Proc. 4th Internat. Colloq. on Structural Information and Communication Complexity, Ascona, 1997, pp. 53\u201368."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB20","doi-asserted-by":"crossref","unstructured":"S. Dobrev, P. Ru\u017ei\u010dka, Broadcasting in anonymous unoriented torus, Proc. 24th Internat. Workshop on Graph-Theoretic Concepts in Computer Science, Smolenice-Castle, 1998, pp. 50\u201362.","DOI":"10.1007\/10692760_5"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB21","doi-asserted-by":"crossref","unstructured":"S. Dobrev, P. Ru\u017ei\u010dka, Yet another modular technique for efficient leader election, Proc. 25th Annu. Conf. on Current Trends in Theory and Practice of Informatics, Slovakia, Springer, Berlin, 1998, pp. 312\u2013321.","DOI":"10.1007\/3-540-49477-4_23"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB22","unstructured":"S. Dobrev, P. Ru\u017ei\u010dka, G. Tel, Time and bit optimal broadcasting in anonymous unoriented hypercubes, Proc. 5th Internat. Colloq. on Structural Information and Communication Complexity, Amalfi, 1998, pp. 173\u2013187."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB23","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0020-0190(97)00031-8","article-title":"Minimal sense of direction in regular networks","volume":"61","author":"Flocchini","year":"1997","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB24","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1006\/jpdc.1996.0026","article-title":"Optimal election in labeled hypercubes","volume":"33","author":"Flocchini","year":"1996","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB25","unstructured":"P. Flocchini, B. Mans, N. Santoro, Distributed traversal and broadcasting in arbitrary network with distance sense of direction, Proc. 9th Internat. Symp. on Computer and Information Sciences, Antalya, 1994, pp. 196\u2013203."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB26","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0020-0190(97)00091-4","article-title":"On the impact of sense of direction on message complexity","volume":"63","author":"Flocchini","year":"1997","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10.1016\/S0304-3975(01)00395-4_BIB27","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<165::AID-NET1>3.0.CO;2-I","article-title":"Sense of direction","volume":"32","author":"Flocchini","year":"1998","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB28","doi-asserted-by":"crossref","unstructured":"P. Flocchini, A. Roncato, N. Santoro, Computing on anonymous networks with sense of direction, Theoret. Comput. Sci., in preparation.","DOI":"10.1016\/S0304-3975(02)00592-3"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0166-218X(98)00051-1","article-title":"Symmetries and sense of direction in labeled graphs","volume":"87","author":"Flocchini","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB30","doi-asserted-by":"crossref","unstructured":"P. Flocchini, A. Roncato, N. Santoro, Backward consistency and sense of direction in advanced distributed systems, Proc. 18th ACM Symp. on Principles of Distributed Computing, Atlanta, 1999, pp. 189\u2013198.","DOI":"10.1145\/301308.301357"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB31","unstructured":"P. Flocchini, N. Santoro, Topological constraints for sense of direction, Proc. 2nd Internat. Colloq. on Structural Information and Communication Complexity, Olympia, 1995, pp. 27\u201338."},{"issue":"2","key":"10.1016\/S0304-3975(01)00395-4_BIB32","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1142\/S0129054198000131","article-title":"Topological constraints for sense of direction","volume":"9","author":"Flocchini","year":"1998","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB33","unstructured":"S. Foldes, J. Urrutia, Sense of direction, semigroups, and cayley graphs, Manuscript, 1998."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB34","unstructured":"J.-L. Fouquet, G. Hahn, Cycle regular graphs need not be transitive, in preparation."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB35","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","article-title":"A distributed algorithm for minimum spanning tree","volume":"5","author":"Gallager","year":"1983","journal-title":"ACM Trans. Programming Languages Systems"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB36","unstructured":"International Standard Organization, ISO\/IEC JTC1, information technology\u2014open distributed processing\u2014naming framework, ISO\/IEC DIS147771, July 1997."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB37","first-page":"317","article-title":"Time-message trade-offs for the weak unison problem","volume":"4","author":"Israeli","year":"1997","journal-title":"Nordic J. Comput."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB38","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1109\/32.54293","article-title":"Optimal distributed t-resilient election in complete networks","volume":"16","author":"Itai","year":"1990","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB39","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0020-0190(91)90069-T","article-title":"Towards optimal distributed election on chordal rings","volume":"38","author":"Kalamboukis","year":"1991","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB40","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1145\/77606.77610","article-title":"A modular technique for the design of efficient distributed leader finding algorithms","volume":"12","author":"Korach","year":"1990","journal-title":"ACM Trans. Programming Languages Systems"},{"issue":"2","key":"10.1016\/S0304-3975(01)00395-4_BIB41","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/0216019","article-title":"Optimality of distributed constructions of minimum weight and degree restricted spanning trees in a complete network of processors","volume":"16","author":"Korach","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB42","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1006\/jagm.1996.0817","article-title":"Distributed computing on anonymous hypercubes","volume":"23","author":"Kranakis","year":"1997","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB43","doi-asserted-by":"crossref","unstructured":"E. Kranakis, N. Santoro, Distributed computing on anonymous hypercubes with faulty components, Proc. 6th Internat. Workshop on Distributed Algorithms, Haifa, 1992, pp. 253\u2013263.","DOI":"10.1007\/3-540-56188-9_17"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB44","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(86)90043-8","article-title":"A fully distributed (minimal) spanning tree algorithm","volume":"23","author":"Lavall\u00e9e","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB45","doi-asserted-by":"crossref","unstructured":"M.C. Loui, T.A. Matsushita, D.B. West, Election in complete networks with a sense of direction, Inform. Process. Lett. 22 (1986) 185\u2013187 (see also Inform. Process. Lett. 28 (1988) 327).","DOI":"10.1016\/0020-0190(88)90181-0"},{"year":"1995","series-title":"Distributed Algorithms","author":"Lynch","key":"10.1016\/S0304-3975(01)00395-4_BIB46"},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB47","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jpdc.1997.1389","article-title":"Optimal distributed algorithms in unlabeled tori and chordal rings","volume":"46","author":"Mans","year":"1997","journal-title":"J. Parallel Distributed Comput."},{"issue":"3","key":"10.1016\/S0304-3975(01)00395-4_BIB48","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/12.660164","article-title":"Optimal elections in faulty loop networks and applications","volume":"4","author":"Mans","year":"1998","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB49","doi-asserted-by":"crossref","unstructured":"G.H. Masapati, H. Ural, Effect of preprocessing on election in a complete network with a sense of direction, Proc. IEEE Internat. Conf. on Systems, Man and Cybernetics, Vol. 3, 1991, pp. 1627\u20131632.","DOI":"10.1109\/ICSMC.1991.169925"},{"issue":"12","key":"10.1016\/S0304-3975(01)00395-4_BIB50","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/scj.4690221202","article-title":"A fault-tolerant algorithm for election in complete networks with a sense of direction","volume":"22","author":"Masuzawa","year":"1991","journal-title":"Systems Comput. Japan"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB51","unstructured":"Y. Metivier, A. Muscholl, P.A. Wacrenier, About the local detection of termination of local computations in graphs, Proc. 4th Internat. Colloq. on Structural Information and Communication Complexity, Ascona, 1997, pp. 188\u2013200."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB52","first-page":"12","article-title":"Fault-tolerant distributed algorithm in complete networks with link and processor failures","volume":"J74D-I","author":"Nishikawa","year":"1991","journal-title":"IEICE Trans. Inform. Systems"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB53","unstructured":"Object Management Group, Naming service specification clause 3, CORBA services, March 1995."},{"issue":"1\u20132","key":"10.1016\/S0304-3975(01)00395-4_BIB54","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0255(94)90071-X","article-title":"A near-optimal multi-stage distributed algorithm for finding leaders in clustered chordal rings","volume":"76","author":"Pan","year":"1994","journal-title":"Inform. Sci."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB55","unstructured":"G.L. Peterson, Efficient algorithms for elections in meshes and complete networks, Technical Report TR-140, Department of Computer Science, University of Rochester, Rochester, NY, 1985."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB56","unstructured":"D. Ramazani, G.v. Bochmann, P. Flocchini, Object naming and object composition, Technical Report 1135, Universit\u00e9 de Montr\u00e9al, 1998."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB57","doi-asserted-by":"crossref","unstructured":"S. Robbins, K.A. Robbins, Choosing a leader on a hypercube, Proc. Internat. Conf. on Databases, Parallel Architectures and their Applications, Miami Beach, 1990, pp. 469\u2013471.","DOI":"10.1109\/PARBSE.1990.77181"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB58","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF00979869","article-title":"On the message complexity of distributed problems","volume":"13","author":"Santoro","year":"1984","journal-title":"J. Comput. Inform. Sci."},{"issue":"16","key":"10.1016\/S0304-3975(01)00395-4_BIB59","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/1008959.1008961","article-title":"Sense of direction, topological awareness and communication complexity","volume":"2","author":"Santoro","year":"1984","journal-title":"SIGACT NEWS"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB60","doi-asserted-by":"crossref","unstructured":"M.B. Sharma, S.S. Iyengar, N.K. Mandyam, An efficient distributed depth-first-search algorithm, Inform. Process. Lett. 32 (1989) 183\u2013186 (see also Inform. Process. Lett. 35 (1990) 55).","DOI":"10.1016\/0020-0190(89)90041-0"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB61","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/71.491576","article-title":"Leader election in the presence of link failures","volume":"7","author":"Singh","year":"1996","journal-title":"IEEE Trans. Parallel Distributed Systems"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB62","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s004460050033","article-title":"Efficient leader election using sense of direction","volume":"10","author":"Singh","year":"1997","journal-title":"Distributed Comput."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB63","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0129054194000037","article-title":"Network orientation","volume":"5","author":"Tel","year":"1994","journal-title":"Internat. J. Foundations Comput. Sci."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB64","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0129626495000333","article-title":"Linear election in hypercubes","volume":"5","author":"Tel","year":"1995","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB65","first-page":"50","article-title":"Sense of direction in processor networks","volume":"Vol. 1012","author":"Tel","year":"1995"},{"key":"10.1016\/S0304-3975(01)00395-4_BIB66","unstructured":"A.M. Verweij, Linear-message election in hypercubes, manuscript."},{"key":"10.1016\/S0304-3975(01)00395-4_BIB67","unstructured":"R. Wieringa, W. de Jonge, Object identifiers, keys, and surrogates\u2014objects identifiers revisited, Theory Practice of Object Systems, in preparation."},{"issue":"1","key":"10.1016\/S0304-3975(01)00395-4_BIB68","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/71.481599","article-title":"Computing on anonymous networks, part I","volume":"7","author":"Yamashita","year":"1996","journal-title":"IEEE Trans. Parallel Distributed Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003954?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003954?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T21:10:13Z","timestamp":1578431413000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":68,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["S0304397501003954"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00395-4","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}