Browsing by Subject "Parallel algorithms"
Now showing items 1-20 of 27
-
Article
Automated implementation of complex distributed algorithms specified in the IOA language
(2009)IOA is a formal language for describing Input/Output automata that serves both as a formal specification language and as a programming language (Garland et al. in http://theory.lcs.mit.edu/tds/ioa/manual.ps, 2004). The IOA ...
-
Conference Object
Comparison of techniques used for mapping parallel algorithms to message-passing multiprocessors
(IEEE, 1994)This paper presents a comparison study of popular clustering and mapping heuristics which are used to map task-flow graphs to message-passing multiprocessors. To this end, we use task-graphs which are representative of ...
-
Article
Computational assessment of distributed decomposition methods for stochastic linear programs
(1998)Incorporating uncertainty in optimization models gives rise to large, structured mathematical programs. Decomposition procedures are well-suited for parallelization, thus providing a promising venue for solving large ...
-
Article
Computing on a partially eponymous ring
(2009)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
-
Conference Object
Coordinated cooperative work using undependable processors with unreliable broadcast
(IEEE Computer Society, 2014)With the end of Moore's Law in sight, parallelism became the main means for speeding up computationally intensive applications, especially in the cases where large collections of tasks need to be performed. Network ...
-
Article
Distributed Balancing of Commodity Networks Under Flow Interval Constraints
(2018)We consider networks the nodes of which are interconnected via directed edges, each able to admit a flow (or weight) within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. ...
-
Article
Distributed Calculation of Edge-Disjoint Spanning Trees for Robustifying Distributed Algorithms against Man-in-the-Middle Attacks
(2017)In this paper we provide a distributed methodology to allow a network of agents, tasked to execute a distributed algorithm, to overcome Man-in-the-middle attacks that aim at steering the result of the algorithm towards ...
-
Article
Distributed Fault Diagnosis in Discrete Event Systems via Set Intersection Refinements
(2018)We extend and verify diagnosability for a class of set intersection refinement strategies, which can be used for distributed state estimation and fault diagnosis in nondeterministic finite automata that are observed at ...
-
Article
Distributed Finite-Time Average Consensus in Digraphs in the Presence of Time Delays
(2015)Most algorithms for distributed averaging only guarantee asymptotic convergence. This paper introduces a distributed protocol that allows nodes to find the exact average of the initial values in a finite and minimum number ...
-
Article
Distributed finite-time average-consensus with limited computational and storage capability
(2017)Consensus is a fundamental feature of distributed systems, and it is the prerequisite for several complex tasks, such as flocking of mobile robots, localization in wireless-sensor networks, or decentralized control of smart ...
-
Article
Distributed finite-time calculation of node eccentricities, graph radius and graph diameter
(2016)The distributed calculation of node eccentricities, graph radius and graph diameter are fundamental steps to tune network protocols (e.g., setting an adequate time-to-live of packets), to select cluster heads, or to execute ...
-
Article
Distributed matrix scaling and application to average consensus in directed graphs
(2013)We propose a class of distributed iterative algorithms that enable the asymptotic scaling of a primitive column stochastic matrix, with a given sparsity structure, to a doubly stochastic form. We also demonstrate the ...
-
Conference Object
Distributed, low contention task allocation
(IEEE, 1996)A new approach to solve task allocation problems is proposed. The method involves introducing a load balancing network, a new class of distributed, and asynchronous algorithms for task allocation in shared memory ...
-
Article
Evaluating a dependable sharable atomic data service on a planetary-scale network
(2009)Practical implementations of atomically consistent read/write memory service are important building blocks for higher level applications. This is especially true when data accessibility and survivability are provided by a ...
-
Article
Failure-sensitive analysis of parallel algorithms with controlled memory access concurrency
(2007)The abstract problem of using P failure-prone processors to cooperatively update all locations of an N-element shared array is called Write-All. Solutions to Write-All can be used iteratively to construct efficient simulations ...
-
Article
Fault-tolerant semifast implementations of atomic read/write registers
(2009)This paper investigates time-efficient implementations of atomic read-write registers in message-passing systems where the number of readers can be unbounded. In particular we study the case of a single writer, multiple ...
-
Article
Functional algorithm simulation of the fast multipole method: Architectural implications
(1996)Functional Algorithm Simulation in a methodology for predicting the computation and communication characteristics of parallel algorithms for a class of scientific problems, without actually performing the expensive numerical ...
-
Conference Object
Integer weight balancing in directed graphs in the presence of communication delays
(Institute of Electrical and Electronics Engineers Inc., 2015)A digraph with positive weights on its edges is weight-balanced if, for each node, the sum of the weights of the incoming edges equals the sum of the weights of the outgoing edges. Weight-balanced digraphs play an important ...
-
Article
Long-lived Rambo: Trading knowledge for communication
(2007)Shareable data services providing consistency guarantees, such as atomicity (linearizability), make building distributed systems easier. However, combining linearizability with efficiency in practical algorithms is difficult. ...
-
Article
Mapping fortran programs to single assignment semantics for efficient parallelization
(1998)This paper presents Mustang, a system that automatically parallellizes Fortran programs by mapping them to single assignment semantics. Specifically, sequential Fortran source programs are translated into IF1, a ...