Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

CHALOPIN_2008_HAL-00332759_1

Jérémie Chalopin, Emmanuel Godard, Yves Métivier. Local terminations and distributed computability in anonymous networks. In Distributed computing International symposium on distributed computing (DISC), Lecture notes in computer science, Volume 4218, Pages 47-62, Arcachon France, 2008.

Download

Download paper: Follow the link

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

{W}e investigate the computability of distributed tasks in reliable anonymous networks with arbitrary knowledge. {M}ore precisely, we consider tasks computable with local termination, i.e., a node knows when to stop to participate in a distributed algorithm, even though the algorithm is not necessarily terminated elsewhere. {W}e also study weak local termination, that is when a node knows its final value but continues to execute the distributed algorithm, usually in order to provide information to other nodes. {W}e give the first characterization of distributed tasks that can be computed with weak local termination and we present a new characterization of tasks computed with local termination. {F}or both terminations, we also characterize tasks computable by polynomial algorithms.

Contact

Jérémie Chalopin
Emmanuel Godard
Yves Métivier

BibTex Reference

@InProceedings{CHALOPIN_2008_HAL-00332759_1,
   Author = {Chalopin, Jérémie and Godard, Emmanuel and Métivier, Yves},
   Title = {{L}ocal terminations and distributed computability in anonymous networks},
   BookTitle = {{D}istributed computing {I}nternational symposium on distributed computing ({DISC})},
   Volume = {4218},
   Pages = {47--62},
   Series = {{L}ecture notes in computer science},
   Publisher = {{S}pringer},
   Address = {{A}rcachon {F}rance},
   Year = {2008}
}

EndNote Reference [help]

Get EndNote Reference (.ref)