| 1. |
- Niazi, Salman, 1982-
(author)
-
Scaling Distributed Hierarchical File Systems Using NewSQL Databases
- 2018
-
Doctoral thesis (other academic/artistic)abstract
- For many years, researchers have investigated the use of database technology to manage file system metadata, with the goal of providing extensible typed metadata and support for fast, rich metadata search. However, earlier attempts failed mainly due to the reduced performance introduced by adding database operations to the file system’s critical path. Recent improvements in the performance of distributed in-memory online transaction processing databases (NewSQL databases) led us to re-investigate the possibility of using a database to manage file system metadata, but this time for a distributed, hierarchical file system, the Hadoop Distributed File System (HDFS). The single-host metadata service of HDFS is a well-known bottleneck for both the size of the HDFS clusters and their throughput.In this thesis, we detail the algorithms, techniques, and optimizations used to develop HopsFS, an open-source, next-generation distribution of the HDFS that replaces the main scalability bottleneck in HDFS, single node in-memory metadata service, with a no-shared state distributed system built on a NewSQL database. In particular, we discuss how we exploit recent high-performance features from NewSQL databases, such as application-defined partitioning, partition pruned index scans, and distribution aware transactions, as well as more traditional techniques such as batching and write-ahead caches, to enable a revolution in distributed hierarchical file system performance.HDFS’ design is optimized for the storage of large files, that is, files ranging from megabytes to terabytes in size. However, in many production deployments of the HDFS, it has been observed that almost 20% of the files in the system are less than 4 KB in size and as much as 42% of all the file system operations are performed on files less than 16 KB in size. HopsFS introduces a tiered storage solution to store files of different sizes more efficiently. The tiers range from the highest tier where an in-memory NewSQL database stores very small files (<1 KB), to the next tier where small files (<64 KB) are stored in solid-state-drives (SSDs), also using a NewSQL database, to the largest tier, the existing Hadoop block storage layer for very large files. Our approach is based on extending HopsFS with an inode stuffing technique, where we embed the contents of small files with the metadata and use database transactions and database replication guarantees to ensure the availability, integrity, and consistency of the small files. HopsFS enables significantly larger cluster sizes, more than an order of magnitude higher throughput, and significantly lower client latencies for large clusters.Lastly, coordination is an integral part of the distributed file system operations protocols. We present a novel leader election protocol for partially synchronous systems that uses NewSQL databases as shared memory. Our work enables HopsFS, that uses a NewSQL database to save the operational overhead of managing an additional third-party service for leader election and deliver performance comparable to a leader election implementation using a state-of-the-art distributed coordination service, ZooKeeper.
|
|
| 2. |
- Aberer, Karl, et al.
(author)
-
The Essence of P2P : A Reference Architecture for Overlay Networks
- 2005
-
In: Fifth IEEE International Conference on Peer-to-Peer Computing, Proceedings. - 0769523765 ; , s. 11-20
-
Conference paper (peer-reviewed)abstract
- The success of the P2P idea has created a huge diversity of approaches, among which overlay networks, for example, Gnutella, Kazaa, Chord, Pastry, Tapestry, P-Grid, or DKS, have received specific attention from both developers and researchers. A wide variety of algorithms, data structures, and architectures have been proposed. The terminologies and abstractions used, however have become quite inconsistent since the P2P paradigm has attracted people from many different communities, e.g., networking, databases, distributed systems, graph theory, complexity theory, biology, etc. In this paper we propose a reference model for overlay networks which is capable of modeling different approaches in this domain in a generic manner It is intended to allow researchers and users to assess the properties of concrete systems, to establish a common vocabulary for scientific discussion, to facilitate the qualitative comparison of the systems, and to serve as the basis for defining a standardized API to make overlay networks interoperable.
|
|
| 3. |
- Al-Shishtawy, Ahmad, et al.
(author)
-
A design methodology for self-management in distributed environments
- 2009
-
In: IEEE International conference on Computational Science and Engineering. - 9780769538235 ; , s. 430-436
-
Conference paper (peer-reviewed)abstract
- Autonomic computing is a paradigm that aims at reducing administrative overhead by providing autonomic managers to make applications selfmanaging. In order to better deal with dynamic environments, for improved performance and scalability, we advocate for distribution of management functions among several cooperative managers that coordinate their activities in order to achieve management objectives. We present a methodology for designing the management part of a distributed self-managing application in a distributed manner. We define design steps, that includes partitioning of management functions and orchestration of multiple autonomic managers. We illustrate the proposed design methodology by applying it to design and development of a distributed storage service as a case study. The storage service prototype has been developed using the distributing component management system Niche. Distribution of autonomic managers allows distributing the management overhead and increased management performance due to concurrency and better locality.
|
|
| 4. |
- Al-Shishtawy, Ahmad, 1978-
(author)
-
Enabling and Achieving Self-Management for Large Scale Distributed Systems : Platform and Design Methodology for Self-Management
- 2010
-
Licentiate thesis (other academic/artistic)abstract
- Autonomic computing is a paradigm that aims at reducing administrative overhead by using autonomic managers to make applications self-managing. To better deal with large-scale dynamic environments; and to improve scalability, robustness, and performance; we advocate for distribution of management functions among several cooperative autonomic managers that coordinate their activities in order to achieve management objectives. Programming autonomic management in turn requires programming environment support and higher level abstractions to become feasible. In this thesis we present an introductory part and a number of papers that summaries our work in the area of autonomic computing. We focus on enabling and achieving self-management for large scale and/or dynamic distributed applications. We start by presenting our platform, called Niche, for programming self-managing component-based distributed applications. Niche supports a network-transparent view of system architecture simplifying designing application self-* code. Niche provides a concise and expressive API for self-* code. The implementation of the framework relies on scalability and robustness of structured overlay networks. We have also developed a distributed file storage service, called YASS, to illustrate and evaluate Niche. After introducing Niche we proceed by presenting a methodology and design space for designing the management part of a distributed self-managing application in a distributed manner. We define design steps, that includes partitioning of management functions and orchestration of multiple autonomic managers. We illustrate the proposed design methodology by applying it to the design and development of an improved version of our distributed storage service YASS as a case study. We continue by presenting a generic policy-based management framework which has been integrated into Niche. Policies are sets of rules that govern the system behaviors and reflect the business goals or system management objectives. The policy based management is introduced to simplify the management and reduce the overhead, by setting up policies to govern system behaviors. A prototype of the framework is presented and two generic policy languages (policy engines and corresponding APIs), namely SPL and XACML, are evaluated using our self-managing file storage application YASS as a case study. Finally, we present a generic approach to achieve robust services that is based on finite state machine replication with dynamic reconfiguration of replica sets. We contribute a decentralized algorithm that maintains the set of resource hosting service replicas in the presence of churn. We use this approach to implement robust management elements as robust services that can operate despite of churn.
|
|
| 5. |
- Al-Shishtawy, Ahmad, 1978-
(author)
-
Self-Management for Large-Scale Distributed Systems
- 2012
-
Doctoral thesis (other academic/artistic)abstract
- Autonomic computing aims at making computing systems self-managing by using autonomic managers in order to reduce obstacles caused by management complexity. This thesis presents results of research on self-management for large-scale distributed systems. This research was motivated by the increasing complexity of computing systems and their management.In the first part, we present our platform, called Niche, for programming self-managing component-based distributed applications. In our work on Niche, we have faced and addressed the following four challenges in achieving self-management in a dynamic environment characterized by volatile resources and high churn: resource discovery, robust and efficient sensing and actuation, management bottleneck, and scale. We present results of our research on addressing the above challenges. Niche implements the autonomic computing architecture, proposed by IBM, in a fully decentralized way. Niche supports a network-transparent view of the system architecture simplifying the design of distributed self-management. Niche provides a concise and expressive API for self-management. The implementation of the platform relies on the scalability and robustness of structured overlay networks. We proceed by presenting a methodology for designing the management part of a distributed self-managing application. We define design steps that include partitioning of management functions and orchestration of multiple autonomic managers.In the second part, we discuss robustness of management and data consistency, which are necessary in a distributed system. Dealing with the effect of churn on management increases the complexity of the management logic and thus makes its development time consuming and error prone. We propose the abstraction of Robust Management Elements, which are able to heal themselves under continuous churn. Our approach is based on replicating a management element using finite state machine replication with a reconfigurable replica set. Our algorithm automates the reconfiguration (migration) of the replica set in order to tolerate continuous churn. For data consistency, we propose a majority-based distributed key-value store supporting multiple consistency levels that is based on a peer-to-peer network. The store enables the tradeoff between high availability and data consistency. Using majority allows avoiding potential drawbacks of a master-based consistency control, namely, a single-point of failure and a potential performance bottleneck.In the third part, we investigate self-management for Cloud-based storage systems with the focus on elasticity control using elements of control theory and machine learning. We have conducted research on a number of different designs of an elasticity controller, including a State-Space feedback controller and a controller that combines feedback and feedforward control. We describe our experience in designing an elasticity controller for a Cloud-based key-value store using state-space model that enables to trade-off performance for cost. We describe the steps in designing an elasticity controller. We continue by presenting the design and evaluation of ElastMan, an elasticity controller for Cloud-based elastic key-value stores that combines feedforward and feedback control.
|
|
| 6. |
- Ali, Khayri Mohammed, et al.
(author)
-
Global garbage collection for distributed heap storage systems
- 1987. - 1
-
Reports (other academic/artistic)abstract
- We present a garbage-collection algorithm, suitable for loosely-coupled multiprocessor systems, in which the processing elements (PE's) share only the communication medium. The algorithm is global, i.e. it involves all the PE's in the system. It allows space compaction, and it uses a system-wide marking phase to mark all accessible objects where a combination of parallel breadth-first/depth-first strategies is used for tracing the object-graphs according to a decentralized credit mechanism that regulates the number of garbage collection messages in the system. The credit mechanism is crucial for determining the space requirement of the garbage-collection messages. Also a variation of the above algorithm is presented for systems with high locality of reference. It allows each PE to perform first its local garbage collection and only invokes the global garbage collection when the freed space by the local collector is insufficient.
|
|
| 7. |
- Alima, Luc Onana, et al.
(author)
-
A Framework for Structured Peer-to-Peer Overlay Networks
- 2004. - 1
-
Reports (other academic/artistic)abstract
- Structured peer-to-peer overlay networks have recently emerged as good candidate infrastructure for building novel large-scale and robust Internet applications in which participating peers share computing resources as equals. In the past three year, various structured peer-to-peer overlay networks have been proposed, and probably more are to come. We present a framework for understanding, analyzing and designing structured peer-to-peer overlay networks. The main objective of the paper is to provide practical guidelines for the design of structured overlay networks by identifying a fundamental element in the construction of overlay networks: the embedding of k-ary trees. Then, a number of effective techniques for maintaining these overlay networks are discussed. The proposed framework has been effective in the development of the DKS system.
|
|
| 8. |
|
|
| 9. |
- Almgren, Jonas, et al.
(author)
-
SICStus Prolog library manual, version 2.1 #8
- 1993. - 1
-
Reports (other academic/artistic)abstract
- This Manual corresponds to SICStus Prolog release 2.1. #8 The Prolog library comprises a number of packages which are thought to be useful in a number of applications. Note that the predicates in the Prolog library are built-in predicates. One has to explicity load each package to get access to its predicates. To load a library package Package, you will normally enter a query. I ?- use_module(library(Package)). Library packages may be compiled and consulted as well as loaded.
|
|
| 10. |
- Alsayfi, Majed S., et al.
(author)
-
Big Data in Vehicular Cloud Computing : Review, Taxonomy, and Security Challenges
- 2022
-
In: ELEKTRONIKA IR ELEKTROTECHNIKA. - : Kaunas University of Technology (KTU). - 1392-1215 .- 2029-5731. ; 28:2, s. 59-71
-
Research review (peer-reviewed)abstract
- Modern vehicles equipped with various smart sensors have become a means of transportation and have become a means of collecting, creating, computing, processing, and transferring data while traveling through modern and rural cities. A traditional vehicular ad hoc network (VANET) cannot handle the enormous and complex data that are collected by modern vehicle sensors (e.g., cameras, lidar, and global positioning systems (GPS)) because they require rapid processing, analysis, management, storage, and uploading to trusted national authorities. Furthermore, the integrated VANET with cloud computing presents a new concept, vehicular cloud computing (VCC), which overcomes the limitations of VANET, brings new services and applications to vehicular networks, and generates a massive amount of data compared to the data collected by individual vehicles alone. Therefore, this study explored the importance of big data in VCC. First, we provide an overview of traditional vehicular networks and their limitations. Then we investigate the relationship between VCC and big data, fundamentally focusing on how VCC can generate, transmit, store, upload, and process big data to share it among vehicles on the road. Subsequently, a new taxonomy of big data in VCC was presented. Finally, the security challenges in big data-based VCCs are discussed.
|
|
| 11. |
- Alsayfi, Majed S., et al.
(author)
-
Securing Real-Time Video Surveillance Data in Vehicular Cloud Computing : A Survey
- 2022
-
In: IEEE Access. - : Institute of Electrical and Electronics Engineers (IEEE). - 2169-3536. ; 10, s. 51525-51547
-
Journal article (peer-reviewed)abstract
- Vehicular ad hoc networks (VANETs) have received a great amount of interest, especially in wireless communications technology. In VANETs, vehicles are equipped with various intelligent sensors that can collect real-time data from inside and from surrounding vehicles. These real-time data require powerful computation, processing, and storage. However, VANETs cannot manage these real-time data because of the limited storage capacity in on board unit (OBU). To address this limitation, a new concept is proposed in which a VANET is integrated with cloud computing to form vehicular cloud computing (VCC) technology. VCC can manage real-time services, such as real-time video surveillance data that are used for monitoring critical events on the road. These real-time video surveillance data include highly sensitive data that should be protected against intruders in the networks because any manipulation, alteration, or sniffing of data will affect a driver's life by causing improper decision-making. The security and privacy of real-time video surveillance data are major challenges in VCC. Therefore, this study reviewed the importance of the security and privacy of real-time video data in VCC. First, we provide an overview of VANETs and their limitations. Second, we provide a state-of-the-art taxonomy for real-time video data in VCC. Then, the importance of real-time video surveillance data in both fifth generation (5G), and sixth generation (6G) networks is presented. Finally, the challenges and open issues of real-time video data in VCC are discussed.
|
|
| 12. |
- Appleby, Karen, et al.
(author)
-
Garbage Collection for Prolog Based on WAM (Revised version)
- 1986. - 1
-
Reports (other academic/artistic)abstract
- Warren Abstract Machine (WAM) has become a generally accepted standard Prolog implementation technique. Garbage collection is an important aspect in the implementation of any Prolog system. We first present a synopsis of the WAM and then show marking and compaction algorithms that take advantage of WAM's unique use of the data areas. Marking and compaction are performed on both the heap and the trail. The marking and compaction algorithms use pointer reversal techniques, which obviate the need for extra stack space. However, two bits for every pointer on the heap are reserved for the garbage collection algorithm. The algorithm can work on segments of the heap, which may lead to a significant reduction of the total garbage collection time. The time of the algorithms are linear in the size of the areas.
|
|
| 13. |
|
|
| 14. |
|
|
| 15. |
- Arad, Cosmin, et al.
(author)
-
Building and Evaluating P2P Systems using the Kompics Component Framework
- 2009
-
In: 2009 IEEE NINTH INTERNATIONAL CONFERENCE ON PEER-TO-PEER COMPUTING (P2P 2009). - NEW YORK : IEEE. - 9781424450664 ; , s. 93-94
-
Conference paper (peer-reviewed)abstract
- We present a framework for building and evaluating P2P systems in simulation, local execution, and distributed deployment. Such uniform system evaluations increase confidence in the obtained results. We briefly introduce the Kompics component model and its P2P framework. We describe the component architecture of a Kompics P2P system and show how to define experiment scenarios for large dynamic systems. The same experiments are conducted in reproducible simulation, in real-time execution on a single machine, and distributed over a local cluster or a wide area network. This demonstration shows the component oriented design and the evaluation of two P2P systems implemented in Kompics: Chord and Cyclon. We simulate the systems and then we execute them in real time. During real-time execution we monitor the dynamic behavior of the systems and interact with them through their web-based interfaces. We demonstrate how component-oriented design enables seamless switching between alternative protocols.
|
|
| 16. |
- Arad, Cosmin, et al.
(author)
-
CATS: linearizability and partition tolerance in scalable and self-organizing key-value stores
- 2012. - 7
-
Reports (other academic/artistic)abstract
- Distributed key-value stores provide scalable, fault-tolerant, and self-organizing storage services, but fall short of guaranteeing linearizable consistency in partially synchronous, lossy, partitionable, and dynamic networks, when data is distributed and replicated automatically by the principle of consistent hashing. This paper introduces consistent quorums as a solution for achieving atomic consistency. We present the design and implementation of CATS, a distributed key-value store which uses consistent quorums to guarantee linearizability and partition tolerance in such adverse and dynamic network conditions. CATS is scalable, elastic, and self-organizing; key properties for modern cloud storage middleware. Our system shows that consistency can be achieved with practical performance and modest throughput overhead (5%) for read-intensive workloads.
|
|
| 17. |
- Arad, Cosmin, et al.
(author)
-
GODS: Global Observatory for Distributed Systems
- 2007. - 1
-
Reports (other academic/artistic)abstract
- We propose GODS, an ecosystem for the evaluation and study of world-wide distributed and dynamic systems under a realistic emulated network environment. GODS allows the evaluation of a system's actual implementation in reproducible experiments, collecting global knowledge about the system state. Furthermore, GODS addresses the problems of debugging distributed algorithms, performance tuning, measuring bandwidth consumption, regression testing, and benchmarking similar systems, thus offering a complete evaluation environment for distributed applications. Our framework uses ModelNet for the network emulation and enhances that by (1) adding dynamism by varying link properties, partitioning the network and emulating churn, (2) offering global knowledge about the observed system by gathering statistics and events and (3) enabling the user to easily deploy, manage and monitor complex, large-scale distributed systems.
|
|
| 18. |
- Arad, Cosmin Ionel, 1981-
(author)
-
Programming Model and Protocols for Reconfigurable Distributed Systems
- 2013
-
Doctoral thesis (other academic/artistic)abstract
- Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand.This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for largescale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle.We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework.Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics.
|
|
| 19. |
- Arad, Cosmin, et al.
(author)
-
Kompics: a message-passing component model for building distributed systems
- 2010. - 7
-
Reports (other academic/artistic)abstract
- The Kompics component model and programming framework was designedto simplify the development of increasingly complex distributed systems. Systems built with Kompics leverage multi-core machines out of the box and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic debugging and reproducible performance evaluation of unmodified Kompics distributed systems. We describe the component model and show how to program and compose event-based distributed systems. We present the architectural patterns and abstractions that Kompics facilitates and we highlight a case study of a complex distributed middleware that we have built with Kompics. We show how our approach enables systematic development and evaluation of large-scale and dynamic distributed systems.
|
|
| 20. |
- Arad, Cosmin, et al.
(author)
-
Message-Passing Concurrency for Scalable, Stateful, Reconfigurable Middleware
- 2012
-
In: Middleware 2012. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642351693 ; , s. 208-228
-
Conference paper (peer-reviewed)abstract
- Message-passing concurrency (MPC) is increasingly being used to build systems software that scales well on multi-core hardware. Functional programming implementations of MPC, such as Erlang, have also leveraged their stateless nature to build middleware that is not just scalable, but also dynamically reconfigurable. However, many middleware platforms lend themselves more naturally to a stateful programming model, supporting session and application state. A limitation of existing programming models and frameworks that support dynamic reconfiguration for stateful middleware, such as component frameworks, is that they are not designed for MPC.In this paper, we present Kompics, a component model and programming framework, that supports the construction and composition of dynamically reconfigurable middleware using stateful, concurrent, message-passing components. An added benefit of our approach is that by decoupling our component execution model, we can run the same code in both simulation and production environments. We present the architectural patterns and abstractions that Kompics facilitates and we evaluate them using a case study of a non-trivial key-value store that we built using Kompics. We show how our model enables the systematic development and testing of scalable, dynamically reconfigurable middleware.
|
|
| 21. |
- Arad, Cosmin, et al.
(author)
-
Practical Protocol Composition, Encapsulation and Sharing in Kompics
- 2008
-
In: SASOW 2008. - LOS ALAMITOS : IEEE COMPUTER SOC. - 9781424434688 ; , s. 266-271
-
Conference paper (peer-reviewed)abstract
- At the core of any distributed system is a set of concurrent distributed algorithms that coordinate the functionality of the distributed system. We present a software architecture, Kompics that is component-based and compositional which facilitates building distributed protocols. The underlying computation model subsumes that of event-based systems, SEDA (staged event-driven architecture.) and thread-based models. We illustrate various salient features of Kompics such as ease of use, compositionality and configurability through a series of well chosen distributed protocols.
|
|
| 22. |
- Ardelius, John, 1978-
(author)
-
On the Performance Analysis of Large Scale, Dynamic, Distributed and Parallel Systems.
- 2013
-
Doctoral thesis (other academic/artistic)abstract
- Evaluating the performance of large distributed applications is an important and non-trivial task. With the onset of Internet wide applications there is an increasing need to quantify reliability, dependability and performance of these systems, both as a guide in system design as well as a means to understand the fundamental properties of large-scale distributed systems. Previous research has mainly focused on either formalised models where system properties can be deduced and verified using rigorous mathematics or on measurements and experiments on deployed applications. Our aim in this thesis is to study models on an abstraction level lying between the two ends of this spectrum. We adopt a model of distributed systems inspired by methods used in the study of large scale system of particles in physics and model the application nodes as a set of interacting particles each with an internal state whose actions are specified by the application program. We apply our modeling and performance evaluation methodology to four different distributed and parallel systems. The first system is the distributed hash table (DHT) Chord running in a dynamic environment. We study the system under two scenarios. First we study how performance (in terms of lookup latency) is affectedon a network with finite communication latency. We show that an average delay in conjunction with other parameters describing changes in the network (such as timescales for network repair and join and leave processes)induces fundamentally different system performance. We also verify our analytical predictions via simulations.In the second scenario we introduce network address translators (NATs) to the network model. This makes the overlay topology non-transitive and we explore the implications of this fact to various performance metrics such as lookup latency, consistency and load balance. The latter analysis is mainly simulation based.Even though these two studies focus on a specific DHT, many of our results can easily be translated to other similar ring-based DHTs with long-range links, and the same methodology can be applied evento DHT's based on other geometries.The second type of system studied is an unstructured gossip protocol running a distributed version of the famous Belman-Ford algorithm. The algorithm, called GAP, generates a spanning tree over the participating nodes and the question we set out to study is how reliable this structure is(in terms of generating accurate aggregate values at the root) in the presence of node churn. All our analytical results are also verified using simulations.The third system studied is a content distribution network (CDN) of interconnected caches in an aggregation access network. In this model, content which sits at the leaves of the cache hierarchy tree, is requested by end users. Requests can then either be served by the first cache level or sent further up the tree. We study the performance of the whole system under two cache eviction policies namely LRU and LFU. We compare our analytical results with traces from related caching systems.The last system is a work stealing heuristic for task distribution in the TileraPro64 chip. This system has access to a shared memory and is therefore classified as a parallel system. We create a model for the dynamic generation of tasks as well as how they are executed and distributed among the participating nodes. We study how the heuristic scales when the number of nodes exceeds the number of processors on the chip as well as how different work stealing policies compare with each other. The work on this model is mainly simulation-based.
|
|
| 23. |
- Basloom, Huda, et al.
(author)
-
A Parallel Hybrid Testing Technique for Tri-Programming Model-Based Software Systems
- 2023
-
In: Computers, Materials and Continua. - : Computers, Materials and Continua (Tech Science Press). - 1546-2218 .- 1546-2226. ; 74:2, s. 4501-4530
-
Journal article (peer-reviewed)abstract
- Recently, researchers have shown increasing interest in combining more than one programming model into systems running on high performance computing systems (HPCs) to achieve exascale by applying parallelism at multiple levels. Combining different programming paradigms, such as Message Passing Interface (MPI), Open Multiple Processing (OpenMP), and Open Accelerators (OpenACC), can increase computation speed and improve performance. During the integration of multiple models, the probability of runtime errors increases, making their detection difficult, especially in the absence of testing techniques that can detect these errors. Numerous studies have been conducted to identify these errors, but no technique exists for detecting errors in three-level programming models. Despite the increasing research that integrates the three programming models, MPI, OpenMP, and OpenACC, a testing technology to detect runtime errors, such as deadlocks and race conditions, which can arise from this integration has not been developed. Therefore, this paper begins with a definition and explanation of runtime errors that result fromintegrating the three programming models that compilers cannot detect. For the first time, this paper presents a classification of operational errors that can result from the integration of the three models. This paper also proposes a parallel hybrid testing technique for detecting runtime errors in systems built in the C++ programming language that uses the triple programming models MPI, OpenMP, and OpenACC. This hybrid technology combines static technology and dynamic technology, given that some errors can be detected using static techniques, whereas others can be detected using dynamic technology. The hybrid technique can detect more errors because it combines two distinct technologies. The proposed static technology detects a wide range of error types in less time, whereas a portion of the potential errors that may or may not occur depending on the operating environment are left to the dynamic technology, which completes the validation.
|
|
| 24. |
- Basloom, Huda Saleh, et al.
(author)
-
Errors Classification and Static Detection Techniques for Dual-Programming Model (OpenMP and OpenACC)
- 2022
-
In: IEEE Access. - : Institute of Electrical and Electronics Engineers (IEEE). - 2169-3536. ; 10, s. 117808-117826
-
Journal article (peer-reviewed)abstract
- Recently, incorporating more than one programming model into a system designed for high performance computing (HPC) has become a popular solution to implementing parallel systems. Since traditional programming languages, such as C, C++, and Fortran, do not support parallelism at the level of multi-core processors and accelerators, many programmers add one or more programming models to achieve parallelism and accelerate computation efficiently. These models include Open Accelerators (OpenACC) and Open Multi-Processing (OpenMP), which have recently been used with various models, including Message Passing Interface (MPI) and Compute Unified Device Architecture (CUDA). Due to the difficulty of predicting the behavior of threads, runtime errors cannot be predicted. The compiler cannot identify runtime errors such as data races, race conditions, deadlocks, or livelocks. Many studies have been conducted on the development of testing tools to detect runtime errors when using programming models, such as the combinations of OpenACC with MPI models and OpenMP with MPI. Although more applications use OpenACC and OpenMP together, no testing tools have been developed to test these applications to date. This paper presents a testing tool for detecting runtime using a static testing technique. This tool can detect actual and potential runtime errors during the integration of the OpenACC and OpenMP models into systems developed in C++. This tool implement error dependency graphs, which are proposed in this paper. Additionally, a dependency graph of the errors is provided, along with a classification of runtime errors that result from combining the two programming models mentioned earlier.
|
|
| 25. |
- Bordencea, D., et al.
(author)
-
Efficient linearizable write operations using bounded global time uncertainty
- 2013
-
In: Proceedings - 2013 IEEE 12th International Symposium on Parallel and Distributed Computing, ISPDC 2013. - : IEEE. - 9780769550183 ; , s. 59-66
-
Conference paper (peer-reviewed)abstract
- Distributed key-value stores employed in data centers treat each key-value pair as a shared memory register. For fault-tolerance and performance, each key-value pair is replicated. Various models exist for the consistency of data amongst the replicas. While atomic consistency, also known as linearizability, provides the strongest form of consistency for read and write operations, various key-value stores, such as Cassandra, and Dynamo, offer only eventual consistency instead. One main motivation for such a decision is performance degradation when guaranteeing atomic consistency. In this paper, we use time with known bounded uncertainty to improve the performance of write operations, while maintaining atomic consistency. We show how to use the concept of commit wait in a shared memory register to perform a write operation in one phase (message round trip), instead of two. We evaluate the solution experimentally by comparing it to ABD, a well-known algorithm for achieving atomic consistency in an asynchronous network, which uses two phases for write operations. We also compare our protocol to an eventually consistent register. Our experiments show an improved throughput, and lower write latency, compared to the ABD algorithm.
|
|
| 26. |
- Brand, Per, et al.
(author)
-
A platform for constructing virtual spaces
- 1998. - 1
-
Conference paper (peer-reviewed)abstract
- Virtual spaces (worlds) applications are among the most complex of distributed applications. They are both distributed and open. Minimizing network latency, fault-tolerance, persistence, resource control, and security are also important aspects. Designing and implementing virtual spaces is currently difficult in that the already not insignificant complexities of program functionality, distribution, openness, and efficiency are interwound and cannot be tackled separately. We present a distributed programming language, distributed-Oz, that greatly reduces the complexity of distributed programming by clearly separating the different aspects of distributed programming. The design and implementation of distributed-Oz is ongoing work, but considerable progress has been made. The current prototype demonstrates network transparency, that computations behave the same way regardless of how the computation is partitioned between different sites. This is the basis for realizing clean separation of the functionality aspect from other aspects. Network awareness allows the programmer to predict and control network communication patterns. The current system gives the programmer the means to tackle separately the aspects of openness, efficiency (minimizing latency), distribution, and functionality. We have extended distributed-Oz with a tool for graphics in a distributed setting. This extends the idea of network transparency and network awareness to graphics. From the programmers point of view graphics programming for a multi-user application is virtually the same as programming for a single-user application. The differences are necessary extensions for achieving network and site awareness, such as visualization control (deciding which users should see what). Finally we consider virtual space applications, and propose a number of abstractions for use by developers of virtual spaces, relating them to the properties of distributed-Oz upon which they are based.
|
|
| 27. |
- Brand, Per, 1952-
(author)
-
The design philosophy of distributed programming systems : the Mozart experience
- 2005
-
Doctoral thesis (other academic/artistic)abstract
- Distributed programming is usually considered both difficult and inherently different from concurrent centralized programming. It is thought that the distributed programming systems that we ultimately deploy, in the future, when we've worked out all the details, will require a very different programming model and will even need to be evaluated by new criteria. The Mozart Programming System, described in this thesis, demonstrates that this need not be the case. It is shown that, with a good system design, distributed programming can be seen as an extended form of concurrent programming. This is from the programmer's point-of-view; under the hood the design and implementation will necessarily be more complex. We relate the Mozart system with the classical transparencies of distributed systems. We show that some of these are inherently on the application level, while as Mozart demonstrates, others can and should be dealt with on the language/system level. The extensions to the programming model, given the right concurrent programming base, are mainly concerned with non-functional properties of programs. The models and tuning facilities for failure and performance need to take latency, bandwidth, and partial failure into account. Other than that there need not be any difference between concurrent programming and distributed programming. The Mozart Programming System is based on the concurrent programming language Oz, which integrates, in a coherent way, all three known concurrency or thread-interaction models. These are message-passing (like Erlang), shared objects (like Java with threads) and shared data-flow variables. The Mozart design philosophy is thus applicable over the entire range of concurrent programming languages/systems. We have extracted from the experience with Mozart a number of principles and properties that are applicable to the design and implementation of all (general-purpose) distributed programming systems. The full range of the design and implementation issues behind Mozart are presented. This includes a description of the consistency protocols that make transparency possible for the full language, including distributed objects and distributed data-flow variables. Mozart is extensively compared with other approaches to distributed programming, in general, and to other language-based distributed programming systems, in particular
|
|
| 28. |
|
|
| 29. |
- Carbone, Paris, et al.
(author)
-
Cutty : Aggregate Sharing for User-Defined Windows
- 2016
-
In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450340731 ; , s. 1201-1210
-
Conference paper (peer-reviewed)abstract
- Aggregation queries on data streams are evaluated over evolving and often overlapping logical views called windows. While the aggregation of periodic windows were extensively studied in the past through the use of aggregate sharing techniques such as Panes and Pairs, little to no work has been put in optimizing the aggregation of very common, non-periodic windows. Typical examples of non-periodic windows are punctuations and sessions which can implement complex business logic and are often expressed as user-defined operators on platforms such as Google Dataflow or Apache Storm. The aggregation of such non-periodic or user-defined windows either falls back to expensive, best-effort aggregate sharing methods, or is not optimized at all.In this paper we present a technique to perform efficient aggregate sharing for data stream windows, which are declared as user-defined functions (UDFs) and can contain arbitrary business logic. To this end, we first introduce the concept of User-Defined Windows (UDWs), a simple, UDF-based programming abstraction that allows users to programmatically define custom windows. We then define semantics for UDWs, based on which we design Cutty, a low-cost aggregate sharing technique. Cutty improves and outperforms the state of the art for aggregate sharing on single and multiple queries. Moreover, it enables aggregate sharing for a broad class of non-periodic UDWs. We implemented our techniques on Apache Flink, an open source stream processing system, and performed experiments demonstrating orders of magnitude of reduction in aggregation costs compared to the state of the art.
|
|
| 30. |
- Carbone, Paris, et al.
(author)
-
Large-scale data stream processing systems
- 2017
-
In: Handbook of Big Data Technologies. - Cham : Springer International Publishing. - 9783319493404 - 9783319493398 ; , s. 219-260
-
Book chapter (other academic/artistic)abstract
- In our data-centric society, online services, decision making, and other aspects are increasingly becoming heavily dependent on trends and patterns extracted from data. A broad class of societal-scale data management problems requires system support for processing unbounded data with low latency and high throughput. Large-scale data stream processing systems perceive data as infinite streams and are designed to satisfy such requirements. They have further evolved substantially both in terms of expressive programming model support and also efficient and durable runtime execution on commodity clusters. Expressive programming models offer convenient ways to declare continuous data properties and applied computations, while hiding details on how these data streams are physically processed and orchestrated in a distributed environment. Execution engines provide a runtime for such models further allowing for scalable yet durable execution of any declared computation. In this chapter we introduce the major design aspects of large scale data stream processing systems, covering programming model abstraction levels and runtime concerns. We then present a detailed case study on stateful stream processing with Apache Flink, an open-source stream processor that is used for a wide variety of processing tasks. Finally, we address the main challenges of disruptive applications that large-scale data streaming enables from a systemic point of view.
|
|
| 31. |
- Carbone, Paris, 1986-, et al.
(author)
-
Lightweight Asynchronous Snapshots for Distributed Dataflows
- 2015
-
Reports (other academic/artistic)abstract
- Distributed stateful stream processing enables the deployment and execution of large scale continuous computations in the cloud, targeting both low latency and high throughput. One of the most fundamental challenges of this paradigm is providing processing guarantees under potential failures. Existing approaches rely on periodic global state snapshots that can be used for failure recovery. Those approaches suffer from two main drawbacks. First, they often stall the overall computation which impacts ingestion. Second, they eagerly persist all records in transit along with the operation states which results in larger snapshots than required. In this work we propose Asynchronous Barrier Snapshotting (ABS), a lightweight algorithm suited for modern dataflow execution engines that minimises space requirements. ABS persists only operator states on acyclic execution topologies while keeping a minimal record log on cyclic dataflows. We implemented ABS on Apache Flink, a distributed analytics engine that supports stateful stream processing. Our evaluation shows that our algorithm does not have a heavy impact on the execution, maintaining linear scalability and performing well with frequent snapshots.
|
|
| 32. |
- Carbone, Paris, 1986-
(author)
-
Scalable and Reliable Data Stream Processing
- 2018
-
Doctoral thesis (other academic/artistic)abstract
- Data-stream management systems have for long been considered as a promising architecture for fast data management. The stream processing paradigm poses an attractive means of declaring persistent application logic coupled with state over evolving data. However, despite contributions in programming semantics addressing certain aspects of data streaming, existing approaches have been lacking a clear, universal specification for the underlying system execution. We investigate the case of data stream processing as a general-purpose scalable computing architecture that can support continuous and iterative state-driven workloads. Furthermore, we examine how this architecture can enable the composition of reliable, reconfigurable services and complex applications that go even beyond the needs of scalable data analytics, a major trend in the past decade.In this dissertation, we specify a set of core components and mechanisms to compose reliable data stream processing systems while adopting three crucial design principles: blocking-coordination avoidance, programming-model transparency, and compositionality. Furthermore, we identify the core open challenges among the academic and industrial state of the art and provide a complete solution using these design principles as a guide. Our contributions address the following problems: I) Reliable Execution and Stream State Management, II) Computation Sharing and Semantics for Stream Windows, and III) Iterative Data Streaming. Several parts of this work have been integrated into Apache Flink, a widely-used, open-source scalable computing framework, and supported the deployment of hundreds of long-running large-scale production pipelines worldwide.
|
|
| 33. |
- Carbone, Paris, et al.
(author)
-
State Management in Apache Flink : Consistent Stateful Distributed Stream Processing
- 2017
-
In: Proceedings of the VLDB Endowment. - : ACM Digital Library. - 2150-8097. ; 10, s. 1718-1729
-
Journal article (peer-reviewed)abstract
- Stream processors are emerging in industry as an apparatus that drives analytical but also mission critical services handling the core of persistent application logic. Thus, apart from scalability and low-latency, a rising system need is first-class support for application state together with strong consistency guarantees, and adaptivity to cluster reconfigurations, software patches and partial failures. Although prior systems research has addressed some of these specific problems, the practical challenge lies on how such guarantees can be materialized in a transparent, non-intrusive manner that relieves the user from unnecessary constraints. Such needs served as the main design principles of state management in Apache Flink, an open source, scalable stream processor.We present Flink’s core pipelined, in-flight mechanism which guarantees the creation of lightweight, consistent, distributed snapshots of application state, progressively, without impacting continuous execution. Consistent snapshots cover all needs for system reconfiguration, fault tolerance and version management through coarse grained rollback recovery. Application state is declared explicitly to the system, allowing efficient partitioning and transparent commits to persistent storage. We further present Flink’s backend implementations and mechanisms for high availability, external state queries and output commit. Finally, we demonstrate how these mechanisms behave in practice with metrics and large deployment insights exhibiting the low performance trade-offs of our approach and the general benefits of exploiting asynchrony in continuous, yet sustainable system deployments.
|
|
| 34. |
|
|
| 35. |
|
|
| 36. |
- Dowling, Jim, et al.
(author)
-
Developing a Distributed Electronic Health-Record Store for India
- 2008
-
In: ERCIM News. - 0926-4981 .- 1564-0094. ; :75, s. 56-57
-
Research review (pop. science, debate, etc.)abstract
- The DIGHT project is addressing the problem of building a scalable and highly available information store for the Electronic Health Records (EHRs) of the over one billion citizens of India. There has been much recent interest in information services that offer to manage an individual's healthcare records in electronic form, with systems such as Microsoft HealthVault and Google Health receiving widespread media attention. These systems are, however, proprietary and fears have been expressed over how the information stored in them will be used. In relation to these developments, countries with nationalized healthcare systems are also investigating the construction of healthcare information systems that store Electronic Health Records (EHRs) for their citizens.
|
|
| 37. |
- Dowling, Jim, et al.
(author)
-
Improving ICE service selection in a P2P system using the gradient topology
- 2007
-
In: First IEEE International Conference on Self-Adaptive and Self-Organizing Systems. - 9780769529066 ; , s. 285-288
-
Conference paper (peer-reviewed)abstract
- Internet Connectivity Establishment (ICE) is becoming increasingly important for P2P systems on the open Internet, as it enables NAT-bound peers to provide accessible services. A problem for P2P systems that provide ICE services is how peers discover good quality ICE servers for NAT traversal, that is, the TURN and STUN servers that provide relaying and hole-punching services, respectively. Skype provides a P2P-based solution to this problem, where super-peers provide ICE services. However experimental analysis of Skype indicates that peers perform a random walk of super-peers to find one with an acceptable round-trip latency. In this paper, we discuss a self organizing approach to discovering good quality ICE servers in a P2P system based the walk Topology. The walk Topology uses information about each peer’s ability to provide ICE services (open IP address, available bandwidth and expected session times) to construct a topology where the “better” peers for providing ICE services cluster in the center of the topology; this adaptation of the super-peer search space reduces the problem of finding a good quality ICE server from a random walk to a gradient ascent search.
|
|
| 38. |
|
|
| 39. |
- Drejhammar, Frej, et al.
(author)
-
Efficient simulation of view synchrony
- 2012. - 6
-
Reports (other academic/artistic)abstract
- This report presents an algorithm for efficiently simulating view synchrony, including failure-atomic total-order multicast in a discrete-time event simulator. In this report we show how a view synchrony implementation tailored to a simulated environment removes the need for third party middleware and detailed network simulation, thus reducing the complexity of a test environment. An additional advantage is that simulated view synchrony can generate all timing behaviours allowed by the model instead of just those exhibited by a particular view synchrony implementation.
|
|
| 40. |
|
|
| 41. |
- Drejhammar, Frej, et al.
(author)
-
Flow Java: declarative concurrency for Java.
- 2003. - 1
-
In: Proceedings of the Nineteenth International Conference on Logic Programming.
-
Conference paper (peer-reviewed)abstract
- Logic variables pioneered by (concurrent) logic and concurrent constraint programming are powerful mechanisms for automatically synchronizing concurrent computations. They support a declarative model of concurrency that avoids explicitly suspending and resuming computations. This paper presents Flow Java which conservatively extends Java with single assignment variables and futures as variants of logic variables. The extension is conservative with respect to object-orientation, types, parameter passing, and concurrency in Java. Futures support secure concurrent abstractions and are essential for seamless integration of single assignment variables into Java. We show how Flow Java supports the construction of simple and concise concurrent programming abstractions. We present how to moderately extend compilation and the runtime architecture of an existing Java implementation for Flow Java. Evaluation using standard Java benchmarks shows that in most cases the overhead is between 10% and 40%. For some pathological cases the runtime increases by up to 75%.
|
|
| 42. |
- Eassa, Fathy Elbouraey, et al.
(author)
-
ACC_TEST : Hybrid Testing Approach for OpenACC-Based Programs
- 2020
-
In: IEEE Access. - : Institute of Electrical and Electronics Engineers (IEEE). - 2169-3536. ; 8, s. 80358-80368
-
Journal article (peer-reviewed)abstract
- In recent years, OpenACC has been used in many supercomputers and attracted many non-computer science specialists for parallelizing their programs in different scientific fields, including weather forecasting and simulations. OpenACC is a high-level programming model that supports parallelism and is easy to learn to use by adding high-level directives without considering too many low-level details. Testing parallel programs is a difficult task, made even harder if using programming models, especially if they have been badly programmed. If so, it will be challenging to detect their runtime errors as well as their causes, whether the error is from the user source code or from the programming model directives. Even when these errors are detected and the source code modified, we cannot guarantee that the errors have been corrected or are still hidden. There are many tools and studies that have investigated several programming models for identifying and detecting related errors. However, OpenACC has not been targeted clearly in any testing tool or previous studies, even though OpenACC has many benefits and features that could lead to increasing use in achieving parallel systems with less effort. In this paper, we enhance ACC_TEST with the ability to test OpenACC-based programs and detect runtime errors by using hybrid-testing techniques that enhance error coverage occurring in OpenACC as well as overheads and testing time.
|
|
| 43. |
- Ekström, Niklas, et al.
(author)
-
A fault-tolerant sequentially consistent DSM with a compositional correctness proof
- 2016
-
In: 4th International Conference on Networked Systems, NETYS 2016. - Cham : Springer. - 9783319461397 ; , s. 183-192
-
Conference paper (peer-reviewed)abstract
- We present the SC-ABD algorithm that implements sequentially consistent distributed shared memory (DSM). The algorithm tolerates that less than half of the processes are faulty (crash-stop). Compared to the multi-writer ABD algorithm, SC-ABD requires one instead of two round-trips of communication to perform a write operation, and an equal number of round-trips (two) to perform a read operation. Although sequential consistency is not a compositional consistency condition, the provided correctness proof is compositional.
|
|
| 44. |
- El-Ansary, Sameh, et al.
(author)
-
A Framework for Peer-To-Peer Lookup Services based on k-ary search
- 2002
-
Reports (other academic/artistic)abstract
- Locating entities in peer-to-peer environments is a fundamentaloperation. Recent studies show that the concept of distributed hash table can be used to design scalable lookup schemes with good performance (i.e. small routing table and lookup length). In this paper, we propose a simple framework for deriving decentralized lookup algorithms. The proposed framework is simple in that it is based on the well-known concept of k-ary search. To demonstrate the applicability of our framework, we show how it can be used to instantiate Chord. When deriving a generalized Chord from our framework, we obtain better performance in terms of the routing table size (38% smaller than the generalization suggested by the Chord authors).
|
|
| 45. |
- El-Ansary, Sameh, et al.
(author)
-
A physics-inspired performance evaluation of a structured peer-to-peer overlay network
- 2005
-
In: IASTED International Conference on Parallel and Distributed Computing and Networks, as part of the 23rd IASTED International Multi-Conference on Applied Informatics. ; , s. 116-122
-
Conference paper (peer-reviewed)abstract
- In the majority of structured peer-to-peer overlay networks a graph with a desirable topology is constructed. In most cases, the graph is maintained by a periodic activity performed by each node in the graph to preserve the desirable structure in face of the continuous change of the set of nodes. The interaction of the autonomous periodic activities of the nodes renders the performance analysis of such systems complex and simulation of scales of interest can be prohibitive. Physicists, however, are accustomed to dealing with scale by characterizing a system using intensive variables, i.e. variables that are size independent. The approach has proved its usefulness when applied to satisfiability theory. This work is the first attempt to apply it in the area of distributed systems. The contribution of this paper is two-fold. First, we describe a methodology to be used for analyzing the performance of large scale distributed systems. Second, we show how we applied the methodology to find an intensive variable that describe the characteristic behavior of the Chord overlay network, namely, the ratio of the magnitude of perturbation of the network (joins/failures) to the magnitude of periodic stabilization of the network.
|
|
| 46. |
- El-Ansary, Sameh, et al.
(author)
-
An Analytical Study of Consistency and Performance of DHTs under Churn
- 2004
-
Reports (other academic/artistic)abstract
- In this paper, we present a complete analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a master-equation-based approach, which is used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. We demonstrate that this methodology is infact also well suited to describing structured overlay networks by an application to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of: the distribution of inter-node distances, the probability of network disconnection, the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict both the performance and consistency of lookups under churn. Additionally, we also discuss how churn may actually be of different 'types' and the implications this will have for structured overlays in general. All theoretical predictions match simulation results to a high extent. The analysis includes details that are applicable to a generic structured overlay deploying a ring as well as Chord-specific details that can act as guidelines for analyzing other systems.
|
|
| 47. |
- El-Ansary, Sameh, et al.
(author)
-
An Overview of Structured Overlay Networks
- 2005. - 1
-
In: Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks. - : CRC Press.
-
Book chapter (peer-reviewed)
|
|
| 48. |
- El-Ansary, Sameh, et al.
(author)
-
Analytical study of consistency and performance of DHTs under churn
-
Other publication (other academic/artistic)abstract
- In this paper, we present a complete analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a master-equation-based approach, which is used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. We demonstrate that this methodology is infact also well suited to describing structured overlay networks by an application to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of: the distribution of inter-node distances, the probability of network disconnection, the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict both the performance and consistency of lookups under churn. Additionally, we also discuss how churn may actually be of different ’types’ and the implications this will have for structured overlays in general. All theoretical predictions match simulation results to a high extent. The analysis includes details that are applicable to a generic structured overlay deploying a ring as well as Chord-specific details that can act as guidelines for analyzing other systems.
|
|
| 49. |
- El-Ansary, Sameh, 1975-
(author)
-
Designs and analyses in structured peer-to-peer systems
- 2005
-
Doctoral thesis (other academic/artistic)abstract
- Peer-to-Peer (P2P) computing is a recent hot topic in the areas of networking and distributed systems. Work on P2P computing was triggered by a number of ad-hoc systems that made the concept popular. Later, academic research efforts started to investigate P2P computing issues based on scientific principles. Some of that research produced a number of structured P2P systems that were collectively referred to by the term ``Distributed Hash Tables'' (DHTs). However, the research occurred in a diversified way leading to the appearance of similar concepts yet lacking a common perspective and not heavily analyzed. In this thesis we present a number of papers representing our research results in the area of structured P2P systems grouped as two sets labeled respectively ``Designs'' and ``Analyses''. The contribution of the first set of papers is as follows. First, we present the principle of distributed k-ary search (DKS) and argue that it serves as a framework for most of the recent P2P systems known as DHTs. That is, given the DKS framework, understanding existing DHT systems is done simply by seeing how they are instances of that framework. We argue that by perceiving systems as instances of the DKS framework, one can optimize some of them. We illustrate that by applying the framework to the Chord system, one of the most established DHT systems. Second, We show how the DKS framework helps in the design of P2P algorithms by two examples: (a) The DKS(n;k;f) system which is a system designed from the beginning on the principles of distributed k-ary search. (b) Two broadcast algorithms that take advantage of the distributed k-ary search tree. The contribution of the second set of papers is as follows. We account for two approaches that we used to evaluate the performance of a particular class of DHTs, namely the one adopting periodic stabilization for topology maintenance. The first approach was of an intrinsic empirical nature. In that approach, we tried to perceive a DHT as a physical system and account for its properties in a size-independent manner. The second approach was of a more analytical nature. In this approach we applied the technique of Master equations, which is a widely used technique in the analysis of natural systems. The application of the technique lead to a highly accurate description of the behavior of structured overlays. Additionally, the thesis contains a primer on structured P2P systems that tries to capture the main ideas that are prevailing in the field and enumerates a subset of the current hot and open research issues.
|
|
| 50. |
- El-Ansary, Sameh, et al.
(author)
-
Efficient broadcast in structured P2P networks
- 2003
-
In: Lecture Notes in Computer Science. - 0302-9743 .- 1611-3349. ; 2735, s. 304-314
-
Journal article (peer-reviewed)abstract
- In this position paper, we present an efficient algorithm for performing a broadcast operation with minimal cost in structured DHT-based P2P networks. In a system of N nodes, a broadcast message originating at an arbitrary node reaches all other nodes after exactly N - 1 messages. We emphasize the perception of a class of DHT systems as a form of distributed k-ary search and we take advantage of that perception in constructing a spanning tree that is utilized for efficient broadcasting. We consider broadcasting as a basic service that adds to existing DHTs the ability to search using arbitrary queries as well as dissiminate/collect global information.
|
|
