More Web Proxy on the site http://driver.im/

research-article

Best-effort group service in dynamic networks

Authors:

Bertrand Ducourthial,

Sofiane Khalfallah,

Franck PetitAuthors Info & Claims

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

Pages 233 - 242

https://doi.org/10.1145/1810479.1810525

Published: 13 June 2010 Publication History

Abstract

We propose a group membership service for dynamic ad hoc networks. It maintains as long as possible the existing groups and ensures that each group diameter is always smaller than a constant, fixed according to the application using the groups. The proposed protocol is self-stabilizing and works in dynamic distributed systems. Moreover, it ensures a kind of continuity in the service offer to the application while the system is converging, except if too strong topology changes happen. Such a best effort behavior allows applications to rely on the groups while the stabilization has not been reached, which is very useful in dynamic ad hoc networks.

References

[1]

A.D. Amis, R. Prakash, and D.H.T. Vuaong. Max-min d-cluster formation in wireless ad hoc networks. In IEEE INFOCOM, pages 32--41, 2000.

[2]

Kenneth P. Birman. The process group approach to reliable distributed computing. Commun. ACM, 36(12):3753, 1993.

Digital Library

[3]

J. Blum, A. Eskandarian, and L. Hoffman. Challenges of intervehicle ad hoc networks. IEEE Transaction on Intelligent Transportation Systems, 5:347351, 2004.

Digital Library

[4]

O. Brukman, S. Dolev, Y. Haviv, and R. Yagel. Self-stabilization as a foundation for autonomic computing. In The Second International Conference on Availability, Reliability and Security (ARES), pages 991--998, Vienna, April 2007.

Digital Library

[5]

G.V. Chockler, I. Keidar, and R. Vitenberg. Group communication specifications: a comprehensive study. ACM Computing Surveys, 4(33):143, 2001.

Digital Library

[6]

A. K. Datta, L. L. Larmore, and P. Vemula. A self-stabilizing O(k)-time k-clustering algorithm. Computer Journal, 2009.

Digital Library

[7]

S. Delaët, B. Ducourthial, and S. Tixeuil. Self-stabilization with r-operators revisited. In Journal of Aerospace Computing, Information, and Communication, 2006.

[8]

Murat Demirbas, Anish Arora, Vineet Mittal, and Vinodkrishnan Kulathumani. A fault-local self-stabilizing clustering service for wireless ad hoc networks. IEEE Trans. Parallel Distrib. Syst., 17(9):912--922, 2006.

Digital Library

[9]

S. Dolev. Self-Stabilization. The MIT Press, 2000.

Digital Library

[10]

S. Dolev and T. Herman. Superstabilizing protocols for dynamic distributed systems. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (PODC), page 255, New York, NY, USA, 1995. ACM.

Digital Library

[11]

S. Dolev, E. Schiller, and J.L. Welch. Random walk for self-stabilizing group communication in ad hoc networks. IEEE Transactions on Mobile Computing, 5(7):893--905, 2006.

Digital Library

[12]

B. Ducourthial. r-semi-groups: A generic approach for designing stabilizing silent tasks. In 9th Stabilization, Safety, and Security of Distributed Systems (SSS'2007), pages 281--295, Paris, novembre 2007.

Digital Library

[13]

B. Ducourthial and S. Tixeuil. Self-stabilization with path algebra. Theor. Comput. Sci., 293(1):219--236, 2003.

Digital Library

[14]

R. Guerraoui and A. Schiper. Software-based replication for fault-tolerance. IEEE Transaction on Computers, 30(4):68--74, 1997.

Digital Library

[15]

Arshad Jhumka and Sandeep S. Kulkarni. On the design of mobility-tolerant TDMA-based media access control (MAC) protocol for mobile sensor networks. In Tomasz Janowski and Hrushikesha Mohanty, editors, ICDCIT, volume 4882 of Lecture Notes in Computer Science, pages 42--53. Springer, 2007.

Digital Library

[16]

Colette Johnen and Le Huy Nguyen. Robust self-stabilizing weight-based clustering algorithm. Theor. Comput. Sci., 410(6-7):581--594, 2009.

Digital Library

[17]

Hirotsugu Kakugawa and Toshimitsu Masuzawa. A self-stabilizing minimal dominating set algorithm with safe convergence. In 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006.

Digital Library

[18]

S. Kutten and D. Peleg. Fast distributed construction of small-dominating sets and applications. Journal of Algorithms, 28(1):40--66, 1998.

Digital Library

[19]

L. Lamport. Time, clocks and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978.

Digital Library

[20]

L. D. Penso and V. C Barbosa. A distributed algorithm to find k -dominating sets. Discrete Applied Mathematics, 141(1-3):243--253, 2004.

Digital Library

[21]

F.B. Schneider. Impliementing fault tolerant services using the state machine approach: a tutorial. Computing Surveys, 22(4):299--319, 2990.

Digital Library

[22]

I. Stojmenovic. Handbook of Wireless Networks and Mobile Computings. John Wiley & Sons, 2002.

Cited By

de Moraes Júnior HDucourthial BHaddad HWainwright RChbeir R(2018)Cooperative neighborhood map in VANETsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167359(2109-2116)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167359
Datta ALarmore LMasuzawa TSudo Y(2017)A Self-Stabilizing Minimal k-Grouping AlgorithmProceedings of the 18th International Conference on Distributed Computing and Networking10.1145/3007748.3007772(1-10)Online publication date: 5-Jan-2017
https://dl.acm.org/doi/10.1145/3007748.3007772
Morales-Ponce OSchiller EFalcone P(2014)Cooperation with disagreement correction in the presence of communication failures17th International IEEE Conference on Intelligent Transportation Systems (ITSC)10.1109/ITSC.2014.6957835(1105-1110)Online publication date: Oct-2014
https://doi.org/10.1109/ITSC.2014.6957835
Show More Cited By

Index Terms

Best-effort group service in dynamic networks

Recommendations

An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing

Vehicular ad hoc networks (VANETs) using WLAN tech-nology have recently received considerable attention. The evaluation of VANET routing protocols often involves simulators since management and operation of a large number of real vehicular nodes is ...
An Efficient Algorithm for Maintaining Consistent Group Membership in Ad Hoc Networks
ICDCSW '03: Proceedings of the 23rd International Conference on Distributed Computing Systems

Designing a reliable group membership algorithm for mobile ad hoc networks is a non-trivial task since we must deal with limited device power, possibilities of frequent disconnections and network partitions. The function of the group membership service ...
Trajectory-Based Statistical Forwarding for Multihop Infrastructure-to-Vehicle Data Delivery

This paper proposes Trajectory-based Statistical Forwarding (TSF) scheme, tailored for the multihop data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles in vehicular ad hoc networks. To our knowledge, this paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

June 2010

378 pages

ISBN:9781450300797

DOI:10.1145/1810479

General Chairs:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Cynthia Phillips
Sandia National Laboratories, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA 10

Sponsor:

SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2010

Santorini, Thira, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
174
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

de Moraes Júnior HDucourthial BHaddad HWainwright RChbeir R(2018)Cooperative neighborhood map in VANETsProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167359(2109-2116)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167359
Datta ALarmore LMasuzawa TSudo Y(2017)A Self-Stabilizing Minimal k-Grouping AlgorithmProceedings of the 18th International Conference on Distributed Computing and Networking10.1145/3007748.3007772(1-10)Online publication date: 5-Jan-2017
https://dl.acm.org/doi/10.1145/3007748.3007772
Morales-Ponce OSchiller EFalcone P(2014)Cooperation with disagreement correction in the presence of communication failures17th International IEEE Conference on Intelligent Transportation Systems (ITSC)10.1109/ITSC.2014.6957835(1105-1110)Online publication date: Oct-2014
https://doi.org/10.1109/ITSC.2014.6957835
Johnen CMekhaldi F(2014)Self-stabilizing with service guarantee construction of 1-hop weight-based bounded size clustersJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.09.00474:1(1900-1913)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2013.09.004
Bui AClavière SSohier D(2013)Nested clusters with intercluster routingThe Journal of Supercomputing10.1007/s11227-013-0886-y65:3(1353-1382)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1007/s11227-013-0886-y
Dieudonne YDucourthial BSenouci S(2012)COL: A data collection protocol for VANET2012 IEEE Intelligent Vehicles Symposium10.1109/IVS.2012.6232266(711-716)Online publication date: Jun-2012
https://doi.org/10.1109/IVS.2012.6232266
Bui AClavière SSohier D(2011)Distributed Construction of Nested Clusters with Inter-cluster RoutingProceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPS.2011.195(673-680)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.1109/IPDPS.2011.195

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents