کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431495 688560 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Self-stabilizing with service guarantee construction of 1-hop weight-based bounded size clusters
ترجمه فارسی عنوان
تثبیت کننده خود با تضمین خدمات ساخت یک کمپوست اندازه گیری محدود بر پایه یک وزن کم؟
کلمات کلیدی
خود تثبیت، تضمین خدمات، ایمنی، سرویس حداقل خوشه بندی خوشه های محدود
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We propose an extension of self-stabilization providing a service guarantee.
• We present a self-stabilization with service guarantee protocol (SG-BSC).
• SG-BSC protocol builds 1-hop, bounded size and weight based clusters.
• We prove the SG-BSC protocol properties: convergence, safety and service guarantee, and its time complexity.
• The interest of self-stabilization with service guarantee is established by simulations.

This paper makes contributions in two areas. First, we introduce an extended approach of self-stabilization, called self-stabilization with service guarantee. A self-stabilizing system tolerates transient faults: it automatically recovers to a correct behavior after a stabilization period. However, during stabilization periods, no property on the system behavior is guaranteed. A self-stabilizing protocol with service guarantee quickly provides a useful minimal service, and it maintains the minimal service during stabilization despite the occurrence of some disruptions. To illustrate our approach, we propose a clustering protocol (called SG-BSC), that builds 1-hop, bounded size and weight based clusters. SG-BSC protocol is self-stabilizing with service guarantee: it quickly reaches, in 4 rounds, a safe configuration from any arbitrary one. In a safe configuration, the following useful minimal service is provided: “each node belongs to a cluster, and each cluster has a leader and at most SizeBoundSizeBound ordinary nodes that are at most at distance 1 from their cluster-head”. The convergence to a legitimate configuration (optimum service) is done in at most 7∗N2+4 rounds, where NN is the number of nodes. We prove that any self-stabilizing protocol building weight-based clusters requires O(N)O(N) rounds to stabilize. Once the optimum service is reached, any cluster-head has the highest weight in its cluster, and the number of clusters is locally optimal. During the stabilization period, the minimal service is preserved; so, the hierarchical organization stays available throughout the entire network. Simulation results show the interest of self-stabilization with service guarantee compared to self-stabilization.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 74, Issue 1, January 2014, Pages 1900–1913
نویسندگان
, ,