NDLI: How to meet asynchronously at polynomial cost

Please wait, while we are loading the content...

On deterministic abortable objects

Compact routing schemes with improved stretch

Fast byzantine agreement

How to meet asynchronously at polynomial cost

Brief announcement: self-stabilizing resource discovery algorithm

Stone age distributed computing

Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors

Upper bound on the complexity of solving hard renaming

Fair and resilient incentive tree mechanisms

Early-deciding consensus is expensive

Leaplist: lessons learned in designing tm-supported range queries

Randomized broadcast in radio networks with collision detection

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

Athena lecture: distributed computing theory for wireless networks and mobile systems

Pragmatic primitives for non-blocking data structures

Optimal deterministic routing and sorting on the congested clique

Byzantine vector consensus in complete graphs

On the complexity of universal leader election

Brief announcement: parameterized model checking of fault-tolerant distributed algorithms by abstraction

Feedback from nature: an optimal distributed algorithm for maximal independent set selection

Highly dynamic distributed computing with byzantine failures

Randomized loose renaming in o(log log n) time

What's a little collusion between friends?

On the complexity of asynchronous agreement against powerful adversaries

A programming language perspective on transactional memory consistency

Maximal independent sets in multichannel radio networks

Efficient distributed source detection with limited bandwidth

Programming models for extreme-scale computing

The SkipTrie: low-depth concurrent search without rebalancing

Brief announcement: fair maximal independent sets in trees

Fast byzantine agreement in dynamic networks

Brief announcement: a simple stretch 2 distance oracle

Brief announcement: on minimum interaction time for continuous distributed interactive computing

What can be decided locally without identifiers?

Brief announcement: constructing fault-tolerant overlay networks for topic-based publish/subscribe

Byzantine renaming in synchronous systems with t < N

A distributed algorithm for gathering many fat mobile robots in the plane

Introducing speculation in self-stabilization: an application to mutual exclusion

Brief announcement: an asymmetric flat-combining based queue algorithm

The cost of radio network broadcast for different models of unreliable links

Distributed algorithms for barrier coverage using relocatable sensors

Brief announcement: threshold load balancing in networks

Synchronous byzantine agreement with nearly a cubic number of communication bits: synchronous byzantine agreement with nearly a cubic number of communication bits

Brief announcement: pareto optimal solutions to consensus and set consensus

Brief announcement: deterministic self-stabilizing leader election with O(log log n)-bits

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time

An O(1)-barriers optimal RMRs mutual exclusion algorithm: extended abstract

Stable and scalable universal swarms

Brief announcement: resettable objects and efficient memory reclamation for concurrent algorithms

Connectivity and aggregation in multihop wireless networks

Delegation of computation with verification outsourcing: curious verifiers

Brief announcement: scalable anonymous communication with byzantine adversary

Brief announcement: a shorter and stronger proof of an Ω(d log(n/d)) lower bound for broadcast in radio networks

Brief announcement: brokerage and closure in a strategic model of social capital

Brief announcement: a local approximation algorithm for MDS problem in anonymous planar networks

Brief announcement: techniques for programmatically troubleshooting distributed systems

How to meet asynchronously at polynomial cost

Content Provider	ACM Digital Library
Author	Pelc, Andrzej Villain, Vincent Dieudonné, Yoann
Abstract	Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it, but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: team size, in which every agent has to find the total number of agents, leader election, in which all agents have to output the label of a single agent, perfect renaming in which all agents have to adopt new different labels from the set 1,.,k}, where k is the number of agents, and gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm we solve all these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.
Starting Page	92
Ending Page	99
Page Count	8
File Format	PDF
ISBN	9781450320658
DOI	10.1145/2484239.2484245
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Gossiping Leader election Network Asynchronous mobile agents Deterministic algorithm Rendezvous Renaming
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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