NDLI: Deterministic Symmetry Breaking in Ring Networks

Content Provider	IEEE Xplore Digital Library
Author	Gasieniec, L. Jurdzinski, T. Martin, R. Stachowicz, G.
Copyright Year	2015
Description	Author affiliation: Dept. of Comput. Sci., Univ. of Liverpool, Liverpool, UK (Gasieniec, L.; Martin, R.) \|\| Inst. of Comput. Sci., Univ. of Wroclaw, Wrocław, Poland (Jurdzinski, T.; Stachowicz, G.)
Abstract	We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronised rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., When an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem.
Starting Page	517
Ending Page	526
File Size	271567
Page Count	10
File Format	PDF
ISBN	9781467372145
ISSN	10636927
DOI	10.1109/ICDCS.2015.59
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-06-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Complexity theory Nominations and elections Trajectory Clocks Robot kinematics Testing bouncing mobile robots location discovery
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Gathering of Mobile Robots Tolerating Multiple Crash Faults

The Power of Lights: Synchronizing Asynchronous Robots Using Visible Bits

Fail-aware failure detectors

Cloud networked robotics

A P2P Sensor Framework for Collaborative Robots Manipulation

ERSP: a software platform and architecture for the service robotics industry

Control of a nonholonomic mobile robot using neural networks

Hierarchical distributed architectures for autonomous mobile robots: A case study

Agents for cooperative heterogeneous mobile robotics: a case study

Deterministic Symmetry Breaking in Ring Networks

Similar Documents

Gathering of Mobile Robots Tolerating Multiple Crash Faults

The Power of Lights: Synchronizing Asynchronous Robots Using Visible Bits

Fail-aware failure detectors

Cloud networked robotics

A P2P Sensor Framework for Collaborative Robots Manipulation

ERSP: a software platform and architecture for the service robotics industry

Control of a nonholonomic mobile robot using neural networks

Hierarchical distributed architectures for autonomous mobile robots: A case study

Agents for cooperative heterogeneous mobile robotics: a case study

Deterministic Symmetry Breaking in Ring Networks