73 publications classées par:
type de publication
: Revue avec comité de lecture
Articles Allani M., Garbinato B. & Pietzuch P. (2012). CHAMS: Churn-aware overlay construction for media streaming. Peer-to-Peer Networking and Applications, 1-16. [doi] [web of science]
Holzer A., Eugster P. & Garbinato B. (2012). ALPS – Adaptive Location-based Publish/Subscribe. Computer Networks, 56(12), 2949 - 2962. [doi] [web of science]
Holzer A., Eugster P. & Garbinato B. (2012). Evaluating Implementation Strategies for Location-based Multicast Addressing. IEEE Transactions on Mobile Computing, PP(99), 1. [doi] [web of science]
Garbinato B., Holzer A. & Vessaz F. (2010). Context-aware broadcasting approaches in mobile ad hoc networks. Computer Networks, 54(7), 1210 - 1228. [doi] [web of science] [abstract]
The aim of this paper is to compare different context-aware broadcasting approaches in mobile ad hoc networks (MANETs) and to evaluate their respective performances. Message broadcasting is one of the core challenges brought up by distributed systems and has therefore largely been studied in the context of traditional network structures, such as the Internet. With the emergence of MANETs, new broadcasting algorithms especially geared at these networks have been introduced. The goal of these broadcasting algorithms is to ensure that a maximum number of nodes deliver the broadcasted message (reliability), while ensuring that the minimum number of nodes retransmit the broadcasted message (efficiency), in order to save their resources, such as bandwidth or battery. In recent years, as more and more mobile devices have become context-aware, several broadcasting algorithms have been introduced that take advantage of contextual information in order to improve their performance. We distinguish four approaches with respect to context: (1) context-oblivious approaches, (2) network traffic-aware approaches, (3) power-aware approaches, and (4) location-aware approaches. This paper precisely aims at presenting these four different broadcasting approaches and at measuring the performance of algorithms built upon them.
Garbinato B., Rochat D., Tomassini M. & Vessaz F. (2010). Injecting Power-Awareness into Epidemic Information Dissemination in Sensor Networks. Future Generation Computer Systems, 26, 868-876.
Eugster P., Garbinato B. & Holzer A. (2009). Pervaho: a Specialized Middleware for Mobile Context-aware Applications. Electronic Commerce Research, 9(4), 245-268. [doi] [url] [web of science] [abstract]
The concept of context-awareness offers a great potential for the future of mobile applications. In order to be developed in an optimal way, mobile context-aware applications need appropriate middleware services. This paper introduces Pervaho, an integrated middleware aimed specifically at supporting the development and testing of mobile context-aware applications. To illustrate the use of Pervaho, we walk through the development of a concrete mobile application and show how it can be built on top of Pervaho's location-based publish/subscribe service. We also illustrate how a specialized mobility testing tool significantly simplifies the process of testing proximity-based semantics. We then present the implementation of Pervaho, which is based on a set of communication protocols geared at mesh networks. Finally, we provide a performance analysis of our implementation.
Garbinato B. & Rickebusch I. (2006). A topological condition for solving fair exchange in byzantine environments. Information and Communications Security, Lecture Notes in Computer Science (LNCS), 4307, 30-49. [doi] [url]
Garbinato B. & Rupp P. (2003). From Ad Hoc Networks to Ad Hoc Applications. ERCIM News, 28-30.
Garbinato B. & Guerraoui R. (2000). An Open Framework for Reliable Distributed Computing. ACM Computing Surveys, 32(1es), 22-26. [doi] [url]
Guerraoui R., Eugster P., Felber P., Garbinato B. & Mazouni K. (2000). Experiences with Object Group Systems. Software: Practice and Experience, 30(12), 1375–1404. [doi] [web of science]
Guerraoui R., Garbinato B. & Mazouni K.R. (1997). GARF: A tool for programming reliable distributed applications. IEEE Concurrency, 5(4), 32-39. [doi] [web of science] [abstract]
The authors discuss Garf object-oriented tool that supports the design and programming of reliable distributed applications. Garf lets developers program an application and then replicate its critical components over several machines. Using a built-in library of distributed abstractions, developers can choose a replication strategy for each component of the application.
Garbinato B., Guerraoui R. & Mazouni K.R. (1995). Implementation of the GARF Replicated Object Plateform. Distributed Systems Engineering Journal, 2, 14-27. [doi]
B. Garbinato, X. Défago, R. Guerraoui & K.R. Mazouni (1994). Abstractions pour la Programmation Concurrente dans GARF. Calculateurs parallèles, 6(2), 85-98. [url]
Parties de livre Doudou A., Garbinato B. & Guerraoui R. (2005). Tolerating Arbitrary Failures with State Machine Replication. Dependable Computing Systems: Paradigms, Performance Issues, and Applications (pp. 27-56). Wiley. [url]
Doudou A., Garbinato B. & Guerraoui R. (2002). Encapsulating Failure Detection: From Crash to Byzantine Failures. Lecture Notes in Computer Science (LNCS), Reliable Software Technologies - Ada-Europe 2002 (Vol. 2361/2002, pp. 24-50). Springer. [doi] [url]
Doudou A., Garbinato B. & Guerraoui R. (2000). Atomic Broadcast in a Byzantine Model. Proceedings of the 3r International Workshop on Communication-Based Systems (CBS-3) (pp. 179-195). Kluwer Academic Publishers.
Felber P., Garbinato B. & Guerraoui R. (1997). Towards Reliable CORBA: Integration vs. Service Approach. In Max Mühlhäuser (Ed.), Special Issues in Object-Oriented Programming (pp. 199-205). dpunkt-Verlag. [url]
Garbinato B., Felber P. & Guerraoui R. (1997). Right Abstractions on Adequate Frameworks for Building Adaptable Distributed Applications. In Max Mühlhäuser (Ed.), Special Issues in Object-Oriented Programming (pp. 24-28). dpunkt-Verlag. [url]
Chapitre Allani M., Garbinato B. & Pedone F. (2009). Application Layer Multicast. In Garbinato B., Miranda H. & Rodrigues L. (Eds.), Middleware for Network Eccentric and Mobile Applications (pp. 191-218). Springer. [doi] [url]
Eugster P., Garbinato B. & Holzer A. (2009). Middleware Support for Context-aware Applications. Middleware for Network Eccentric and Mobile Applications (pp. 305-322). Springer. [doi] [url]
Garbinato B. & Guerraoui R. (1999). The Bast Framework for Reliable Distributed Computing. In Fayad M & Johnson R. (Eds.), Domain-Specific Application Frameworks - Frameworks Experience by Industry (pp. 283-326). Wiley. [url]
Actes de conférence (partie) Vessaz F., Garbinato B., Moro A. & Holzer A. (2013). Developing, Deploying and Evaluating Protocols with ManetLab. Lecture Notes in Computer Science (LNCS), Proceedings of the International Conference on NETworked sYStems, 7583 (pp. 89-104). Springer-Verlag. [doi] [abstract]
Evaluating the performance of MANET-specific communication protocols is essential to build robust mobile ad hoc applications. Unfortunately, most existing evaluation results are either based on simulations - which makes it difficult to draw conclusions beyond confined lab settings - or they are based on custom testbed results - which makes it difficult to reproduce them. In order to overcome this challenge, we introduce ManetLab, a modular and configurable software framework for creating and running testbeds to evaluate MANET-specific protocols. With ManetLab, one can easily configure and automate reproducible protocol executions on standard computer hardware, and thus provides both the accuracy of testbed-based evaluations and the reproducibility of simulation-based evaluations. After presenting ManetLab's extensible architecture, based on the notion of modular protocol stack, we show how it helps evaluate the performance of different broadcast protocols in real MANETs and how its results compare with simulation-based results.
Bostanipour B., Garbinato B. & Holzer A. (2012, Août). Spotcast – A Communication Abstraction for Proximity-Based Mobile Applications. NCA'12, Proceedings of the 2012 IEEE 11th International Symposium on Network Computing and Applications (pp. 121 -129). IEEE Press. [doi] [web of science]
Holzer A., Garbinato B. & Vessaz F. (2012). Middleware for location privacy: an overview. RACS '12, Proceedings of the 2012 ACM Research in Applied Computation Symposium (pp. 296–303). ACM, New York, NY, USA. [doi] [url]
Ataee S., Garbinato B., Allani M. & Pedone F. (2011). ScaleStream - An Adaptive Replication Algorithm for Scalable Multimedia Streaming. NCA '11, Proceedings of the 2011 IEEE 10th International Symposium on Network Computing and Applications (pp. 229–234). IEEE Computer Society, Washington, DC, USA. [doi] [web of science]
Holzer A., Vessaz F., Pierre S. & Garbinato B. (2011). PLAN-B: Proximity-Based Lightweight Adaptive Network Broadcasting. NCA '11, Proceedings of the 2011 IEEE 10th International Symposium on Network Computing and Applications (pp. 265–270). IEEE Computer Society, Washington, DC, USA. [doi] [web of science]
Allani M., Leitao J., Garbinato B. & Rodrigues L. (2010, Fév). RASM: A Reliable Algorithm for Scalable Multicast. PDP '10, Parallel, Distributed and Network-Based Processing (PDP), 2010 18th Euromicro International Conference on (pp. 137 -144). IEEE Press. [doi]
Garbinato B., Holzer A. & Vessaz F. (2010). Six-shot multicast: A location-aware strategy for efficient message routing in MANETs. NCA '10, Proceedings of the 9th IEEE International Symposium on Network Computing and Applications (NCA'10) (pp. 1-9). IEEE Computer Society Press. [doi] [url] [abstract]
In this paper, we introduce six-shot multicast (6Shot), a location-aware multicast algorithm devised for mobile ad hoc networks. Multicast is a one-to-many communication scheme and has largely been studied in such networks. Indeed, this communication primitive can be used as a building block for popular services, such as data streaming or group communication. The particularity of 6Shot is the location- aware routing scheme of its implementation, which offers improved efficiency in terms of message overhead compared to existing algorithms, for a reasonable cost in terms of reliability.
Garbinato B. & Rickebusch I. (2010, Juin). Impossibility results on fair exchange. GI-Edition - Lecture Notes in Informatics (LNI), 10th International Conference on Innovative Internet Community Services (I2CS), Jubilee Edition 2010, p-165 (pp. 507-518). Bonner Köllen Verlag. [url]
Allani M., Garbinato B., Malekpour A. & Pedone F. (2009, Nov). Reliable Communication Infrastructure for Adaptive Data Replication. Lecture Notes in Computer Science (LNCS), On the Move to Meaningful Internet Systems: OTM 2009, 5870/2009 (pp. 634-652). Springer. [doi] [url] [web of science]
Allani M., Garbinato B., Malekpour A. & Pedone F. (2009, Juil). QuoCast : a Resource Aware Algorithm for Reliable Peer-to-Peer Multicast. Proceedings of The 8th IEEE International Symposium on Networking Computing and Applications (NCA'09) (pp. 20-27). IEEE Computer Society. [doi] [url] [web of science]
Garbinato B., Rochat D. & Tomassini M. (2009). Power-Efficient Epidemic Information Dissemination in Sensor Networks. Proceedings of Workshop on Bio-Inspired Algorithms for Distributed Systems, BADS 09 (pp. 69-76). [web of science]
Malekpour A., Pedone F., Allani M. & Garbinato B. (2009, Juil). Streamline : an Architecture for Overlay Multicast. Proceedings of The 8th IEEE International Symposium on Networking Computing and Applications (NCA'09) (pp. 44-51). IEEE Computer Society. [doi] [url] [web of science]
Eugster P., Garbinato B. & Holzer A. (2008, Jan). Design and Implementation of the Pervaho Middleware for Mobile Context-aware Applications. Proceedings of the 2008 International MCETECH Conference on e-Technologies (MCETECH'08) (pp. 125-135). IEEE Computer Society. [doi] [url]
Garbinato B., Holzer A. & Vessaz F. (2008, Nov). Six-shot Broadcast: a context-aware algorithm for efficient message diffusion in MANETs. Lecture Notes in Computer Science (LNCS), On the Move to Meaningful Internet Systems: OTM 2008, 5331/2008 (pp. 625-638). Springer. [doi] [url]
Garbinato B., Rochat D. & Tomassini M. (2008). Power-Efficient gossiping in multi-hop ad hoc networks. Proceedings of 2nd International Conference on Autonomic Computing and Communication Systems, Autonomics 2008 (pp. 23-25).
Allani M., Garbinato B., Pedone F. & Stamenkovic M. (2007, Oct). A Gambling Approach to Scalable Resource-Aware Streaming. Proceedings of the 26th IEEE Symposium on Reliable Distributed Systems (SRDS'07) (pp. 288-300). IEEE Computer Society. [doi] [url]
Bugnon S., Garbinato B. & Lebuhan-Jordan C. (2007, Sep). A reference model for the consumption of protected content in home networks. In IEEE Press (Ed.), Proceedings of the 15th IEEE International Conference on Software. Telecommunications and Computer Networks (SoftCom'07) (pp. 1-5). IEEE Press. [doi] [url]
Garbinato B., Guerraoui R., Hulaas J., Kounine A., Monod M. & Spring J.H. (2007, Juil). The weight-watcher service and its lightweight implementation. Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modelling and Simulation (IC-SAMOS'07) (pp. 118 - 127). IEEE Computer Society. [doi] [url]
Garbinato B., Guerraoui R., Hulaas J., Monod M. & Spring J. (2007, Mai). Pervasive Computing with Frugal Objects. Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW'07), 2 (pp. 13-18). IEEE Computer Society. [doi] [url]
Garbinato B., Rochat D. & Tomassini M. (2007, Juil). Impact of Scale-free Topologies on Gossiping in Ad Hoc Networks. Proceedings of the 6th IEEE International Symposium on Network Computing and Applications (NCA'07) (pp. 269-272). IEEE Computer Society. [doi] [url]
Eugster P.Th., Garbinato B. & Holzer A. (2006, Juil). Pervaho: A Development and Test Platform for Mobile Ad hoc Applications. Proceedings of the 3rd Annual International Conference on Mobile and Ubiquitous Systems: Networks and Services (Mobiquitous'06). IEEE Computer Society. [doi] [url]
Garbinato B., Guerraoui R., Hulaas J., Monod M. & Spring J. (2006). Frugal Mobile Objects. Euro-American Workshop on Middleware for Sensor Networks, co-located with the 2nd International Conference on Distributed Computing in Sensor Systems (DCOSS '06) (pp. 41–52). IEEE Press. [pdf]
Garbinato B. & Rickebusch I. (2006, Nov). Orchestrating fair exchanges between mutually distrustful web services. Proceedings of the 3rd ACM workshop on Secure web services (SWS'06) (pp. 33-42). ACM Press. [doi] [url]
Eugster P.Th., Garbinato B. & Holzer A. (2005, Juil). Location-based Publish/Subscribe. Proceedings of the 4th IEEE International Symposium on Network Computing and Applications (NCA'05), Cambridge (MA) (pp. 279-282). IEEE Computer Society. [doi] [url]
Garbinato B., Pedone F. & Schmidt R. (2004, Juin). A modular approach to optimizing highly dynamic distributed systems (Fast Abstract). Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04) - Supplemental Volume (pp. 74-75). IEEE Computer Society. [url]
Garbinato B., Pedone F. & Schmidt R. (2004, Juin). An adaptive algorithm for efficient message diffusion in unreliable environments. Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04) (pp. 507-516). IEEE Computer Society. [doi] [url]
Garbinato B. & Rupp P. (2003, Juin). From Ad Hoc Networks to Ad Hoc Applications. Proceedings of 7th International Conference on Reliable Software Technologies (ConTEL'03), 1 (pp. 145-149). IEEE Press. [url]
Doudou A., Garbinato B. & Guerraoui R. (2000, Oct). Abstractions for Devising Byzantine-Resilient State Machine Replication. Proceedings of the 19th IEEE Symposium on reliable Distributed Systems (SRDS'00) (pp. 14-153). IEEE Computer Society. [doi] [url]
Doudou A., Garbinato B., Guerraoui R. & Schiper A. (1999, Jan). Muteness Failure Detectors: Specification and Implementation. Lecture Notes in Computer Science (LNCS), Proceedings of the 3rd European Dependable Computing Conference (EDCC-3), 1667/1999 (pp. 71-87). Springer. [doi] [url] [web of science]
Garbinato B. & Guerraoui R. (1998, Mai). Flexible protocol composition in Bast. Proceedings of the 18th International Conference on Distributed Computing Systems (ICDCS- 18), Amsterdam, The Netherlands (pp. 22-29). IEEE Computer Society Press. [doi] [web of science]
Guerraoui R., Felber P., Garbinato B. & Mazouni K.R. (1998, Oct). System Support for Object Groups. Proceedings of the 13th ACM Conference on Object-Oriented Programming, Systems, Languages, and applications (OOPSLA'98) (pp. 233-258). ACM Press. [doi] [web of science]
B. Garbinato, P. Felber & R. Guerraoui (1997, Jan). Modeling Protocols as Objects for Structuring Reliable Distributed Systems. Proceedings of the Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS'97) (pp. 165-171). [web of science]
Défago X., Felber P., Garbinato B. & Guerraoui R. (1997, Juin). Reliability with CORBA Event Channels. Proceeding of the 3rd USENIX Conference on Object-Oriented Technologies and Systems (COOTS'97) (pp. 237-244). [url] [web of science]
Garbinato B. & Guerraoui R. (1997, Juin). Using the Strategy Design Pattern to Compose Reliable Distributed Protocols. Proceeding of the 3rd USENIX Conference on Object-Oriented Technologies and Systems (COOTS'97) (pp. 221-232). [web of science]
Felber P., Garbinato B. & Guerraoui R. (1996, Oct). The Design of a CORBA Group Communication Service. Proceedings of the 15th IEEE Symposium on Reliable Distributed Systems (SRDS'96) (pp. 150-159). IEEE Computer Society Press, Niagara (Canada). [doi] [web of science]
Garbinato B., Felber P. & Guerraoui R. (1996, Sep). Strategy Pattern for composing Reliable Distributed Protocols. Proceedings of the 3rd Conference on the Pattern Languages of Programs (PLoP'96). [url]
Garbinato B., Felber P. & Guerraoui R. (1996). Protocol classes for designing reliable distributed environments. Lecture Notes in Computer Science (LNCS), European Conference on Object-Oriented Programming Proceedings (ECOOP'96), 1098 (pp. 316-343). Springer Verlag. [doi]
Guerraoui R., Garbinato B. & Mazouni K.R. (1995, Juin). Lessons from Designing an Implementing GARF. In J.-P. Briot, J.-M. Geib & A. Yonezawa (Eds.), Lecture Notes in Computer Science, Object-Based Parallel and Distributed Computation (OBPDC'95), 1107. Springer Verlag. [doi]
K.R. Mazouni, B. Garbinato & R. Guerraoui (1995, Mars). Building Reliable Client-Server Software Using Actively Replicated Objects. In I. Graham, B. Magnusson, B. Meyer & J.-M. Nerson (Eds.), Proceedings of the TOOLS EUROPE'95 Conference (pp. 37-51). Prentice-Hall, Versailles (France). [url]
Mazouni K.R., Garbinato B. & Guerraoui R. (1995, Août). Filtering Duplicated Invocations Using Symmetric Proxies. Proceedings of the 4th IEEE International Workshop on Object Orientation in Operating Systems (IWOOOS). IEEE Computer Society Press, Lund (Sweden). [doi]
Garbinato B., Guerraoui R. & Mazouni K.R. (1994). Distributed Programming in GARF. In R. Guerraoui, O. Nierstrasz & M. Riveill (Eds.), Lecture Notes in Computer Science, Object-Based Distributed Programming, 791 (pp. 225-239). Springer Verlag. [doi]
Guerraoui R., Garbinato B. & Mazouni K.R. (1994, Sep). The GARF Library Of DSM Consistency Models. Proceedings of the 6th ACM SIGOPS European Workshop (pp. 51-56). ACM Press, Dagstuhl (Germany). [doi]
K.R. Mazouni, B. Garbinato & R. Guerraoui (1994, Juil). Object Replication Support in GARF: Which Group Service to Implement Object Groups?. ECOOP'94 System Implementor's Workshop. [url]
Garbinato B., Guerraoui R. & Mazouni K.R. (1993, Oct). Programming Fault-Tolerant Applications Using Two Orthogonal Object Levels. Proceedings of the 8th International Symposium on Computer and Information Sciences (ISCIS-8).
Garbinato B., Mougeotte E., Ricci N., Iseli C. & Sanchez E. (1993, Août). An Algotronix FPGAs Development System on Mac. Scientific & Engineering Applications of the Macintosh Technical Conference Proceedings (SEAM'93). [url]
Rapports Allani M., Garbinato B., Pedone F., Schmidt R. & Stamenkovic M. (2007). Local-Knowledge Algorithms for Structured Message Diffusion in Unreliable Environments (DOP-20070604). University of Lausanne.
Thèses Ataee S, Garbinato B. (Dir.) (2015). An architecture for adaptive replication-based multimedia streaming in P2P networks. Université de Lausanne, Faculté des hautes études commerciales. [abstract]
This PhD thesis addresses the issue of scalable media streaming in large-scale networking environments. Multimedia streaming is one of the largest sink of network resources and this trend is still growing as testified by the success of services like Skype, Netflix, Spotify and Popcorn Time (BitTorrent-based). In traditional client-server solutions, when the number of consumers increases, the server becomes the bottleneck. To overcome this problem, the Content-Delivery Network (CDN) model was invented. In CDN model, the server copies the media content to some CDN servers, which are located in different strategic locations on the network. However, they require heavy infrastructure investment around the world, which is too expensive. Peer-to-peer (P2P) solutions are another way to achieve the same result. These solutions are naturally scalable, since each peer can act as both a receiver and a forwarder. Most of the proposed streaming solutions in P2P networks focus on routing scenarios to achieve scalability. However, these solutions cannot work properly in video-on-demand (VoD) streaming, when resources of the media server are not sufficient. Replication is a solution that can be used in these situations.¦This thesis specifically provides a family of replication-based media streaming protocols, which are scalable, efficient and reliable in P2P networks. First, it provides SCALESTREAM, a replication-based streaming protocol that adaptively replicates media content in different peers to increase the number of consumers that can be served in parallel. The adaptiveness aspect of this solution relies on the fact that it takes into account different constraints like bandwidth capacity of peers to decide when to add or remove replicas. SCALESTREAM routes media blocks to consumers over a tree topology, assuming a reliable network composed of homogenous peers in terms of bandwidth. Second, this thesis proposes RESTREAM, an extended version of SCALESTREAM that addresses the issues raised by unreliable networks composed of heterogeneous peers.¦Third, this thesis proposes EAGLEMACAW, a multiple-tree replication streaming protocol in which two distinct trees, named EAGLETREE and MACAWTREE, are built in a decentralized manner on top of an underlying mesh network. These two trees collaborate to serve consumers in an efficient and reliable manner. The EAGLETREE is in charge of improving efficiency, while the MACAWTREE guarantees reliability.¦Finally, this thesis provides TURBOSTREAM, a hybrid replication-based streaming protocol in which a tree overlay is built on top of a mesh overlay network. Both these overlays cover all peers of the system and collaborate to improve efficiency and low-latency in streaming media to consumers. This protocol is implemented and tested in a real networking environment using PlanetLab Europe testbed composed of peers distributed in different places in Europe.
Vessaz F., Garbinato B. (Dir.) (2013). System-level Support for Mobile Ad hoc Communications: an Algorithmic & Practical Approach. Université de Lausanne, Faculté des hautes études commerciales. [pdf] [abstract]
A mobile ad hoc network (MANET) is a decentralized and infrastructure-less network. This thesis aims to provide support at the system-level for developers of applications or protocols in such networks. To do this, we propose contributions in both the algorithmic realm and in the practical realm. In the algorithmic realm, we contribute to the field by proposing different context-aware broadcast and multicast algorithms in MANETs, namely six-shot broadcast, six-shot multicast, PLAN-B and ageneric algorithmic approach to optimize the power consumption of existing algorithms. For each algorithm we propose, we compare it to existing algorithms that are either probabilistic or context-aware, and then we evaluate their performance based on simulations. We demonstrate that in some cases, context-aware information, such as location or signal-strength, can improve the effciency. In the practical realm, we propose a testbed framework, namely ManetLab, to implement and to deploy MANET-specific protocols, and to evaluate their performance. This testbed framework aims to increase the accuracy of performance evaluation compared to simulations, while keeping the ease of use offered by the simulators to reproduce a performance evaluation. By evaluating the performance of different probabilistic algorithms with ManetLab, we observe that both simulations and testbeds should be used in a complementary way. In addition to the above original contributions, we also provide two surveys about system-level support for ad hoc communications in order to establish a state of the art. The first is about existing broadcast algorithms and the second is about existing middleware solutions and the way they deal with privacy and especially with location privacy.¦-¦Un réseau mobile ad hoc (MANET) est un réseau avec une architecture décentralisée et sans infrastructure. Cette thèse vise à fournir un support adéquat, au niveau système, aux développeurs d'applications ou de protocoles dans de tels réseaux. Dans ce but, nous proposons des contributions à la fois dans le domaine de l'algorithmique et dans celui de la pratique. Nous contribuons au domaine algorithmique en proposant différents algorithmes de diffusion dans les MANETs, algorithmes qui sont sensibles au contexte, à savoir six-shot broadcast,six-shot multicast, PLAN-B ainsi qu'une approche générique permettant d'optimiser la consommation d'énergie de ces algorithmes. Pour chaque algorithme que nous proposons, nous le comparons à des algorithmes existants qui sont soit probabilistes, soit sensibles au contexte, puis nous évaluons leurs performances sur la base de simulations. Nous montrons que, dans certains cas, des informations liées au contexte, telles que la localisation ou l'intensité du signal, peuvent améliorer l'efficience de ces algorithmes. Sur le plan pratique, nous proposons une plateforme logicielle pour la création de bancs d'essai, intitulé ManetLab, permettant d'implémenter, et de déployer des protocoles spécifiques aux MANETs, de sorte à évaluer leur performance. Cet outil logiciel vise à accroître la précision desévaluations de performance comparativement à celles fournies par des simulations, tout en conservant la facilité d'utilisation offerte par les simulateurs pour reproduire uneévaluation de performance. En évaluant les performances de différents algorithmes probabilistes avec ManetLab, nous observons que simulateurs et bancs d'essai doivent être utilisés de manière complémentaire. En plus de ces contributions principales, nous fournissons également deux états de l'art au sujet du support nécessaire pour les communications ad hoc. Le premier porte sur les algorithmes de diffusion existants et le second sur les solutions de type middleware existantes et la façon dont elles traitent de la confidentialité, en particulier celle de la localisation.
Allani M., Garbinato B. (Dir.) (2010). Tree-based message diffusion for managing replicated data in unreliable and resource-constrained peer-to-peer environment. Université de Lausanne, Faculté des hautes études commerciales. [abstract]
Abstract¦This thesis proposes a set of adaptive broadcast solutions and an adaptive data replication solution to support the deployment of P2P applications. P2P applications are an emerging type of distributed applications that are running on top of P2P networks. Typical P2P applications are video streaming, file sharing, etc.¦While interesting because they are fully distributed, P2P applications suffer from several deployment problems, due to the nature of the environment on which they perform. Indeed, defining an application on top of a P2P network often means defining an application where peers contribute resources in exchange for their ability to use the P2P application. For example, in P2P file sharing application, while the user is downloading some file, the P2P application is in parallel serving that file to other users. Such peers could have limited hardware resources, e.g., CPU, bandwidth and memory or the end-user could decide to limit the resources it dedicates to the P2P application a priori. In addition, a P2P network is typically emerged into an unreliable environment, where communication links and processes are subject to message losses and crashes, respectively.¦To support P2P applications, this thesis proposes a set of services that address some underlying constraints related to the nature of P2P networks. The proposed services include a set of adaptive broadcast solutions and an adaptive data replication solution that can be used as the basis of several P2P applications. Our data replication solution permits to increase availability and to reduce the communication overhead. The broadcast solutions aim, at providing a communication substrate encapsulating one of the key communication paradigms used by P2P applications: broadcast. Our broadcast solutions typically aim at offering reliability and scalability to some upper layer, be it an end-to-end P2P application or another system-level layer, such as a data replication layer.¦Our contributions are organized in a protocol stack made of three layers. In each layer, we propose a set of adaptive protocols that address specific constraints imposed by the environment. Each protocol is evaluated through a set of simulations. The adaptiveness aspect of our solutions relies on the fact that they take into account the constraints of the underlying system in a proactive manner.¦To model these constraints, we define an environment approximation algorithm allowing us to obtain an approximated view about the system or part of it. This approximated view includes the topology and the components reliability expressed in probabilistic terms.¦To adapt to the underlying system constraints, the proposed broadcast solutions route messages through tree overlays permitting to maximize the broadcast reliability. Here, the broadcast reliability is expressed as a function of the selected paths reliability and of the use of available resources. These resources are modeled in terms of quotas of messages translating the receiving and sending capacities at each node. To allow a deployment in a large-scale system, we take into account the available memory at processes by limiting the view they have to maintain about the system. Using this partial view, we propose three scalable broadcast algorithms, which are based on a propagation overlay that tends to the global tree overlay and adapts to some constraints of the underlying system.¦At a higher level, this thesis also proposes a data replication solution that is adaptive both in terms of replica placement and in terms of request routing. At the routing level, this solution takes the unreliability of the environment into account, in order to maximize reliable delivery of requests. At the replica placement level, the dynamically changing origin and frequency of read/write requests are analyzed, in order to define a set of replica that minimizes communication cost.
Holzer A., Garbinato B. (Dir.) (2009). Modular support for developing mobile ad hoc applications. Université de Lausanne, Faculté des hautes études commerciales. [abstract]
Abstract¦This PhD thesis addresses the issue of alleviating the burden of developing ad hoc applications. Such applications have the particularity of running on mobile devices, communicating in a peer-to-peer manner and implement some proximity-based semantics. A typical example of such application can be a radar application where users see their avatar as well as the avatars of their friends on a map on their mobile phone. Such application become increasingly popular with the advent of the latest generation of mobile smart phones with their impressive computational power, their peer-to-peer communication capabilities and their location detection technology. Unfortunately, the existing programming support for such applications is limited, hence the need to address this issue in order to alleviate their development burden.¦This thesis specifically tackles this problem by providing several tools for application development support. First, it provides the location-based publish/subscribe service (LPSS), a communication abstraction, which elegantly captures recurrent communication issues and thus allows to dramatically reduce the code complexity. LPSS is implemented in a modular manner in order to be able to target two different network architectures. One pragmatic implementation is aimed at mainstream infrastructure-based mobile networks, where mobile devices can communicate through fixed antennas. The other fully decentralized implementation targets emerging mobile ad hoc networks (MANETs), where no fixed infrastructure is available and communication can only occur in a peer-to-peer fashion. For each of these architectures, various implementation strategies tailored for different application scenarios that can be parametrized at deployment time. Second, this thesis provides two location-based message diffusion protocols, namely 6Shot broadcast and 6Shot multicast, specifically aimed at MANETs and fine tuned to be used as building blocks for LPSS. Finally this thesis proposes Phomo, a phone motion testing tool that allows to test proximity semantics of ad hoc applications without having to move around with mobile devices. These different developing support tools have been packaged in a coherent middleware framework called Pervaho.
Rickebusch I., Garbinato B. (Dir.) (2007). On solving fair exchange and related distributed problems in Byzantine environments. Université de Lausanne, Faculté des hautes études commerciales. [pdf] [abstract]
Abstract¦The solvability of the problem of fair exchange in a synchronous system subject to Byzantine failures is investigated in this work. The fair exchange problem arises when a group of processes are required to exchange digital items in a fair manner, which means that either each process obtains the item it was expecting or no process obtains any information on, the inputs of others.¦After introducing a novel specification of fair exchange that clearly separates safety and liveness, we give an overview of the difficulty of solving such a problem in the context of a fully-connected topology. On one hand, we show that no solution to fair exchange exists in the absence of an identified process that every process can trust a priori; on the other, a well-known solution to fair exchange relying on a trusted third party is recalled. These two results lead us to complete our system model with a flexible representation of the notion of trust. We then show that fair exchange is solvable if and only if a connectivity condition, named the reachable majority condition, is satisfied. The necessity of the condition is proven by an impossibility result and its sufficiency by presenting a general solution to fair exchange relying on a set of trusted processes.¦The focus is then turned towards a specific network topology in order to provide a fully decentralized, yet realistic, solution to fair exchange. The general solution mentioned above is optimized by reducing the computational load assumed by trusted processes as far as possible. Accordingly, our fair exchange protocol relies on trusted tamperproof modules that have limited communication abilities and are only required in key steps of the algorithm. This modular solution is then implemented in the context of a pedagogical application developed for illustrating and apprehending the complexity of fair exchange. This application, which also includes the implementation of a wide range of Byzantine behaviors, allows executions of the algorithm to be set up and monitored through a graphical display.¦Surprisingly, some of our results on fair exchange seem contradictory with those found in the literature of secure multiparty computation, a problem from the field of modern cryptography, although the two problems have much in common. Both problems are closely related to the notion of trusted third party, but their approaches and descriptions differ greatly. By introducing a common specification framework, a comparison is proposed in order to clarify their differences and the possible origins of the confusion between them. This leads us to introduce the problem of generalized fair computation, a generalization of fair exchange. Finally, a solution to this new problem is given by generalizing our modular solution to fair exchange
Garbinato B., André Schiper (Dir.) (1998). Protocol Objects & Patterns for Structuring Reliable Distributed Systems. EPFL. [doi] [url]