Search

Your search keyword '"Tredan, Gilles"' showing total 16 results
Start Over Author "Tredan, Gilles" Database OpenAIRE
16 results on '"Tredan, Gilles"'

1. On the relevance of APIs facing fairwashed audits

Author

Bourrée, Jade Garcia, Merrer, Erwan Le, Tredan, Gilles, and Rottembourg, Benoît

Subjects
Software Engineering (cs.SE), FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Computers and Society, Computer Science - Software Engineering, Computers and Society (cs.CY), Machine Learning (cs.LG)
Abstract

Recent legislation required AI platforms to provide APIs for regulators to assess their compliance with the law. Research has nevertheless shown that platforms can manipulate their API answers through fairwashing. Facing this threat for reliable auditing, this paper studies the benefits of the joint use of platform scraping and of APIs. In this setup, we elaborate on the use of scraping to detect manipulated answers: since fairwashing only manipulates API answers, exploiting scraps may reveal a manipulation. To abstract the wide range of specific API-scrap situations, we introduce a notion of proxy that captures the consistency an auditor might expect between both data sources. If the regulator has a good proxy of the consistency, then she can easily detect manipulation and even bypass the API to conduct her audit. On the other hand, without a good proxy, relying on the API is necessary, and the auditor cannot defend against fairwashing. We then simulate practical scenarios in which the auditor may mostly rely on the API to conveniently conduct the audit task, while maintaining her chances to detect a potential manipulation. To highlight the tension between the audit task and the API fairwashing detection task, we identify Pareto-optimal strategies in a practical audit scenario. We believe this research sets the stage for reliable audits in practical and manipulation-prone setups., 18 pages, 7 figures

Published
2023

2. On the Feasibility of Perfect Resilience with Local Fast Failover

Author

Foerster, Klaus-Tycho, Hirvonen, Juho, Pignolet, Yvonne-Anne, Schmid, Stefan, Tredan, Gilles, University of Vienna [Vienna], Department of Information and Computer Science [Aalto], Helsinki Institute for Information Technology (HIIT), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University-Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, DFINITY Foundation [Zurich], Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Aalto University-University of Helsinki-Aalto University-University of Helsinki, Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, and TREDAN, Gilles

Subjects
Computer Science - Networking and Internet Architecture, Networking and Internet Architecture (cs.NI), FOS: Computer and information sciences, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract

In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. These rules determine for each incoming link from which a packet may arrive and the set of local link failures (i.e., the failed links incident to a node), on which outgoing link a packet should be forwarded. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. (ACM PODC 2012) and also Chiesa et al. (IEEE/ACM Trans. Netw. 2017) showed that it is not always possible to provide perfect resilience. Interestingly, not much more is known currently about the feasibility of perfect resilience. This paper revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. We first derive several fairly general impossibility results: By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; furthermore, while planarity is necessary, it is also not sufficient for perfect resilience. On the positive side, we show that graph families closed under link subdivision allow for simple and efficient failover algorithms which simply skip failed links. We demonstrate this technique by deriving perfect resilience for outerplanar graphs and related scenarios, as well as for scenarios where the source and target are topologically close after failures., Comment: To appear in the proceedings of the 2nd Symposium on Algorithmic Principles of Computer Systems (APOCS) 2021

Published
2021

3. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

Author

Foerster, Klaus-Tycho, Hirvonen, Juho, Pignolet, Yvonne-Anne, Schmid, Stefan, Tredan, Gilles, University of Vienna [Vienna], Aalto University, DFINITY Foundation [Zurich], Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Attiya, Hagit, University of Vienna, Professorship Suomela J., DFINITY, Centre National de la Recherche Scientifique (CNRS), Department of Computer Science, and Aalto-yliopisto

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 2012 ACM Subject Classification Networks → Routing protocols, Resilience, Theory of computation → Distributed algorithms phrases Resilience, Computer systems organization → Dependable and fault-tolerant systems and networks, Theory of computation → Distributed algorithms, Networks → Routing protocols, Local Failover
Abstract

In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs., LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 46:1-46:3

Published
2020

5. TamperNN: Efficient Tampering Detection of Deployed Neural Nets

Author

Tredan Gilles, Erwan Le Merrer, the World Is Distributed Exploring the tension between scale and coordination (WIDE), 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), 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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Université de Bretagne Sud (UBS)-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)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-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)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées

Subjects
FOS: Computer and information sciences, 021110 strategic, defence & security studies, Class (computer programming), Computer Science - Machine Learning, Computer Science - Cryptography and Security, Artificial neural network, Computer science, Reliability (computer networking), Computer Vision and Pattern Recognition (cs.CV), Real-time computing, 0211 other engineering and technologies, Computer Science - Computer Vision and Pattern Recognition, 02 engineering and technology, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Machine Learning (cs.LG), Range (mathematics), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, State (computer science), Quantization (image processing), Digital watermarking, Cryptography and Security (cs.CR), MNIST database, ComputingMilieux_MISCELLANEOUS
Abstract

Neural networks are powering the deployment of embedded devices and Internet of Things. Applications range from personal assistants to critical ones such as self-driving cars. It has been shown recently that models obtained from neural nets can be trojaned ; an attacker can then trigger an arbitrary model behavior facing crafted inputs. This has a critical impact on the security and reliability of those deployed devices. We introduce novel algorithms to detect the tampering with deployed models, classifiers in particular. In the remote interaction setup we consider, the proposed strategy is to identify markers of the model input space that are likely to change class if the model is attacked, allowing a user to detect a possible tampering. This setup makes our proposal compatible with a wide range of scenarios, such as embedded models, or models exposed through prediction APIs. We experiment those tampering detection algorithms on the canonical MNIST dataset, over three different types of neural nets, and facing five different attacks (trojaning, quantization, fine-tuning, compression and watermarking). We then validate over five large models (VGG16, VGG19, ResNet, MobileNet, DenseNet) with a state of the art dataset (VGGFace2), and report results demonstrating the possibility of an efficient detection of model tampering., Comment: In the 30th International Symposium on Software Reliability Engineering (ISSRE 2019)

Published
2019

6. The Bouncer Problem: Challenges to Remote Explainability

Author

Merrer, Erwan Le and Tredan, Gilles

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Cryptography and Security, Statistics - Machine Learning, Machine Learning (stat.ML), Cryptography and Security (cs.CR), Machine Learning (cs.LG)
Abstract

The concept of explainability is envisioned to satisfy society's demands for transparency on machine learning decisions. The concept is simple: like humans, algorithms should explain the rationale behind their decisions so that their fairness can be assessed. While this approach is promising in a local context (e.g. to explain a model during debugging at training time), we argue that this reasoning cannot simply be transposed in a remote context, where a trained model by a service provider is only accessible through its API. This is problematic as it constitutes precisely the target use-case requiring transparency from a societal perspective. Through an analogy with a club bouncer (which may provide untruthful explanations upon customer reject), we show that providing explanations cannot prevent a remote service from lying about the true reasons leading to its decisions. More precisely, we prove the impossibility of remote explainability for single explanations, by constructing an attack on explanations that hides discriminatory features to the querying user. We provide an example implementation of this attack. We then show that the probability that an observer spots the attack, using several explanations for attempting to find incoherences, is low in practical settings. This undermines the very concept of remote explainability in general.

Published
2019
Full Text
View/download PDF

7. Fast Abstracts and Student Forum Proceedings - EDCC 2016 - 12th European Dependable Computing Conference

Author

Tredan, Gilles and Schwefel, Hans Peter

Subjects
FOS: Computer and information sciences, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract

Fast Abstracts are short presentations of work in progress or opinion pieces and aim to serve as a rapid and flexible mechanism to (i) Report on current work that may or may not be complete; (ii) Introduce new ideas to the community; (iii) State positions on controversial issues or open problems. On the other hand, the goal of the Student Forum is to encourage students to attend EDCC and present their work, exchange ideas with researchers and practitioners, and get early feedback on their research efforts., Comment: 12th European Dependable Computing Conference, Gothenburg, Sweden, September 5-9, 2016

Published
2016
Full Text
View/download PDF

8. Request Complexity of VNet Topology Extraction: Dictionary-Based Attacks

Author

Pignolet, Yvonne-Anne, Schmid, Stefan, and Tredan, Gilles

Subjects
Networking and Internet Architecture (cs.NI), FOS: Computer and information sciences, Computer Science - Networking and Internet Architecture, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
Abstract

The network virtualization paradigm envisions an Internet where arbitrary virtual networks (VNets) can be specified and embedded over a shared substrate (e.g., the physical infrastructure). As VNets can be requested at short notice and for a desired time period only, the paradigm enables a flexible service deployment and an efficient resource utilization. This paper investigates the security implications of such an architecture. We consider a simple model where an attacker seeks to extract secret information about the substrate topology, by issuing repeated VNet embedding requests. We present a general framework that exploits basic properties of the VNet embedding relation to infer the entire topology. Our framework is based on a graph motif dictionary applicable for various graph classes. Moreover, we provide upper bounds on the request complexity, the number of requests needed by the attacker to succeed., full version of paper at NETYS 2013

Published
2013

9. Revisiting Content Availability in Distributed Online Social Networks

Author

Schiöberg, Doris, Schneider, Fabian, Tredan, Gilles, Uhlig, Steve, and Feldmann, Anja

Subjects
Computer Science - Networking and Internet Architecture, Networking and Internet Architecture (cs.NI), Social and Information Networks (cs.SI), FOS: Computer and information sciences, Computer Science - Social and Information Networks
Abstract

Online Social Networks (OSN) are among the most popular applications in today's Internet. Decentralized online social networks (DOSNs), a special class of OSNs, promise better privacy and autonomy than traditional centralized OSNs. However, ensuring availability of content when the content owner is not online remains a major challenge. In this paper, we rely on the structure of the social graphs underlying DOSN for replication. In particular, we propose that friends, who are anyhow interested in the content, are used to replicate the users content. We study the availability of such natural replication schemes via both theoretical analysis as well as simulations based on data from OSN users. We find that the availability of the content increases drastically when compared to the online time of the user, e. g., by a factor of more than 2 for 90% of the users. Thus, with these simple schemes we provide a baseline for any more complicated content replication scheme., Comment: 11pages, 12 figures; Technical report at TU Berlin, Department of Electrical Engineering and Computer Science (ISSN 1436-9915)

Published
2012
Full Text
View/download PDF

10. Centralité du second ordre : Calcul distribué de l'importance de noeuds dans un réseau complexe

Author

Kermarrec, Anne-Marie, Le Merrer, Erwan, Sericola, Bruno, Tredan, Gilles, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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), 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), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), INRIA, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-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)-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 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-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)-Université de Rennes (UNIV-RENNES)-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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-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)

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract

A complex network can be modeled as a graph representing the "who knows who" relationship. In the context of graph theory for social networks, the notion of centrality is used to assess the relative importance of nodes in a given network topology. For example, in a network composed of large dense clusters connected through only a few links, the nodes involved in those links are particularly critical as far as the network survivability is concerned. This may also impact any application running on top of it. Such information can be exploited for various topological maintenance issues to prevent congestion and disruptance. This can also be used offline to identify the most important nodes in large social interaction graphs. Several forms of centrality have been proposed so far. Yet, they suffer from imperfections : designed for abstract graphs, they are either of limited use (degree centrality), either uncomputable in a distributed setting (random walk betweenness centrality). In this paper we introduce a novel form of centrality : the second order centrality which can be computed in a fully decentralized manner. This provides locally each node with its relative criticity and relies on a random walk visiting the network in an unbiased fashion. To this end, each node records the time elapsed between visits of that random walk (called return time in the sequel) and computes the standard deviation (or second order moment) of such return times. Both through theoretical analysis and simulation, we show that the standard deviation can be used to accurately identify critical nodes as well as to globally characterize graphs topology in a fully decentralized way.

Published
2009

11. Centralite du second ordre : Calcul distribue de l'importance de noeuds

Author

Kermarrec, Anne-Marie, Le Merrer, Erwan, Sericola, Bruno, Tredan, Gilles, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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), 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), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Chaintreau, Augustin and Magnien, Clemence, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-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)-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 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-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)-Université de Rennes (UNIV-RENNES)-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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-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)

Subjects
Caractérisation de graphes, Marches Aléatoires, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Centralité
Abstract

International audience; Dans le contexte de la théorie des graphes pour les réseaux sociaux, la notion de centralité a été introduite pour mesurer l'importance relative de noeuds dans une topologie donnée. Connaître cette importance est un enjeu majeur pour assurer la robustesse des systèmes distribués. De nombreuses formes de centralités ont déjà été définies; dans le contexte des systèmes distribués, elles sont cependant soit d'un intérêt limité (centralité des degrés), soit difficilement distribuables (centralité d'intermédiarité). Dans cet article, nous introduisons une nouvelle forme de centralité: la centralité du second ordre. Celle-ci est calculée de façon totalement distribuée, au moyen d'une marche aléatoire. Elle attribue à chaque noeud une valeur indicatrice de son importance dans le graphe. Pour cela, chaque noeud conserve les temps écoulés entre deux visites de la marche et calcule l'écart type de ces temps. Nous montrons que cet écart type est une mesure de centralité qui permet également de caractériser globalement la topologie d'un graphe donné.

Published
2009

12. Routing Attacks as a Viable Threat: Can Software Systems Protect Themselves?

Author

Alistarh, Dan, Avramopoulos, Ioannis, Kuznetsov, Petr, and Tredan, Gilles

Subjects
routing attacks, byzantine fault-tolerance
Abstract

In this paper, we show that distributed systems are vul- nerable to routing attacks and propose an architecture to obviate this vulnerability. A somewhat surprising finding is that even a small-scale routing attack can completely dis- rupt the operation of a state-machine replication service. The architecture that we propose is based on the following simple ideas: (1) Circumvent the adversary if possible and (2) if it is not possible, relax the application semantics.

13. A Generic Trust Framework For Large-Scale Open Systems Using Machine Learning

Author

Liu, Xin, Tredan, Gilles, and Datta, Anwitaman

Subjects
FOS: Computer and information sciences, large-scale systems, Computer Science - Learning, Computer Science - Cryptography and Security, machine learning, Computer Science - Distributed, Parallel, and Cluster Computing, features, Distributed, Parallel, and Cluster Computing (cs.DC), trust management, Cryptography and Security (cs.CR), Machine Learning (cs.LG)
Abstract

In many large scale distributed systems and on the web, agents need to interact with other unknown agents to carry out some tasks or transactions. The ability to reason about and assess the potential risks in carrying out such transactions is essential for providing a safe and reliable environment. A traditional approach to reason about the trustworthiness of a transaction is to determine the trustworthiness of the specific agent involved, derived from the history of its behavior. As a departure from such traditional trust models, we propose a generic, machine learning approach based trust framework where an agent uses its own previous transactions (with other agents) to build a knowledge base, and utilize this to assess the trustworthiness of a transaction based on associated features, which are capable of distinguishing successful transactions from unsuccessful ones. These features are harnessed using appropriate machine learning algorithms to extract relationships between the potential transaction and previous transactions. The trace driven experiments using real auction dataset show that this approach provides good accuracy and is highly efficient compared to other trust mechanisms, especially when historical information of the specific agent is rare, incomplete or inaccurate., Comment: 30 pages

14. Grafting Arborescences for Extra Resilience of Fast Rerouting Schemes

Author

Stefan Schmid, Andrzej Kamisinski, Gilles Tredan, Klaus-Tycho Foerster, Yvonne-Anne Pignolet, TREDAN, Gilles, University of Vienna [Vienna], Dfinity Switzerland, Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)

Subjects
Spanning tree, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer science, Distributed computing, Grafting (decision trees), [INFO] Computer Science [cs], Network topology, Telecommunications network, Failover, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Forwarding plane, [INFO]Computer Science [cs], Resilience (network), Heterogeneous network
Abstract

International audience; To provide a high availability and to be able to quickly react to link failures, most communication networks feature fast rerouting (FRR) mechanisms in the data plane. However, configuring these mechanisms to provide a high resilience against multiple failures is algorithmically challenging, as rerouting rules can only depend on local failure information and need to be predefined. This paper is motivated by the observation that the common approach to design fast rerouting algorithms, based on spanning trees and covering arborescences, comes at a cost of reduced resilience as it does not fully exploit the available links in heterogeneous topologies. We present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine ("graft") multiple spanning arborescences to improve resilience. We compare our algorithms analytically and empirically, and show that they can significantly improve not only the resilience, but also accelerate the preprocessing to generate the local fast failover rules.

Published
2021

15. Implications of Routing Coherence and Consistency on Network Optimization

Author

Pignolet, Yvonne-Anne, Schmid, Stefan, Trédan, Gilles, Dfinity Switzerland, University of Vienna [Vienna], Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and TREDAN, Gilles

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS
Abstract

International audience; In network optimization problems, from traffic engineering to network monitoring, the routing model is typically considered as something given and fixed. This paper is motivated by the fundamental question how the ability to change and optimize the routing model itself influences the efficiency at which communication networks can be operated. To this end, we identify two main dimensions of the routing model: consistency (of a single route) and coherence (of sets of routes). We present analytical results on the impact of the routing model on the achievable route diversity as well as on the runtime of solving optimization problems underlying different case studies. We also uncover that it can sometimes be beneficial to artificially restrict the routing model, to significantly reduce the computational complexity without negatively affecting the route diversity much.

Published
2020

16. Adaptive Data Collection Mechanisms for Smart Monitoring of Distribution Grids

Author

Kemal, Mohammed Seifu, Olsen, Rasmus Løvenstein, Peter Schwefel, Hans, and Tredan, Gilles

Subjects
FOS: Computer and information sciences, Computer Science - Distributed, Parallel, and Cluster Computing, FOS: Electrical engineering, electronic engineering, information engineering, Computer Science - Systems and Control, Systems and Control (eess.SY), Distributed, Parallel, and Cluster Computing (cs.DC)
Abstract

Smart Grid systems not only transport electric energy but also information which will be active part of the electricity supply system. This has led to the introduction of intelligent components on all layers of the electrical grid in power generation, transmission, distribution and consumption units. For electric distribution systems, Information from Smart Meters can be utilized to monitor and control the state of the grid. Hence, it is indeed inherent that data from Smart Meters should be collected in a resilient, reliable, secure and timely manner fulfilling all the communication requirements and standards. This paper presents a proposal for smart data collection mechanisms to monitor electrical grids with adaptive smart metering infrastructures. A general overview of a platform is given for testing, evaluating and implementing mechanisms to adapt Smart Meter data aggregation. Three main aspects of adaptiveness of the system are studied, adaptiveness to smart metering application needs, adaptiveness to changing communication network dynamics and adaptiveness to security attacks. Execution of tests will be conducted in real field experimental set-up and in an advanced hardware in the loop test-bed with power and communication co-simulation for validation purposes., 5 pages, 2 figures , Hans-Peter Schwefel. 12th European Dependable Computing Conference (EDCC 2016), September 5-9, 2016, Gothenburg, Sweden. Proceedings of Student Forum - EDCC 2016

Published
2016

Catalog

Books, media, physical & digital resources
See catalog results