2013-03-01, English, Article, Report edition: Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots.(Report) Flocchini, Paola; Ilcinkas, David; Pelc, Andrzej; ...

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/193246831
Physical Description
  • Report
  • Magazine/​Journal article
Published
  • Springer, 2013 March
Language
  • English

Edition details

Title
  • Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots.(Report)
Also Titled
  • Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots.
Appears In
  • Algorithmica, v.65, no.3, 2013 March, p.562(22) (ISSN: 0178-4617)
Author
  • Flocchini, Paola
  • Ilcinkas, David
  • Pelc, Andrzej
  • Santoro, Nicola
Published
  • Springer, 2013 March
Physical Description
  • Report
  • Magazine/​Journal article
Subjects
Target Audience
  • Academic
Summary
  • Byline: Paola Flocchini (1), David Ilcinkas (2), Andrzej Pelc (3), Nicola Santoro (4) Keywords: Mobile robots; Asynchronous; Oblivious; Exploration; Ring Abstract: We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for kaY=​17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number [rho](n) of robots that can explore a ring of size n. As a consequence of our positive result we show that [rho](n) is O(logn). We additionally prove that [OMEGA](logn) robots are necessary for infinitely many n. Author Affiliation: (1) School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Ontario, K1N 6N5, Canada (2) LaBRI, CNRS &​ Universite de Bordeaux, 351 cours de la Liberation, 33405, Talence cedex, France (3) Departement d'informatique, Universite du Quebec en Outaouais, Gatineau, Quebec, J8X 3X7, Canada (4) School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada Article History: Registration Date: 29/​12/​2011 Received Date: 10/​10/​2008 Accepted Date: 29/​12/​2011 Online Date: 07/​01/​2012 Article note: A preliminary version of this paper appeared in [27].
Terms of Use
  • COPYRIGHT 2013 Springer
Language
  • English
Database
  • Gale Academic OneFile
Identifier
  • 321493801

Get this edition

Via a library membership

Library View online via
Australian Bureau of Statistics. Castles Library.
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University. Document Supply Service.
Australian Institute of Professional Education.
Australian Lutheran College. Lohe Memorial Library.
Australian School of Management. Perth Campus Library.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
University of Adelaide. Barr Smith Library.
Blue Mountains International Hotel Management School.
Bond University. John and Alison Kearney Library .
Campion College Australia.
Charles Darwin University. Casuarina Campus Library.
Cengage Education.
Christian Heritage College. Christian Heritage College Library.
Deakin University. Deakin University Library.
Edith Cowan University. Edith Cowan University Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
University of Notre Dame Australia. Galvin Medical Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Moore Theological College. Moore Theological College Library.
SA Mental Health Services.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
South Western Sydney Institute of TAFE.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Tabor Adelaide. Tabor College Library.
The Southport School. Senior Library.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Canberra. University of Canberra Library.
University of Wollongong. University of Wollongong Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Australian Bureau of Statistics. Castles Library.
University of Canberra. University of Canberra Library.
Show 0 more libraries...
Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University. Document Supply Service.
Australian Institute of Professional Education.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
Blue Mountains International Hotel Management School.
Campion College Australia.
Cengage Education.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Moore Theological College. Moore Theological College Library.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Western Sydney Institute of TAFE.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Wollongong. University of Wollongong Library.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Charles Darwin University. Casuarina Campus Library.
Show 0 more libraries...
Library View online via
Bond University. John and Alison Kearney Library .
Christian Heritage College. Christian Heritage College Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
The Southport School. Senior Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Show 0 more libraries...
Library View online via
Australian Lutheran College. Lohe Memorial Library.
University of Adelaide. Barr Smith Library.
SA Mental Health Services.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
Tabor Adelaide. Tabor College Library.
Show 0 more libraries...
Library View online via
Deakin University. Deakin University Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Show 0 more libraries...

Published in

Some editions of the publication "Algorithmica" are available from these libraries. The edition containing this article ( v.65, no.3, 2013 March, p.562(22) ) may not be available:

None of your libraries hold this item.

These 9 locations in All:

Library Access Call number(s) Formats held Language
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001505716; Full Text Available; Springer Standard Collection - Available from 1997 Periodical; Journal, magazine, other English
Defence Science and Technology Group. DST Group Research Information Services - Melbourne. Not open to the public Serials; Vol.17 (1997)- v.22 (1998) Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
The University of Melbourne. The University Library. Open to the public MS P ALGO; Vol. 7, no. 1-Vol. 25, no. 4; 1992-1999 Periodical; Journal, magazine, other English
The University of Sydney. University of Sydney Library. Open to the public Periodical; Journal, magazine, other English
University of Newcastle. University of Newcastle Library. Open to the public S005.105/4; Vol. 17-v. 37, no. 4; 1997-Dec. 2003 Periodical; Journal, magazine, other English
University of New England. Dixson Library. Open to the public 8549-43260; P005.1/A396 <8549-43260>; Vol. 15, no. 1(Jan. 1996)- Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public .b1190298x; psep QA75.5 .A53 : 1(1986)-37(2003); Online access via SpringerLink journal archives : (1986-1996). Available for document delivery - restrictions apply; Online access via SpringerLink : (1997)-. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
University of Western Australia. University of Western Australia Library. Open to the public 9990221802101; HELD; V. 6-37 ; 1991-2003 Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

These 5 locations in New South Wales:

Library Access Call number(s) Formats held Language
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001505716; Full Text Available; Springer Standard Collection - Available from 1997 Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
The University of Sydney. University of Sydney Library. Open to the public Periodical; Journal, magazine, other English
University of Newcastle. University of Newcastle Library. Open to the public S005.105/4; Vol. 17-v. 37, no. 4; 1997-Dec. 2003 Periodical; Journal, magazine, other English
University of New England. Dixson Library. Open to the public 8549-43260; P005.1/A396 <8549-43260>; Vol. 15, no. 1(Jan. 1996)- Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

This single location in Queensland:

Library Access Call number(s) Formats held Language
University of Queensland. University of Queensland Library. Open to the public .b1190298x; psep QA75.5 .A53 : 1(1986)-37(2003); Online access via SpringerLink journal archives : (1986-1996). Available for document delivery - restrictions apply; Online access via SpringerLink : (1997)-. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.

These 2 locations in Victoria:

Library Access Call number(s) Formats held Language
Defence Science and Technology Group. DST Group Research Information Services - Melbourne. Not open to the public Serials; Vol.17 (1997)- v.22 (1998) Periodical; Journal, magazine, other English
The University of Melbourne. The University Library. Open to the public MS P ALGO; Vol. 7, no. 1-Vol. 25, no. 4; 1992-1999 Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment