Search

Your search keyword '"ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008)"' showing total 6 results
Start Over Author "ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008)" Topic computer science
6 results on '"ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008)"'

1. The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction

Author

Alain Cournier, Stephane Rovedakis, Vincent Villain, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), and Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy

Subjects
Polynomial, K-ary tree, Computer science, Breadth-first search, 0102 computer and information sciences, 02 engineering and technology, Minimum spanning tree, k-minimum spanning tree, Distributed systems, Polynomial algorithm, 01 natural sciences, Theoretical Computer Science, Distributed minimum spanning tree, 0202 electrical engineering, electronic engineering, information engineering, Transient (computer programming), ComputingMilieux_MISCELLANEOUS, Minimum degree spanning tree, Spanning tree, 020206 networking & telecommunications, State (functional analysis), Spanning tree construction, Stabilization, Computer Science Applications, Fault-tolerance, Tree (data structure), Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Mutual exclusion, Routing (electronic design automation), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Information Systems
Abstract

The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i.e., routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recover a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O(da) and a step complexity in O(nb) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in O(d2) and its step complexity is in O(n6). To our knowledge, since in general the diameter of a network is much smaller than the number of nodes (log(n) in average instead of n), this algorithm reaches the best compromise of the literature between the complexities in terms of rounds and in terms of steps.

Published
2019
Full Text
View/download PDF

2. Optimization in a Self-stabilizing Service Discovery Framework for Large Scale Systems

Author

Anissa Lamani, Florent Chuffart, Eddy Caron, Franck Petit, Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Andréa W. Richa, Christian Scheideler, ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Scheme (programming language), Theoretical computer science, Range query (data structures), Computer science, Distributed computing, Service discovery, 0102 computer and information sciences, 02 engineering and technology, Overlay, 01 natural sciences, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Service Discovery Framework, Computer Science::Distributed, Parallel, and Cluster Computing, computer.programming_language, Structure (mathematical logic), 020206 networking & telecommunications, Lexicographical order, Self-Stabilizing, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Propagation of Information, Key (cryptography), Table (database), Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract

Ability to find and get services is a key requirement in the development of large-scale distributed sys- tems. We consider dynamic and unstable environments, namely Peer-to-Peer (P2P) systems. In previous work, we designed a service discovery solution called Distributed Lexicographic Placement Table (DLPT), based on a hierar- chical overlay structure. A self-stabilizing version was given using the Propagation of Information with Feedback (PIF) paradigm. In this paper, we introduce the self-stabilizing COPIF (for Collaborative PIF) scheme. An algo- rithm is provided with its correctness proof. We use this approach to improve a distributed P2P framework designed for the services discovery. Significantly efficient experimental results are presented., Comment: (2012)

Published
2012
Full Text
View/download PDF

3. On Cluster Resource Allocation for Multiple Parallel Task Graphs

Author

Frédéric Desprez, Henri Casanova, Frédéric Suter, Information and Computer Sciences [Hawaii] (ICS), University of Hawai‘i [Mānoa] (UHM), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre de Calcul de l'IN2P3 (CC-IN2P3), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
020203 distributed computing, Job shop scheduling, Computer Networks and Communications, Data parallelism, Computer science, Distributed computing, Parallel algorithm, Approximation algorithm, 02 engineering and technology, Theoretical Computer Science, Scheduling (computing), Artificial Intelligence, Hardware and Architecture, Scalability, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software
Abstract

International audience; Many scientific applications can be structured as Parallel Task Graphs (PTGs), that is, graphs of data-parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, both from the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm.

Published
2010
Full Text
View/download PDF

4. Forecasting for Grid and Cloud Computing On-Demand Resources Based on Pattern Matching

Author

Adrian Muresan, Frédéric Desprez, Eddy Caron, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Algorithms and Software Architectures for Distributed and HPC Platforms (AVALON), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
business.industry, Computer science, Real-time computing, Approximation algorithm, SPADES, 020206 networking & telecommunications, Workload, Cloud computing, 02 engineering and technology, Cloud Computing, Grid, computer.software_genre, Resource (project management), Grid computing, Cloud testing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Pattern matching, business, computer
Abstract

International audience; The Cloud phenomenon brings along the cost-saving benefit of dynamic scaling. As a result, the question of efficient resource scaling arises. Prediction is necessary as the virtual resources that Cloud computing uses have a setup time that is not negligible. We propose an approach to the problem of workload prediction based on identifying similar past occurrences of the current short-term workload history. We present in detail the Cloud client resource auto-scaling algorithm that uses the above approach to help when scaling decisions are made, as well as experimental results by using real-world traces from Cloud and Grid platforms. We also present an overall evaluation of this approach, its potential and usefulness for enabling efficient auto-scaling of Cloud user resources.

Published
2010
Full Text
View/download PDF

5. A practical study of self-stabilization for prefix-tree based overlay networks

Author

V Acretoaie, Eddy Caron, Cédric Tedeschi, École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Design and Implementation of Autonomous Distributed Systems (MYRIADS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), IEEE, ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), INRIA, and École normale supérieure de Lyon (ENS de Lyon)

Subjects
Theoretical computer science, Fault-Tolerance, Computer science, Distributed computing, Service discovery, Overlay network, Self-stabilization, 02 engineering and technology, Time to live, Overlay Schemes, Time-To-Live, Tree (data structure), 020204 information systems, Convergence (routing), Trie, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Routing (electronic design automation), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Self-Stabilization
Abstract

As part of The International Conference on High Performance Computing and Simulation (HPCS 2010); International audience; Service discovery is crucial in the development of fully decentralized computational grids. Among the significant amount of work produced by the convergence of peer-to-peer (P2P) systems and grids, a new kind of overlay networks, based on prefix trees (a.k.a., tries), has emerged. In particular, the Distributed Lexicographic Placement Table (DLPT) approach is a decentralized and dynamic service discovery service. Fault-tolerance within the DLPT approach is achieved through best-effort policies relying on formal self-stabilization results. Self-stabilization means that the tree can become transiently inconsistent, but is guaranteed to autonomously converge to a correct topology after arbitrary crashes, in a finite time. However, during convergence, the tree may not be able to process queries correctly. In this paper, we present some simulation results having several objectives. First, we investigate the interest of self-stabilization for such architectures. Second, we explore, still based on simulation, a simple Time-To-Live policy to avoid useless processing during convergence time.

Published
2010
Full Text
View/download PDF

6. A Bi-Criteria Algorithm for Scheduling Parallel Task Graphs on Clusters

Author

Frédéric Suter, Frédéric Desprez, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre de Calcul de l'IN2P3 (CC-IN2P3), Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), ANR-08-SEGI-0025,SPADES,Plateforme de Services Pour Architecture Petascale et DistribuéES.(2008), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
020203 distributed computing, Computer science, business.industry, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Task parallelism, Graph theory, Cloud computing, 02 engineering and technology, Parallel computing, computer.software_genre, Scheduling (computing), Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Task analysis, Concurrent computing, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Cluster analysis, business, computer, Algorithm
Abstract

International audience; Applications structured as parallel task graphs exhibit both data and task parallelism, and arise in many domains. Scheduling these applications on parallel platforms has been a long-standing challenge. In the case of a single homogeneous cluster, most of the existing algorithms focus on the reduction of the application completion time (makespan). But in presence of resource managers such as batch schedulers and due to accentuated pressure on energy concerns, the produced schedules also have to be efficient in terms of resource usage. In this paper we propose a novel bi-criteria algorithm, called biCPA, able to optimize these two performance metrics either simultaneously or separately. Using simulation over a wide range of experimental scenarios, we find that biCPA leads to better results than previously published algorithms.

Published
2010

Catalog

Books, media, physical & digital resources
See catalog results