Search

Your search keyword '"Tucci-Piergiovanni, Sara"' showing total 16 results
Start Over Author "Tucci-Piergiovanni, Sara" Publisher hal ccsd
16 results on '"Tucci-Piergiovanni, Sara"'

1. Ethereum Proof-of-Stake under Scrutiny

Author

Pavloff, Ulysse, Amoussou-Guenou, Yackolley, Tucci-Piergiovanni, Sara, Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Centre de Recherche en Economie et Droit (CRED), Université Paris-Panthéon-Assas, and CEA DILS

Subjects
Bouncing attack, Ethereum, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 2012 ACM Subject Classification Theory of computation → Distributed algorithms, Ethereum Proof-of-Stake, Availability, Computer systems organization → Dependable and fault-tolerant systems and networks phrases Ethereum Proof-of-Stake, Liveness, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Bouncing attack Digital Object Identifier 10.4230/OASIcs
Abstract

Ethereum has undergone a recent change called the Merge, which made Ethereum a Proof-of-Stake blockchain shifting closer to BFT consensus. Ethereum, which wished to keep the best of the two protocols designs (BFT and Nakomoto-style), now has an involved consensus protocol as its core. The result is a blockchain being possibly produced in a tree-like form while participants try to finalize blocks. Several attacks jeopardizing liveness have been found in this new setting. The Ethereum community has responded by creating a patch. We discovered a new attack on the patched protocol. To support our analysis, we propose a new formalization of the properties of liveness and availability of the Ethereum blockchain, and we provide a pseudo-code. We believe this formalization to be helpful for other analyses as well. Our results yield that the Ethereum Proof-of-Stake has probabilistic liveness, influenced by the parameter describing the time frame allowed for validators to change their mind about the current main chain.

Published
2022

2. Yggdrasil: Secure State Sharding of Transactions and Smart Contracts that Self-adapts to Transaction Load

Author

Djari, Aimen, Amoussou-Guenou, Yackolley, Anceaume, Emmanuelle, Tucci Piergiovanni, Sara, Pozzo, Antonella, Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-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)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)

Subjects
[INFO]Computer Science [cs]
Abstract

This paper presents Yggdrasil a sharding solution for permissionless blockchains that supports both payment transactions and general Ethereum-like smart contracts. Yggdrasil allows to split and merge shard dynamically leveraging decentralized mechanisms to assign nodes to shards in a secure way. A new 2PC protocol allows to guarantee the execution of smart contracts distributed across different shards even when shards dynamically re-organise. An experimental study confirms the capability of Yggdrasil to scale and to adapt to transaction load.

Published
2022

3. Simulation study of Sycomore ++ , a self-adapting graph-based permissionless distributed ledger

Author

Djari, Aimen, Anceaume, Emmanuelle, Tucci-Piergiovanni, Sara, Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-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)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)

Subjects
distributed ledger quality, [INFO]Computer Science [cs], Graph-based distributed ledger, agent-based simulation, scalability
Abstract

International audience; The arrival of Bitcoin [1] drove the shift to decentralized ecosystems through the exchange of transactions without intermediary. However, one of the main challenges that need to face permissionless blockchains are scalability and security. In this paper, we present a performance evaluation of Sycomore ++ , a permissionless graph-based distributed ledger whose main feature is to dynamically self-adapt the number of created blocks to the current number of submitted transactions, and compare them with the ones of Bitcoin and Sycomore, a graph-based distributed ledger. Our evaluation relies on agentbased simulations to evaluate the capability of these distributed ledgers to address the aforementioned challenges, within different execution contexts.

Published
2022

4. Sycomore ++ , un registre distribué orienté graphe auto-adaptatif

Author

Djari, Aimen, Anceaume, Emmanuelle, Tucci-Piergiovanni, Sara, Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-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)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)

Subjects
Registre distribué, [INFO]Computer Science [cs], simulation basée agents, scalabilité, graphe
Abstract

International audience; L'arrivée de Bitcoin a entraîné le passage vers des écosystèmes décentralisés grâce à l'échange de transactions sans tiers de confiance. Cependant, parmi les principaux défis auxquels doivent faire face les blockchains non permissionnées figurent la scalabilité et la sécurité. C'est dans cette optique qu'a été créé Sycomore, un registre distribué orienté graphe dont la structure s'auto-adapte au débit de transactions soumises. Dans cet article, nous présentons et évaluons une extension de Sycomore, Sycomore ++ dont la principale caractéristique est l'auto-adaptation de son débit de création de blocs au débit de transactions soumises. Nous comparons ensuite ses performances à celles de Bitcoin et de Sycomore. En s'appuyant sur des simulations par agents, nous évaluons la capacité de ces registres distribués à relever les défis susmentionnés, dans différents contextes d'exécution. L'un des principaux enseignements tirés de ces simulations est la capacité de Sycomore ++ à réduire considérablement le temps de confirmation des transactions, à réagir rapidement à toute variation soudaine du débit de soumission des transactions et à minimiser le gaspillage d'énergie, en comparaison avec les autres registres distribués basés sur le Proof-of-Work précédemment cités.

Published
2022

5. An agent-based simulation study of Sycomore ++ , a scalable and self-adapting graph-based permissionless distributed ledger

Author

Anceaume, Emmanuelle, Djari, Aimen, Tucci-Piergiovanni, Sara, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-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)-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), CEA- Saclay (CEA), and Commissariat à l'énergie atomique et aux énergies alternatives (CEA)

Subjects
distributed ledger quality, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], Graph-based distributed ledger, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], scalability, agent-based simulation
Abstract

International audience; The arrival of Bitcoin [1] drove the shift to decentralized ecosystems through the exchange of transactions without intermediary. However, one of the main challenges that need to face permissionless blockchains are scalability and security. In this paper, we present a performance evaluation of Sycomore ++ , a permissionless graph-based distributed ledger whose main feature is to dynamically self-adapt the number of created blocks to the current number of submitted transactions, and compare them with the ones of Bitcoin and Sycomore, a graph-based distributed ledger. Our evaluation relies on agentbased simulations to evaluate the capability of these distributed ledgers to address the aforementioned challenges, within different execution contexts. One of the main lessons drawn from these intensive simulations is the capability of Sycomore ++ to drastically reduce transaction confirmation time with respect to the other two ledgers, to quickly react to any sudden variation of the transaction submission rate, to minimize the computational power waste w.r.t. PoW-based permissionless distributed ledgers, and to surpass Bitcoin in terms of resilience to a network adversarial environment. We also study resilience to adversarial miners that want to endanger the quality of the graph showing that, as in Bitcoin, the adversary is limited by its computational power.

Published
2022

6. On Finality in Blockchains

Author

Anceaume, Emmanuelle, Del Pozzo, Antonella, Rieutord, Thibault, Tucci-Piergiovanni, Sara, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-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-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-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)-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)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES), Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France, 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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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 Rennes 1 (UR1), 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)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-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)-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é de Rennes (UNIV-RENNES)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), ANR-20-CE25-0002,ByBloS,Au-delà des Blockchains : Modules de construction pour les applications à grande échelle zero-confiance multi-utilisateurs(2020), 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 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)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))

Subjects
consistency properties, FOS: Computer and information sciences, Finality, Blockchain, Byzantine tolerant algorithms, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Impossibility results, Byzantine tolerant implementations, Theory of computation, Consistency criteria
Abstract

This paper focuses on blockchain finality, which refers to the time when it becomes impossible to remove a block that has previously been appended to the blockchain. Blockchain finality can be deterministic or probabilistic, immediate or eventual. To favor availability against consistency in the face of partitions, most blockchains only offer probabilistic eventual finality: blocks may be revoked after being appended to the blockchain, yet with decreasing probability as they sink deeper into the chain. Other blockchains favor consistency by leveraging the immediate finality of Consensus - a block appended is never revoked - at the cost of additional synchronization. The quest for "good" deterministic finality properties for blockchains is still in its infancy, though. Our motivation is to provide a thorough study of several possible deterministic finality properties and explore their solvability. This is achieved by introducing the notion of bounded revocation, which informally says that the number of blocks that can be revoked from the current blockchain is bounded. Based on the requirements we impose on this revocation number, we provide reductions between different forms of eventual finality, Consensus and Eventual Consensus. From these reductions, we show some related impossibility results in presence of Byzantine processes, and provide non-trivial results. In particular, we provide an algorithm that solves a weak form of eventual finality in an asynchronous system in presence of an unbounded number of Byzantine processes. We also provide an algorithm that solves eventual finality with a bounded revocation number in an eventually synchronous environment in presence of less than half of Byzantine processes. The simplicity of the arguments should better guide blockchain designs and link them to clear formal properties of finality., LIPIcs, Vol. 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021), pages 6:1-6:19

Published
2020

7. Rational Behaviors in Committee-Based Blockchains

Author

Amoussou-Guenou, Yackolley, Biais, Bruno, Potop-Butucaru, Maria, Tucci-Piergiovanni, Sara, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), CEA- Saclay (CEA), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Ecole des Hautes Etudes Commerciales (HEC Paris), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Quentin Bramas, Rotem Oshman, and Paolo Romano

Subjects
Game Theory, BFT Consensus, Computer systems organization → Dependable and fault-tolerant systems and networks, [INFO]Computer Science [cs], Theory of computation → Solution concepts in game theory, Blockchains
Abstract

We study the rational behaviors of participants in committee-based blockchains. Committee-based blockchains rely on specific blockchain consensus that must be guaranteed in presence of rational participants. We consider a simplified blockchain consensus algorithm based on existing or proposed committee-based blockchains that encapsulate the main actions of the participants: voting for a block, and checking its validity. Knowing that those actions have costs, and achieving the consensus gives rewards to committee members, we study using game theory how strategic participants behave while trying to maximize their gains. We consider different reward schemes, and found that in each setting, there exist equilibria where blockchain consensus is guaranteed; in some settings however, there can be coordination failures hindering consensus. Moreover, we study equilibria with trembling participants, which is a novelty in the context of committee-based blockchains. Trembling participants are rational that can do unintended actions with a low probability. We found that in presence of trembling participants, there exist equilibria where blockchain consensus is guaranteed; however, when only voters are rewarded, there also exist equilibria where validity can be violated., LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 12:1-12:16

Published
2020

8. Consensus en Présence de Participants Rationnels et Byzantins

Author

Amoussou-Guenou, Yackolley, Biais, Bruno, Potop-Butucaru, Maria, Tucci-Piergiovanni, Sara, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Ecole des Hautes Etudes Commerciales (HEC Paris), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), and Amoussou-Guenou, Yackolley

Subjects
Équilibre de Nash, Blockchain, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Comité, Théorie des jeux, Terminaison, Validité
Abstract

International audience; Nous étudions les comportements des participants d'un protocole de consensus lorsqu'ils présentent des comportements rationnels ou Byzantins. Nous nous inspirons des protocoles de blockchains tolérantes aux fautes Byzantines (comme Tendermint). Dans ces protocoles, les participants proposent des blocs et s'échangent des messages. Un bloc est accepté si une majorité de participants envoie le message correspondant à ce bloc (un vote), et les votants sont récompensés. Dans ce travail, nous étudions les conditions sous lesquelles ce protocole satisfait les deux propriétés suivantes : la terminaison (le système converge vers une décision) et la validité (toute décision est valide), quand certains participants sont rationnels et les autres Byzantins. Nous supposons que les participants Byzantins ont le comportement infligeant le plus de dégâts au système, tandis que les stratégies des participants rationnels forment un équilibre Bayésien parfait. Nous considérons les paramètres suivant : (i) le nombre de votes nécessaires, ν, pour qu'un bloc soit considéré comme accepté, et (ii) le nombre de participants Byzantins, noté f , dans le système. Nous obtenons les résultats suivants : Quand f ≥ ν, les blocs invalides sont acceptés, et donc la validité ne peut être garantie ; Quand f < ν, il existe un équilibre où la validité et la terminaison sont toutes deux satisfaites, par contre, il existe d'autres équilibres où la terminaison, et dans quelques cas la validité, ne sont pas satisfaites. Cela nous permet de conclure à l'existence de problèmes de coordination dans les protocoles étudiés.

Published
2020

9. International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Author

Danos, Vincent, Herlihy, Maurice, Potop-Butucaru, Maria, Prat, Julien, Tucci-Piergiovanni, Sara, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Analyse Statique par Interprétation Abstraite (ANTIQUE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science (Brown University), Brown University, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Économie et Statistique (CREST), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI)-École polytechnique (X)-École Nationale de la Statistique et de l'Administration Économique (ENSAE Paris)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))

Subjects
[INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2020

10. Reconfigurable Lattice Agreement and Applications

Author

Kuznetsov, Petr, Rieutord, Thibault, Tucci-Piergiovanni, Sara, Autonomic and Critical Embedded Systems (ACES), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Informatique et Réseaux (INFRES), Télécom ParisTech, Institut Polytechnique de Paris (IP Paris), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Institut Polytechnique Paris, and CEA List

Subjects
FOS: Computer and information sciences, Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or $servers$) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the $clients$ of the service should be able to reach some form of agreement on the system configuration. We observe that this agreement is naturally captured via a $lattice$ partial order on the system states. We propose an asynchronous implementation of $reconfigurable$ lattice agreement that implies elegant reconfigurable versions of a large class of $lattice$ abstract data types, such as max-registers and conflict detectors, as well as popular distributed programming abstractions, such as atomic snapshot and commit-adopt.

Published
2019

11. Blockchains basées sur du Consensus Répété

Author

Amoussou-Guenou, Yackolley, Del Pozzo, Antonella, Potop-Butucaru, Maria, Tucci-Piergiovanni, Sara, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), and Amoussou-Guenou, Yackolley

Subjects
Blockchain, Consensus, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Tendermint, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Équité
Abstract

International audience; Les blockchains basées sur le consensus sont considérées aujourd'hui comme étant parmi les alternatives les plus viables aux blockchains utilisant un mécanisme de Proof-of-work (Bitcoin, Ethereum,. . .), ces dernières étant très énergivores et ne garantissent pas une cohérence forte. Elles ont pour but d'offrir des garanties de cohérence forte (pas de fourches) dans un système ouvert grâce à : (i) un ensemble de validateurs qui produit un bloc via une variante du protocole de consensus Practical Byzantine Fault Tolerant (PBFT), et (ii) un mécanisme de sélection qui choisit dynamiquement les noeuds qui seront validateurs pour le bloc suivant. Dans cet article, nous caractérisons précisément le problème que tentent de résoudre ces protocoles de blockchains. Nous étudions Tendermint. Nos contributions sont les suivantes : nous formalisons pour la première fois le protocole Tendermint, puis nous présentons le modèle et les hypothèses précis sous lesquels il atteint son objectif. Nous prouvons que dans un système ultimement synchrone et avec une hypothèse supplémentaire, une légère modification du protocole résout une variante (i) du consensus pour la production d'un bloc, et une variante (ii) du consensus répété pour construire la chaîne de bloc ; cela si strictement moins d'un tiers des validateurs est atteint de fautes Byzantines. Nous nous sommes ensuite intéressés à l'étude de l'équité du mécanisme de récompense dans ces blockchains. Cette étude préliminaire permet d'établir que garantir (ultimement) l'équité de la récompense requiert une communication (ultimement) synchrone.

Published
2019

12. Rationals vs Byzantines in Consensus-based Blockchains

Author

Amoussou-Guenou, Yackolley, Biais, Bruno, Potop-Butucaru, Maria, Tucci-Piergiovanni, Sara, Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Ecole des Hautes Etudes Commerciales (HEC Paris), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Département Ingénierie Logiciels et Systèmes (DILS), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, CEA List, LIP6, Sorbonne Université, CNRS, UMR 7606, HEC Paris, and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))

Subjects
[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

In this paper we analyze from the game theory point of view Byzantine Fault Tolerantblockchains when processes exhibit rational or Byzantine behavior. Our work is the first tomodel the Byzantine-consensus based blockchains as a committeecoordination game. Ourfirstcontribution is to offer a game-theoretical methodology to analyseequilibrium interactions be-tween Byzantine and rational committee members in Byzantine FaultTolerant blockchains.Byzantine processes seek to inflict maximum damage to the system,while rational processesbest-respond to maximise their expected net gains. Oursecondcontribution is to derive condi-tions under which consensus properties are satisfied or not in equilibrium. When the majoritythreshold is lower than the proportion of Byzantine processes, invalid blocks are accepted inequilibrium. When the majority threshold is large, equilibrium can involvecoordination fail-ures, in which no block is ever accepted. However, when the cost ofaccepting invalid blocks islarge, there exists an equilibrium in which blocks are accepted iff they are valid.

Published
2019

13. On Cancellation of Transactions in Bitcoin-like Blockchains

Author

Gürcan, Önder, Pedrosa, Alejandro, Tucci-Piergiovanni, Sara, Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Gürcan, Önder

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO]Computer Science [cs], [INFO] Computer Science [cs], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; Bitcoin-like blockchains do not envisage any specific mechanism to avoid unfairness for the users. Hence, unfair situations, like impossibility of cancellation of transactions explicitly or having uncon-firmed transactions, reduce the satisfaction of users dramatically, and, as a result, they may leave the system entirely. Such a consequence would impact significantly the security and the sustainability of the blockchain. Based on this observation, in this paper, we focus on explicit cancellation of transactions to improve the fairness for users. We propose a novel scheme with which it is possible to cancel a transaction, whether it is confirmed in a block or not, under certain conditions. We show that the proposed scheme is superior to the existing workarounds and is imple-mentable for Bitcoin-like blockchains.

Published
2018

14. Model-Based Analysis and Engineering of Automotive Architectures with EAST-ADL

Author

Kolagari, Ramin, Chen, Dejiu, Lanusse, Agnes, Librino, Renato, Lönn, Henrik, Mahmud, Nidhal, Mraidha, Chokri, Reiser, Mark-Oliver, Torchiaro, Sandra, Tucci-Piergiovanni, Sara, Wägemann, Tobias, Yakymets, Nataliya, Nuremberg Institut of Technology, Royal Institute of Technology [Stockholm] ( KTH ), Département Ingénierie Logiciels et Systèmes ( DILS ), Laboratoire d'Intégration des Systèmes et des Technologies ( LIST ), Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay, Advanced Technology and Research, Volvo Group, Hull University, Technische Universität Berlin ( TUB ), Centro Ricerche Fiat ( CRF ), Centro Ricerche Fiat, Royal Institute of Technology [Stockholm] (KTH ), Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, University of Hull [United Kingdom], Technische Universität Berlin (TU), Centro Ricerche Fiat (CRF), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), and Technical University of Berlin / Technische Universität Berlin (TU)

Subjects
Optimization, [ INFO ] Computer Science [cs], Automotive Software Development, Model-Based Software Development, [INFO]Computer Science [cs], Timing, AUTOSAR, Functional Safety, EAST-ADL, Dependability, Modelling, Software Product Lines, ISO 26262
Abstract

International audience; Modern cars have turned into complex high-technology products, subject to strict safety and timing requirements , in a short time span. This evolution has translated into development processes that are not as efficient, flexible and agile as they could or should be. This paper presents the main aspects and capabilities of a rich model-based design framework, founded on EAST-ADL. EAST-ADL is an architecture description language specific to the automotive domain and complemented by a methodology compliant with the functional safety standard for the automotive domain ISO26262. The language and the methodology are used to develop an information model in the sense of a conceptual model, providing the engineer the basis for specifying the various aspects of the system. Inconsistencies, redundancies, and partly even missing system description aspects can be found automaticlally by advanced analyses and optimization capabilities to effectively improve development processes of modern cars.

Published
2015

15. Multi-Agent Optimization for Safety Analysis of Cyber-Physical Systems: Position Paper

Author

Gürcan, Önder, YAKYMETS, Nataliya, Tucci-Piergiovanni, Sara, Radermacher, Ansgar, Département Ingénierie Logiciels et Systèmes ( DILS ), Laboratoire d'Intégration des Systèmes et des Technologies ( LIST ), Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay-Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Saclay, Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))

Subjects
[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], self-adaptation, [ INFO.INFO-MA ] Computer Science [cs]/Multiagent Systems [cs.MA], [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, [ INFO.INFO-ES ] Computer Science [cs]/Embedded Systems, safety analysis, [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], optimization, FMEA, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], FMECA
Abstract

International audience; Failure Mode, Effects and Criticality Analysis (FMECA) is one of the safety analysis methods recommended by most of the international standards. The classical FMECA is made in a form of a table filled in either manually or by using safety analysis tools. In both cases, the design engineers have to choose the trade-offs between safety and other development constraints. In the case of complex cyber-physical systems (CPS) with thousands of specified constraints, this may lead to severe problems and significantly impact the overall criticality of CPS. In this paper, we propose to adopt optimization techniques to automate the decision making process conducted after FMECA of CPS. We describe a multi-agent based optimization method which extends classical FMECA for offering optimal solutions in terms of criticality and development constraints of CPS.

Published
2015

16. A Mixed Integer Linear Programming formulations for optimizing timing performance during the deployment phase in real-time systems design

Author

Mehiaoui, Asma, Sara, Tucci-Piergiovanni, Babau, Jean-Philippe, Laboratoire d'Ingénierie dirigée par les modèles pour les Systèmes Embarqués (LISE), Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Tucci-Piergiovanni, Sara, Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), and Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR], [INFO.INFO-AR] Computer Science [cs]/Hardware Architecture [cs.AR]
Abstract

Following the standard development methodologies for the real-time systems, the designer has to deploy functions exchanging signals information onto an execution platform. The deployment consists of the three stages i.e. (i) the placement of functions and signals on a distributed network of nodes, (ii) the partitioning of these functions and signals in fixed-priority tasks and messages, respectively, and (iii) the tasks and messages scheduling (i.e. tasks and messages priority assignment). As the design choices at each stage highly influence the timing performance of the system, in the present report, we are interested in supporting designers in their choices during the three stages. To achieve that, we use the Mixed Integer Linear Programming (MILP) technique. Therefore, we first give a MILP formulation which deals with the three stages at the same time; it is called one-step MILP formulation. Then, we face the high complexity of the one-step MILP formulation by decomposing it into two less complex MILP formulations; we call that two-step MILP formulation. The first MILP formulation treats the placement of functions and exchanged signals to nodes and buses, respectively. The second MILP formulation determines the partitioning of functions (resp. signals) in tasks (resp. messages) and assigns priorities to each partition.

Published
2012

Catalog

Books, media, physical & digital resources
See catalog results