Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
127
result(s) for
"Ghosh, Sukumar"
Sort by:
Fault-containing self-stabilizing distributed protocols
Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment. [PUBLICATION ABSTRACT]
Journal Article
Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
Locating a center or a median in a graph is a fundamental graph-theoretic problem. Centers and medians are especially important in distributed systems because they are ideal locations for placing resources that need to be shared among different processes in a network. This paper presents simple self-stabilizing algorithms for locating centers and medians of trees. Since these algorithms are self-stabilizing, they can tolerate transient failures. In addition, they can automatically adjust to a dynamically changing tree topology. After the algorithms are presented, their correctness is proven and upper bounds on their time complexity are established. Finally, extensions of our algorithms to trees with arbitrary, positive edge costs are sketched.
Journal Article
Empowerment of Tribal Women Through Family Planning Programme – A Micro Study of Sandeshkhali Block of Sundarban Area
Our present study aims to find out the impact of literacy status of tribal women on knowledge, attitude and method about family planning programme of Sandeshkhali block of Sundarban area. The effect of different age group of tribal women is also taken into consideration. The statistical analysis reflect generally, higher the literacy status higher will be the acceptance of family planning programme, age will not be a factor regarding non-acceptance of the programme.
Journal Article
A Self-Organized Grouping (SOG) Framework for Efficient Grid Resource Discovery
Dynamic and heterogeneous characteristics of large-scale Grids make the fundamental problem of resource discovery a great challenge. This paper presents a self-organized grouping (SOG) framework that achieves efficient Grid resource discovery by forming and maintaining autonomous resource groups. Each group dynamically aggregates a set of resources together with respect to similarity metrics of resource characteristics. The SOG framework takes advantage of the strengths of both centralized and decentralized approaches that were previously developed for Grid/P2P resource discovery. The design of SOG minimizes the overhead incurred by the process of group formation and maximizes the performance of resource discovery. The way SOG approach handles resource discovery queries is metaphorically similar to searching for a word in an English dictionary, by identifying its alphabetical group at the first place, and then performing a lexical search within the group. Because multi-attribute range queries represent an important aspect of resource discovery, we devise a generalized approach using a space-filling curve in conjunction with the SOG framework. We exploit the Hilbert space-filling curve’s locality preserving and dimension reducing mapping. This mapping provides a 1-dimensional grouping attribute to be used by the SOG framework. Experiments show that the SOG framework achieves superior look-up performance that is more scalable, stable and efficient than other existing approaches. Furthermore, our experimental results indicate that the SOG framework has little dependence on factors such as resource density, query type, and Grid size.
Journal Article
Locally Self-Adjusting Hypercubic Networks
In a prior work (ICDCS 2017), we presented a distributed self-adjusting algorithm DSG for skip graphs. DSG performs topological adaption to communication pattern to minimize the average routing costs between communicating nodes. In this work, we present a distributed self-adjusting algorithm (referred to as DyHypes) for topological adaption in hypercubic networks. One of the major differences between hypercubes and skip graphs is that hypercubes are more rigid in structure compared skip graphs. This property makes self-adjustment significantly different in hypercubic networks than skip graphs. Upon a communication between an arbitrary pair of nodes, DyHypes transforms the network to place frequently communicating nodes closer to each other to maximize communication efficiency, and uses randomization in the transformation process to speed up the transformation and reduce message complexity. We show that, as compared to DSG, DyHypes reduces the transformation cost by a factor of \\(O(\\log n)\\), where \\(n\\) is the number of nodes involved in the transformation. Moreover, despite achieving faster transformation with lower message complexity, the combined cost (routing and transformation) of DyHypes is at most a \\(\\log \\log n\\) factor more than that of any algorithm that conforms to the computational model adopted for this work. Similar to DSG, DyHypes is fully decentralized, conforms to the \\(\\mathcal{CONGEST}\\) model, and requires \\(O(\\log n)\\) bits of memory for each node, where \\(n\\) is the total number of nodes.
Paper
Locally Self-Adjusting Skip Graphs
We present a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the \\(\\mathcal{CONGEST}\\) model (i.e. uses \\(O(\\log n)\\) bit messages), and requires \\(O(\\log n)\\) bits of memory for each node, where \\(n\\) is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model.
Paper
