Cyber-Physical Systems typically consist of a combination of mobile devices, embedded systems and computers to monitor, sense, and actuate with the surrounding real world. These computing elements are usually wireless...
详细信息
Cyber-Physical Systems typically consist of a combination of mobile devices, embedded systems and computers to monitor, sense, and actuate with the surrounding real world. These computing elements are usually wireless, interconnected to share data and interact with each other, with the server part and also with cloud computing services. In such a heterogeneous environment, new applications arise to meet ever-increasing needs and these are an important challenge to the processing capabilities of devices. For example, automatic driving systems, manufacturing environments, smart city management, etc. To meet the requirements of said application contexts, the system can create computing processes to distribute the workload over the network and/or a cloud computing server. Multiple options arise in relation to what network nodes should support the execution of the processes. This paper focuses on this problem by introducing a distributed computational model to dynamically share these tasks among the computing nodes and considering the inherent variability of the context in these environments. Our novel approach promotes the integration of the computing resources, with externally supplied cloud services, to fulfill modern application requirements. A prototype implementation for the proposed model has been built and an application example has been designed to validate the proposal in a real working environment. (C) 2017 Elsevier B.V. All rights reserved.
In a network, a distributed consensus algorithm is fully characterized by its weighting matrix. Although there exist numerical methods for obtaining the optimal weighting matrix, we have not found an in-network implem...
详细信息
In a network, a distributed consensus algorithm is fully characterized by its weighting matrix. Although there exist numerical methods for obtaining the optimal weighting matrix, we have not found an in-network implementation of any of these methods that works for all network topologies. In this paper, we propose an in-network algorithm for finding such an optimal weighting matrix.
At Google, the PageRank algorithm helps rankings in search results by providing measures of web page importance. This paper builds upon the distributed randomized approach for this algorithm proposed in our recent wor...
详细信息
ISBN:
(纸本)9781612848006
At Google, the PageRank algorithm helps rankings in search results by providing measures of web page importance. This paper builds upon the distributed randomized approach for this algorithm proposed in our recent works. To reduce computation and communication, we develop a method to systematically aggregate web pages into groups by exploiting the sparsity inherent in the web. Each group computes an aggregated PageRank, which can be distributed among group members. We provide a decentralized scheme for its computation and analyze convergence properties.
In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the relations....
详细信息
In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the relations. The relations provide a fine-grained granularity to specify causality relations between distributed nonatomic events. The set of relations between nonatomic events is complete in first-order predicate logic, using only the causality relation between atomic events, for a pair of distributed nonatomic events X and Y, the evaluation of any of the causality relations requires \Nx\ x \N-Y(\) integer comparisons, where \N-X\ and \N-Y\, respectively, are the number of nodes on which the two nonatomic events X and Y occur. In this paper: we show that this polynomial complexity of evaluation can by simplified to a linear complexity using properties of partial orders. Specifically, we show that most relations can be evaluated in min(\N-X\, \N-Y\) integer comparisons, some in \N-X\ integer comparisons, and the others in \N-Y\ integer comparisons. During the derivation of the efficient testing conditions, we also define special system execution prefixes associated with distributed nonatomic events and examine their knowledge-theoretic significance.
An interval of a sequential process is a sequence of consecutive events of this process. The set of intervals defined on a distributed computation defines an abstraction of this distributed computation, and the tradit...
详细信息
An interval of a sequential process is a sequence of consecutive events of this process. The set of intervals defined on a distributed computation defines an abstraction of this distributed computation, and the traditional causality relation on events induces a relation on the set of intervals that we call I-precedence. An important question is then, "Is the interval-based abstraction associated with a distributed computation consistent?" To answer this question, this paper introduces a consistency criterion named interval consistency (IC). Intuitively, this criterion states that an interval-based abstraction of a distributed computation is consistent if its I-precedence relation does not contradict the sequentiality of each process. More formally, IC is defined as a property of a precedence graph. Interestingly, the IC criterion can be operationally characterized in terms of timestamps (whose values belong to a lattice). The paper uses this characterization to design a versatile protocol that, given intervals defined by a daemon whose behavior is unpredictable, breaks them (in a nontrivial manner) in order to produce an abstraction satisfying the IC criterion. Applications to communication-induced check-pointing are suggested. (C) 2002 Elsevier Science (USA).
Events in a distributed computation have been implicitly modeled in the literature in the isolated contexts of various applications. This paper presents a unifying framework for expressing and analyzing events at vari...
详细信息
Events in a distributed computation have been implicitly modeled in the literature in the isolated contexts of various applications. This paper presents a unifying framework for expressing and analyzing events at various levels of atomicity in a distributed computation. In the framework, events at any level of atomicity are defined and composed in terms of events at a finer level of atomicity using hierarchical views of the distributed computation. We identify and prove three properties that are satisfied by each level of atomicity. Results based on these properties that hold for any one level of atomicity apply to all levels of atomicity. The properties also show that the global states at the various levels of atomicity correspond to embedded lattices of global states, thereby providing different abstract views of the same computation. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
At some abstraction level a distributed computation can be modeled as a partial order on a set of observable events. This paper presents an analysis technique which can be superimposed on distributed computations to a...
详细信息
At some abstraction level a distributed computation can be modeled as a partial order on a set of observable events. This paper presents an analysis technique which can be superimposed on distributed computations to analyze the structure of control flows terminating at observable events. A general algorithm working on the longest control hows of distributed computations is introduced. Moreover it is shown how this algorithm can be simplified according to the position of observable events with respect to communication events.
This paper identifies two classes of communication patterns that occur in distributed computations and explores their properties. It first examines local patterns. primarily 10 and 01 intervals, that occur at nodes in...
详细信息
This paper identifies two classes of communication patterns that occur in distributed computations and explores their properties. It first examines local patterns. primarily 10 and 01 intervals, that occur at nodes in distributed computations. These local patterns form building blocks that are then used to define the global patterns, termed segments and paths, that occur across nodes in distributed computations. By controlling the predicates on the local patterns used to define segments and paths. various types of segments and paths can be defined, While a causal chain captures only the causality relation, it turns out that some of the other message sequences that do not capture causality also play a significant role in the analysis of a distributed computation. The paper presents a framework and shows that a number of key concepts and structures characterizing distributed computations are specific instantiations of the communication patterns identified in the framework. (C) 2002 Elsevier Science (USA).
The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers...
详细信息
The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an off-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural. We define predicate control formally and show that, in its full generality, the problem is NP-complete. We find efficient solutions for some important classes of predicates including "disjunctive predicates", "mutual exclusion predicates", and "readers writers predicates". For each class of predicates, we determine the necessary and sufficient conditions for solving predicate control and describe an efficient algorithm for determining a synchronization strategy. In the case of "independent mutual exclusion predicates", we determine that predicate control is NP-complete and describe an efficient algorithm that finds a solution under certain constraints. (C) 2003 Elsevier Inc. All rights reserved.
暂无评论