| 1. |
- Atalar, Aras, 1985, et al.
(författare)
-
Modeling Energy Consumption of Lock-Free Queue Implementations
- 2015
-
Ingår i: 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, 25-29 May. - : IEEE Computer Society. - 1530-2075. - 9781479986484 ; , s. 229-238
-
Konferensbidrag (refereegranskat)abstract
- This paper considers the problem of modeling the energy behavior of lock-free concurrent queue data structures. Our main contribution is a way to model the energy behavior of lock-free queue implementations and parallel applications that use them. Focusing on steady state behavior we decompose energy behavior into throughput and power dissipation which can be modeled separately and later recombined into several useful metrics, such as energy per operation. Based on our models, instantiated from synthetic benchmark data, and using only a small amount of additional application specific information, energy and throughput predictions can be made for parallel applications that use the respective data structure implementation. To model throughput we propose a generic model for lock-free queue throughput behavior, based on a combination of the dequeuers' throughput and enqueuers' throughput. To model power dissipation we commonly split the contributions from the various computer components into static, activation and dynamic parts, where only the dynamic part depends on the actual instructions being executed. To instantiate the models a synthetic benchmark explores each queue implementation over the dimensions of processor frequency and number of threads. Finally, we show how to make predictions of application throughput and power dissipation for a parallel application using a lock-free queue requiring only a limited amount of information about the application work done between queue operations. Our case study on a Mandelbrot application shows convincing prediction results.
|
|
| 2. |
- Cederman, Daniel, 1981, et al.
(författare)
-
Lock-free Concurrent Data Structures
- 2013
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Concurrent data structures are the data sharing side of parallel programming. Data structures give the means to the program to store data, but also provide operations to the program to access and manipulate these data. These operations are implemented through algorithms that have to be efficient. In the sequential setting, data structures are crucially important for the performance of the respective computation. In the parallel programming setting, their importance becomes more crucial because of the increased use of data and resource sharing for utilizing parallelism. The first and main goal of this chapter is to provide a sufficient background and intuition to help the interested reader to navigate in the complex research area of lock-free data structures. The second goal is to offer the programmer familiarity to the subject that will allow her to use truly concurrent methods.
|
|
| 3. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Adaptive Plausible Clocks
- 2004
-
Ingår i: Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS 2004). - 0769520863 ; , s. 86--93-
-
Konferensbidrag (refereegranskat)abstract
- Having small-sized logical clocks with high causal-ordering accuracy is useful, especially where (i) the precision of the knowledge of the causal dependencies among events implies savings in time overhead and (ii) the cost of transmitting full vector clock timestamps - that precisely characterise the causal relation - is high. Plausible clocks can be used as timestamps to order events in a distributed system in a way that is consistent with the causal order as long as the events are causally dependent. We introduce the nonuniformly mapped R-entries vector (NUREV) clocks, a general class of plausible clocks that allow accuracy adaptation and we analyse the ways that these clocks may relate causally independent event pairs. Our analysis resulted in a set of conclusions and the formulation of new, adaptive plausible clocks algorithms, with improved accuracy, even when the number of clock entries is very small, which is important in peer-to-peer communication systems.
|
|
| 4. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Adaptive Plausible Clocks
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Having small-sized logical clocks with high causal-ordering accuracy is useful, especially where (i) the precision of the knowledge of the causal dependencies among events implies savings in time overhead and (ii) the cost of transmitting Full Vector clock timestamps |that precisely characterise the causal relation| is high. Plausible clocks can be used as timestamps to order events in a distributed system in a way that is consistent with the causal order as long as the events are causally dependent. The inaccuracy of a plausible clock algorithm is measured by the number of ordering errors it makes in an execution, i.e. the number of causally independent event pairs that it relates. In this work we study the accuracy of plausible clocks, which is measured by the number of causally independent event pairs that they relate. We introduce the Non-Uniformly Mapped R-Entries Vector (NUREV) clocks, a general class of plausible clocks, which allow the use of clock vectors with a small number of entries and which also allow each process in the system to use a di erent mapping between process-ids and clock-entry indices, the idea being that dynamic mappings allow self-tuning and adaptation to improve the accuracy of the clocks. Furthermore, we analyse the ways that these clocks may relate causally independent event pairs. Our analysis resulted in a set of conclusions and the formulation of new, adaptive plausible clocks algorithms, with improved accuracy, even when the number of clock entries is very small, which is important in peer-to-peer communication systems.
|
|
| 5. |
- Gidenstam, Anders, 1977
(författare)
-
Algorithms for synchronization and consistency in concurrent system services
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Synchronization, consistency and scalability are important issues in the design of concurrent computer system services. In this thesis we study the application of optimistic and scalable methods in concurrent system services. In a distributed setting we study scalable tracking of the causal relations between events, lightweight information dissemination in optimistic causal order in distributed systems and fault-tolerant and dynamic resource sharing. Further, we study scalable memory allocation, memory reclamation, threading, thread synchronization and data structures in shared memory systems. For each of the services we study we give the design of algorithms using optimistic methods, assess the correctness and analyze the behaviour of the algorithm, and in most cases describe implementations and perform experimental studies comparing the proposed algorithms to traditional approaches. We present a study of the accuracy of plausible timestamps for scalable event tracking in large systems. We analyze how these clocks may relate causally independent event pairs and based on the analysis we propose two new clock algorithms to satisfy the analysis criteria. We propose an information dissemination service providing optimistic causal order called lightweight causal cluster consistency. It offers scalable behaviour, low message size overhead and highprobability reliability guarantees for e.g. multi-peer collaborative applications. A key component in the dissemination service is a dynamic and fault-tolerant cluster management algorithm, which manages a set of tickets/resources such that each ticket has at most one owner at a time. In the dissemination service this algorithm manages senders and enables the use of small fixed size vector clocks. We present a lock-free concurrent memory allocator, NBmalloc, designed to enhance performance and scalability on multiprocessors which also shows in our experimental evaluation. We present a lock-free memory reclamation algorithm for use in the implementation of lock-free data structures. Our algorithm is the first practical one that has all the following features: (i) guarantees the safety of local as well as global references, (ii) provides an upper bound of deleted but not yet reclaimed nodes, (iii) is compatible with standard memory allocation schemes. We also present LFthreads, a user-level thread library that is implemented entirely using lock-free methods aiming for increased scalability and efficiency over traditional thread libraries.
|
|
| 6. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Allocating memory in a lock-free manner
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The potential of multiprocessor systems is frequently not fully realized by their system services. Certain synchronization methods, such as lock-based ones, may limit the parallelism. It is signi cant to see the impact of wait/lock-free synchronization design in key services for multiprocessor systems, such as the memory allocation service. E cient, scalable memory allocators for multithreaded applications in multiprocessor systems is a signi cant goal of recent research projects. We propose a lock-free memory allocator, to enhance the parallelism in the system. Its architecture is inspired by Hoard, a successful concurrent memory allocator, with a modular, scalable design that preserves scalability and helps avoiding false sharing and heap blowup. Within our e ort on designing appropriate lock-free algorithms for the synchronization in this system, we propose a new non-blocking data structure called at-sets, supporting conventional \internal" operations as well as \inter-object" operations, for moving elements between at-sets. We implemented the memory allocator in a set of multiprocessor systems (UMA Sun Enterprise 450, ccNUMA Origin 2000 and ccNUMA Origin 3800) and studied its behaviour. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved, while the scalability properties are enhanced even further with the help of lock-free synchronization.
|
|
| 7. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Allocating memory in a lock-free manner
- 2005
-
Ingår i: Proceedings of the 13th Annual European Symposium on Algorithms. ; , s. 329 -- 242-
-
Konferensbidrag (refereegranskat)abstract
- The potential of multiprocessor systems is often not fullyrealized by their system services. Certain synchronization methods, such as lock-based ones, may limit the parallelism. It is significant to see the impact of wait/lock-free synchronization design in key services for multiprocessor systems, such as the memory allocation service. Efficient, scalable memory allocators for multithreaded applications on multiprocessors is a significant goal of recent research projects. We propose a lock-free memory allocator, to enhance the parallelism in the system. Its architecture is inspired by Hoard, a successful concurrent memory allocator, with a modular, scalable design that preserves scalability and helps avoiding false-sharing and heap blowup. Within our effort on designing appropriate lock-free algorithms to construct this system, we propose a new non-blocking data structure called flat-sets, supporting conventional``internal'' operations as well as ``inter-object'' operations, for moving items between flat-sets.We implemented the memory allocator in a set of multiprocessor systems and studied its behaviour. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved, while thescalability properties are enhanced even further with the help of lock-free synchronization.
|
|
| 8. |
- Gidenstam, Anders, et al.
(författare)
-
Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency
- 2010
-
Ingår i: Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS) 2010. - Berlin, Heidelberg : Springer. - 9783642176524 - 3642176526 ; 6490, s. 302-317
-
Konferensbidrag (refereegranskat)abstract
- A lock-free FIFO queue data structure is presented in this paper. The algorithm supports multiple producers and multiple consumers and weak memory models. It has been designed to be cache-aware and work directly on weak memory models. It utilizes the cache behavior in concert with lazy updates of shared data, and a dynamic lock-free memory management scheme to decrease unnecessary synchronization and increase performance. Experiments on an 8-way multi-core platform show significantly better performance for the new algorithm compared to previous fast lock-free algorithms.
|
|
| 9. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Dynamic and fault-tolerant cluster management
- 2005
-
Ingår i: Proceedings of the 5th IEEE International Conference on Peer-to-Peer Computing. - 0769523765 ; , s. 237 -- 244-
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Recent decentralised event-based systems have focused on providing event delivery which scales with increasing number of processes. While the main focus of research has been on ensuring that processes maintain only a small amount of information on maintaining membership and routing, an important factor in achieving scalability for event-based peer-to-peer dissemination system is the number of events disseminated at the same time. This work presents a dynamic and fault tolerant cluster management method which can be used to coordinate concurrent access to resources in a peer-to-peer system. In the context of event-based dissemination systems the cluster management can be used to control the number of concurrently disseminated events. We present and analyse an algorithm implementing the proposed cluster management model in a fault-tolerant and decentralised way. The algorithm provides for each cluster a limited set of tickets. A process which has obtained a ticket may send events corresponding to the resources of the cluster. The algorithm guarantees that no two processes ever issue an event corresponding to the same ticket at the same time. The cluster management model on its own has interesting properties which can be useful for many peer-to-peer applications.
|
|
| 10. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2009
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : IEEE. - 1558-2183 .- 1045-9219. ; 20:8, s. 1173-1187
-
Tidskriftsartikel (refereegranskat)abstract
- We present an efficient and practical lock-free method for semiautomatic (application-guided) memory reclamation based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The method guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives that are available in modern computer systems, and provides an upper bound on the amount of memory waiting to be reclaimed. To the best of our knowledge, this is the first lock-free method that provides all of these properties. We provide analytical and experimental study of the method. The experiments conducted have shown that the method can also provide significant performance improvements for lock-free algorithms of dynamic data structures that require strong memory management.
|
|
| 11. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Efficient and Reliable Lock-Free Memory Reclamation Based on Reference Counting
- 2005
-
Ingår i: Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms & Networks. - 0769525091 ; , s. 202 - 207
-
Konferensbidrag (refereegranskat)abstract
- We present an efficient and practical lock-free implementation of a memory reclamation scheme based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The scheme guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives which are available in modern computer systems and provides an upper bound on the memory prevented for reuse. To the best of our knowledge, this is the first lock-free algorithm that provides all of these properties. Experimental results indicate significant performance improvements for lock-free algorithms of dynamic data structures that require strong garbage collection support.
|
|
| 12. |
- Gidenstam, Anders, et al.
(författare)
-
LFTHREADS : a lock-free thread library
- 2008
-
Ingår i: SIGARCH Computer Architecture News. - : Association for Computing Machinery, Inc.. - 0163-5964. ; , s. 88-92
-
Konferensbidrag (refereegranskat)abstract
- This extended abstract presents LFTHREADS, a thread library entirely based on lock-free methods, i.e. no spinlocks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lockfreedom is highly desirable in multiprocessors/multicores due to its advantages in parallelism, fault-tolerance, convoy-avoidance and more, there is an increased demand in lock-free methods in parallel applications, hence also in multiprocessor/multicore system services. LFTHREADS is the first thread library that provides a lock-free implementation of blocking synchronization primitives for application threads; although the latter may sound like a contradicting goal, such objects have several benefits: e.g. library operations that block and unblock threads on the same synchronization object can make progress in parallel while maintaining the desired thread-level semantics and without having to wait for any "low" operations among them. Besides, as no spin-locks or similar synchronization mechanisms are employed, memory contention can be reduced and processors/cores are able to do useful work. As a consequence, applications, too, can enjoy enhanced parallelism and fault-tolerance. For the synchronization in LFTHREADS we have introduced a new method, which we call responsibility hand-off (RHO), that does not need any special kernel support. The RHO method is also of independent interest, as it can also serve as a tool for lock-free token passing, management of contention and interaction between scheduling and synchronization. This paper gives an outline and the context of LFTHREADS. For more details the reader is refered to [7] and [8].
|
|
| 13. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
LFthreads: A lock-free thread library
- 2007
-
Ingår i: Proceedings of the 11th International Conference On Principles Of Distributed Systems, Lecture Notes in Computer Science Vol. 4878, Springer Verlag. - 9783540770954 ; , s. 217 - 231
-
Konferensbidrag (refereegranskat)
|
|
| 14. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
LFthreads: a lock-free thread library
- 2008
-
Ingår i: 1st Swedish Workshop on Multi-Core Computing. ; urn:nbn:se:bth-00422, s. 107-116
-
Konferensbidrag (refereegranskat)
|
|
| 15. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
LFthreads: A lock-free thread library or "Blocking without locking"
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This paper presents LFthreads, a thread library whose synchronization is entirely based on lock-free techniques, which means that no spin-locks or similar synchronization mechanisms are employed in the implementation of the multithreading. This implies that processors are always able to do useful work and is achieved by a new synchronization mechanism that does not need any special kernel support. Since lock-freeness is highly desirable in multiprocessors due to its advantages in performance, fault-tolerance, convoy- and deadlock-avoidance, there is an increased demand in lock-free methods in multiprocessor applications, hence also in multiprocessor system services. This is why the existence of a lock-free multithreading library is important. To the best of our knowledge LFthreads is the first thread library that provides a lock-free blocking synchronization primitive for application threads.
|
|
| 16. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Lightweight Causal Cluster Consistency
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Within an effort for providing a layered architecture of services supporting multi-peer collaborative applications, this paper proposes a new type of consistency management aimed for applications where a large number of processes share a large set of replicated objects. Many such applications, like peer-to-peer collaborative environments for training or entertaining purposes, platforms for distributed monitoring and tuning of networks, rely on a fast propagation of updates on objects, however they also require a notion of consistent state update. To cope with these requirements and also ensure scalability, we propose the cluster consistency model. In the proposed model a dynamic set of processes, called coordinators, may concurrently propose updates to a subset of objects which form a cluster. Updates are applied in some order of interest by the coordinators of the cluster. Moreover, any interested process can receive update messages referring to replicated objects, with an option for the updates to be delivered unordered or in the same order as to the coordinators.We also propose a two-layered architecture for providing cluster consistency. This is a general architecture that can be applied on top of the standard Internet communication layers and can offer a modular, layered set of services to the applications that need them. Further, we present a fault-tolerant protocol implementing causal cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting group communication. Our experimental study, conducted by programming and evaluating the two-layered architecture as protocols executing on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high-probability reliability guarantees.
|
|
| 17. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Lightweight Causal Cluster Consistency
- 2005
-
Ingår i: Proceedings of the Conference on Innovative Internet Community Systems (I2CS 2005), Lecture Notes in Computer Science Vol. 3908, Springer Verlag, 2006.. ; 3908, s. 17 - 28
-
Konferensbidrag (refereegranskat)abstract
- Within an effort for providing a layered architecture of services supporting multi-peer collaborative applications, this paper proposes a new type of consistency management aimed for applications where a large number of processes share a large set of replicated objects. Many such applications, like peer-to-peer collaborative environments for training or entertaining purposes, platforms for distributed monitoring and tuning of networks, rely on a fast propagation of updates on objects, however they also require a notion of consistent state update. To cope with these requirements and also ensure scalability, we propose the cluster consistency model. We also propose a two-layered architecture for providing cluster consistency. This is a general architecture that can be applied on top of the standard Internet communication layers and offers a modular, layered set of services to the applications that need them. Further, we present a fault-tolerant protocol implementing causal cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting group communication. Our experimental study, conducted by implementing and evaluating the two-layered architecture on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high-probability reliability guarantees.
|
|
| 18. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Lightweight Causal Cluster Consistency
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Within an effort for providing a layered architecture of services for middleware supporting multi-peer collaborative applications, this paper proposes a type of consistency management called causal cluster consistency which is aimed for applications where a large number of processes share a large set of replicated objects. Many such applications, like peer-to-peer collaborative environments for educational, training or entertaining purposes, platforms for distributed monitoring and tuning of networks, rely on a fast propagation of updates on objects, however they also require a notion of consistent state update. To cope with these requirements and also ensure scalability, we propose the cluster consistency model. In a cluster consistency protocol a privileged dynamic set of processes, called coordinators, may concurrently propose updates to a subset of objects which form a cluster. The updates are applied in some order of interest by the coordinators of the cluster. Moreover, any interested process can receive update messages referring to replicated objects, with an option for the updates to be delivered unordered or in the same order as to the coordinators. This work also describes a protocol implementing causal cluster consistency, which provides a fault tolerant and dynamic membership algorithm to manage the cluster members. The membership algorithm also coordinates the dynamic assignment of process identifiers to vector clock entries. Hence, this protocol provides optimistic causal order in combination with any group communication protocol. We evaluate the performance of causal cluster consistency running on top of decentralised probabilistic protocols on support for group communication. These protocols scale well, impose an even load on the system, and provide high-probability reliability guarantees for events to be delivered to every process in the group.
|
|
| 19. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Lightweight Causal Cluster Consistency
- 2006
-
Ingår i: Proceedings of the Conference on Innovative Internet Community Systems, LNCS, Springer Verlag. ; 3908:-, s. 17-28
-
Tidskriftsartikel (refereegranskat)abstract
- Within an e®ort for providing a layered architecture of services supporting multipeer collaborative applications, this paper proposes a new type of consistency management aimed for applications where a large number of processes share a large set of replicated objects. Many such applications, like peer-to-peer collaborative environments for training or entertaining purposes, platforms for distributed monitoring and tuning of networks, rely on a fast propagation of updates on objects, however they also require a notion of consistent state update. To cope with these requirements and also ensure scalability, we propose the cluster consistency model. We also propose a two-layered architecture for providing cluster consistency. This is a general architecture that can be applied on top of the standard Internet communication layers and o®ers a modular, layered set of services to the applications that need them. Further, we present a fault-tolerant protocol implementing causal cluster consistency with predictable reliability, running on top of decentralized probabilistic protocols supporting group communication. Our experimental study, conducted by implementing and evaluating the two-layered architecture on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high-probability reliability guarantees.
|
|
| 20. |
- Gidenstam, Anders, et al.
(författare)
-
NBmalloc: Allocating Memory in a Lock-Free Manner
- 2010
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 58:2, s. 304-338
-
Tidskriftsartikel (refereegranskat)abstract
- Efficient, scalable memory allocation for multithreaded applications on multiprocessors is a significant goal of recent research. In the distributed computing literature it has been emphasized that lock-based synchronization and concurrency-control may limit the parallelism in multiprocessor systems. Thus, system services that employ such methods can hinder reaching the full potential of these systems. A natural research question is the pertinence and the impact of lock-free concurrency control in key services for multiprocessors, such as in the memory allocation service, which is the theme of this work. We show the design and implementation of NBmalloc, a lock-free memory allocator designed to enhance the parallelism in the system. The architecture of NBmalloc is inspired by Hoard, a well-known concurrent memory allocator, with modular design that preserves scalability and helps avoiding false-sharing and heap-blowup. Within our effort to design appropriate lock-free algorithms for NBmalloc, we propose and show a lock-free implementation of a new data structure, flat-set, supporting conventional "internal" set operations as well as "inter-object" operations, for moving items between flat-sets. The design of NBmalloc also involved a series of other algorithmic problems, which are discussed in the paper. Further, we present the implementation of NBmalloc and a study of its behaviour in a set of multiprocessor systems. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved.
|
|
| 21. |
- Gidenstam, Anders, 1977, et al.
(författare)
-
Practical and Efficient Lock-Free Garbage Collection Based on Reference Counting
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present an efficient and practical lock-free implementation of a garbage collection scheme based on reference counting aimed for the use with arbitrary lock-free dynamic data structures. The scheme guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives which are available in modern computer systems and provides an upper bound on the memory prevented for reuse. To the best of our knowledge, this is the first lock-free algorithm that provides all of these properties. Experimental results indicate significant performance improvements for lock-free data structures that require strong garbage collection.
|
|
| 22. |
- Gidenstam, Anders, et al.
(författare)
-
Scalable group communication supporting configurable levels of consistency
- 2013
-
Ingår i: Concurrency Computation Practice and Experience. - : Wiley. - 1532-0634 .- 1532-0626. ; 25:5, s. 649-671
-
Tidskriftsartikel (refereegranskat)abstract
- Group communication is deployed in many evolving Internet-scale cooperative applications such as multiplayer online games and virtual worlds to efficiently support interaction on information relevant to a potentially very large number of users or objects. Especially peer-to-peer based group communication protocols have evolved as a promising approach to allow intercommunication between many distributed peers. Yet, the delivery semantics of robust and scalable protocols such as gossiping is not sufficient to support consistency semantics beyond eventual consistency because no relationship on the order of events is enforced. On the other hand, traditional consistency models provided by reliable group communication providing causal or even total order are restricted to support only small groups.This article proposes the cluster consistency model which bridges the gap between traditional and current approaches in supporting both scalability and ordered event delivery. We introduce a dynamic and fault tolerant cluster management method that can coordinate concurrent access to resources in a peer-to-peer system and can be used to establish fault-tolerant configurable cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting scalable group communication. This is achieved by a general two-layered architecture that can be applied on top of the standard Internet communication layers and offers a modular, layered set of services to the applications that need them. Further, we present a fault-tolerant method implementing causal cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting group communication.This paper provides analytical and experimental evaluation of the properties regarding the fault tolerance of the approach. Furthermore, our experimental study, conducted by implementing and evaluating the two-layered architecture on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high-probability reliability guarantees.
|
|
| 23. |
- Gidenstam, Anders, 1977
(författare)
-
Synchronization and consistency in concurrent systems
- 2004
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis investigates aspects of synchronization and coordination in concurrent systems. In such systems synchronization and coordination are highly important as they form a basis for how a set of entities can collaborate to solve a task. In systems without shared knowledge of global time logical clocks provide a way to track how events are related to each other. Small-sized logical clocks with high causal-ordering accuracy is useful, in particular where(i) the precision of the knowledge of the causal dependencies among events implies savings in time overhead and (ii) the overhead of Full Vector clock timestamps is high. We introduce the Non-Uniformly Mapped R-Entries Vector (NUREV) clocks, a general class of plausible clocks that allow accuracy adaptation and we analyse the ways that these clocks may relate causally independent pairs of events.Our analysis resulted in a set of conclusions and the formulation of new, adaptive plausible clocks algorithms with improved accuracy even when the number of clock entries is very small, which is important in peer-to-peer communication systems.Concerning system services in concurrent systems, such as scheduling and resource allocation, the potential of efficient synchronization methods is large.In particular, in multiprocessor systems certain synchronization methods, such as lock-based ones, may limit the parallelism. It is significant to see the impact of wait/lock-free synchronization design in key services for multiprocessor systems, such as the memory allocationservice. Therefore efficient and scalable memory allocators for multi-threaded applications in multiprocessor systems is a significant goal of recent research projects.We propose a lock-free memory allocator, to enhance the parallelism in such systems. Its architecture is inspired by Hoard, a successful concurrent memory allocator, with a modular and scalable design that preserves scalability and helps avoiding false sharing and heap blowup. Within our effort on designing appropriate lock-free algorithms for the synchronization in multiprocessor systems, we propose anew non-blocking data structure called flat-sets, supporting conventional ``internal'' operations as well as ``inter-object'' operations for moving elements between flat-sets. Our experiments indicate that the scalability properties are enhanced even further with the help of the lock-free synchronization, without compromising the othergood properties provided by the Hoard architecture.
|
|
| 24. |
- Johansson, Ulf, et al.
(författare)
-
Venn predictors for well-calibrated probability estimation trees
- 2018
-
Ingår i: 7th Symposium on Conformal and Probabilistic Prediction and Applications. ; , s. 3-14, s. 3-14
-
Konferensbidrag (refereegranskat)abstract
- Successful use of probabilistic classification requires well-calibrated probability estimates, i.e., the predicted class probabilities must correspond to the true probabilities. The standard solution is to employ an additional step, transforming the outputs from a classifier into probability estimates. In this paper, Venn predictors are compared to Platt scaling and isotonic regression, for the purpose of producing well-calibrated probabilistic predictions from decision trees. The empirical investigation, using 22 publicly available datasets, showed that the probability estimates from the Venn predictor were extremely well-calibrated. In fact, in a direct comparison using the accepted reliability metric, the Venn predictor estimates were the most exact on every data set.
|
|
| 25. |
- Larsson, Andreas, 1979, et al.
(författare)
-
Multi-word Atomic Read/Write Registers on Multiprocessor Systems
- 2004
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 3540230254 ; 3221, s. 736-748
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this paper we develop a simple and efficient algorithm for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this paper we also evaluate the performance of our algorithm and the performance of a practical previously know algorithm that is based only on read and write primitives. The evaluation is performed on 3 well-known, parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases our algorithm performs better, accordingly to its complexity behavior.
|
|
| 26. |
- Larsson, Andreas, 1979, et al.
(författare)
-
Multiword atomic read/write registers on multiprocessor systems
- 2008
-
Ingår i: Journal of Experimental Algorithmics. - 1084-6654. ; 13, s. 7-30
-
Tidskriftsartikel (refereegranskat)abstract
- Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this article, we also experimentally evaluate the performance of our algorithm, together with lock-based approaches and a practical, previously previously known algorithm that is based that is based only on read and write primitives. The experimental evaluation is performed on three well-known parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases the READERSFIELD algorithm performs better, following its analytical evaluation.
|
|
| 27. |
- Larsson, Andreas, et al.
(författare)
-
Multiword atomic read/write registers on multiprocessor systems
- 2009
-
Ingår i: ACM Journal of Experimental Algorithmics. - : Association for Computing Machinery, Inc.. - 1084-6654. ; 13:1, s. 1.7-1.30
-
Tidskriftsartikel (refereegranskat)abstract
- Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this article, we develop a simple and efficient algorithm, the READERSFIELD algorithm, for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this article, we also experimentally evaluate the performance of our algorithm, together with lock-based approaches and a practical, previously previously known algorithm that is based that is based only on read and write primitives. The experimental evaluation is performed on three well-known parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases the READERSFIELD algorithm performs better, following its analytical evaluation.
|
|
| 28. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
A Consistency Framework for Iteration Operations in Concurrent Data Structures
- 2015
-
Ingår i: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015. - : IEEE Computer Society. - 1530-2075. - 9781479986484 ; , s. 239-248
-
Konferensbidrag (refereegranskat)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides invariability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamppost's systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we point out and study trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.
|
|
| 29. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
Enhancing Concurrent Data Structures with Concurrent Iteration Operations
- 2014
-
Ingår i: MCC14: Seventh Swedish Workshop on Multicore Computing.
-
Konferensbidrag (refereegranskat)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data.Data structures come with a set of predefined operations, specified by the semantics of the data structure.In the literature and in several contemporary commonly used programming environments,the notion of iteration has been introduced for collection data structures,as a bulk operation enhancing the native set of operations.Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures.In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide.Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport's systematic definitions for registers.Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations.Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We describe a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.
|
|
| 30. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
Enhancing Concurrent Data Structures with Concurrent Iteration Operations: Consistency and Algorithms
- 2013
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data.Data structures come with a set of predefined operations, specified by the semantics of the data structure.In the literature and in several contemporary commonly used programming environments,the notion of iterations has been introduced for collection data structures,as a bulk operation enhancing the native set of their operations.Iterations in several of these contexts are treated as sequential in nature and may freeze the data structure while operatingor provide a variety of consistency guarantees when running concurrently with the native operations of the data structures.In this work we study iterations in concurrent data structures with respect to their coexistence with the native operations of the latter and the guarantees that they provide under concurrency.Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport's systematic definitions for registers.By using queues, fixed-domain sets and composite registers as case-studies of underlying objects, we show a set of constructions of iteration operations, satisfying these properties.Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We show a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.
|
|
| 31. |
- Nikolakopoulos, Ioannis, 1986, et al.
(författare)
-
Of concurrent data structures and iterations
- 2015
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. - 9783319240237 ; 9295, s. 358-369, s. 358-369
-
Konferensbidrag (refereegranskat)abstract
- Bulk operations on data structures are widely used both on user-level but also on programming language level. Iterations are a good example of such bulk operations. In the sequential setting iterations are easy to design on top of an algorithmic construction of a data structure and is not considered as a challenge. In a concurrent environment, such as a multicore system, the situation is completely different and the issue of extending concurrent data structure designs to support iteration operations opens new research challenges in concurrent algorithmic data structure implementations, with respect to consistency and efficiency. In this paper we take a journey through this young and evolving research topic. More precisely we describe recent advances in the area together with an overview of iteration implementations that have appeared in the research literature as well as in widely-used programming environments and we outline a range of application targets and challenging future directions.
|
|
| 32. |
- Nikolakopoulos, Yiannis, et al.
(författare)
-
Enhancing Concurrent Data Structures with Concurrent Iteration Operations : Consistency Framework and Trade-offs
- 2014
-
Konferensbidrag (refereegranskat)abstract
- Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides linearizability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamport’s systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we demonstrate the trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure. We describe a set of algorithms that demonstrate these and study the implications on the efficiency of the implementations.
|
|
| 33. |
- Sundell, Håkan, 1968, et al.
(författare)
-
A Lock-Free Algorithm for Concurrent Bags
- 2011
-
Ingår i: 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11.San Jose, 4-6 June 2011. - New York, NY, USA : ACM. - 9781450307437 ; , s. 335-344
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithmsupports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrencyefficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supportedsemantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handlingconcurrent modifications of linked lists using double marks, detection of total emptiness, and efficientmemory management. Experiments on a 24-way multi-core platform show significantly better performancefor the new algorithm compared to previous algorithms of relevance.Keywords: concurrent; data structure; non-blocking; shared memory;
|
|
| 34. |
- Sweidan, Dirar
(författare)
-
Data-driven decision support in digital retailing
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In the digital era and advent of artificial intelligence, digital retailing has emerged as a notable shift in commerce. It empowers e-tailers with data-driven insights and predictive models to navigate a variety of challenges, driving informed decision-making and strategic formulation. While predictive models are fundamental for making data-driven decisions, this thesis spotlights binary classifiers as a central focus. These classifiers reveal the complexities of two real-world problems, marked by their particular properties. Specifically, binary decisions are made based on predictions, relying solely on predicted class labels is insufficient because of the variations in classification accuracy. Furthermore, prediction outcomes have different costs associated with making different mistakes, which impacts the utility.To confront these challenges, probabilistic predictions, often unexplored or uncalibrated, is a promising alternative to class labels. Therefore, machine learning modelling and calibration techniques are explored, employing benchmark data sets alongside empirical studies grounded in industrial contexts. These studies analyse predictions and their associated probabilities across diverse data segments and settings. The thesis found, as a proof of concept, that specific algorithms inherently possess calibration while others, with calibrated probabilities, demonstrate reliability. In both cases, the thesis concludes that utilising top predictions with the highest probabilities increases the precision level and minimises the false positives. In addition, adopting well-calibrated probabilities is a powerful alternative to mere class labels. Consequently, by transforming probabilities into reliable confidence values through classification with a rejection option, a pathway emerges wherein confident and reliable predictions take centre stage in decision-making. This enables e-tailers to form distinct strategies based on these predictions and optimise their utility.This thesis highlights the value of calibrated models and probabilistic prediction and emphasises their significance in enhancing decision-making. The findings have practical implications for e-tailers leveraging data-driven decision support. Future research should focus on producing an automated system that prioritises high and well-calibrated probability predictions while discarding others and optimising utilities based on the costs and gains associated with the different prediction outcomes to enhance decision support for e-tailers.
|
|
| 35. |
- Sweidan, Dirar, et al.
(författare)
-
Improved Decision Support for Product Returns using Probabilistic Prediction
- 2023
-
Ingår i: Proceedings 2023 Congress in Computer Science, Computer Engineering, & Applied Computing, CSCE 2023. - : IEEE. - 9798350327601 - 9798350327595 - 9798350327588 ; , s. 1567-1573
-
Konferensbidrag (refereegranskat)abstract
- Product returns are not only costly for e-tailers, but the unnecessary transports also impact the environment. Consequently, online retailers have started to formulate policies to reduce the number of returns. Determining when and how to act is, however, a delicate matter, since a too harsh approach may lead to not only the order being cancelled, but also the customer leaving the business. Being able to accurately predict which orders that will lead to a return would be a strong tool, guiding which actions to be taken. This paper addresses the problem of data-driven product return prediction, by conducting a case study using a large real-world data set. The main results are that well-calibrated probabilistic predictors are essential for providing predictions with high precision and reasonable recall. This implies that utilizing calibrated models to predict some instances, while rejecting to predict others can be recommended. In practice, this would make it possible for a decision-maker to only act upon a subset of all predicted returns, where the risk of a return is very high.
|
|
| 36. |
- Sweidan, Dirar, et al.
(författare)
-
Predicting Customer Churn in Retailing
- 2022
-
Ingår i: Proceedings 21st IEEE International Conference on Machine Learning and Applications ICMLA 2022. - : IEEE. - 9781665462839 - 9781665462846 ; , s. 635-640
-
Konferensbidrag (refereegranskat)abstract
- Customer churn is one of the most challenging problems for digital retailers. With significantly higher costs for acquiring new customers than retaining existing ones, knowledge about which customers are likely to churn becomes essential. This paper reports a case study where a data-driven approach to churn prediction is used for predicting churners and gaining insights about the problem domain. The real-world data set used contains approximately 200 000 customers, describing each customer using more than 50 features. In the pre-processing, exploration, modeling and analysis, attributes related to recency, frequency, and monetary concepts are identified and utilized. In addition, correlations and feature importance are used to discover and understand churn indicators. One important finding is that the churn rate highly depends on the number of previous purchases. In the segment consisting of customers with only one previous purchase, more than 75% will churn, i.e., not make another purchase in the coming year. For customers with at least four previous purchases, the corresponding churn rate is around 25%. Further analysis shows that churning customers in general, and as expected, make smaller purchases and visit the online store less often. In the experimentation, three modeling techniques are evaluated, and the results show that, in particular, Gradient Boosting models can predict churners with relatively high accuracy while obtaining a good balance between precision and recall.
|
|
| 37. |
- Sweidan, Dirar, et al.
(författare)
-
Predicting returns in men's fashion
- 2020
-
Ingår i: Developments of Artificial Intelligence Technologies In Computation and Robotics. - Singapore : World Scientific. - 9789811223334 - 9789811223341 ; , s. 1506-1513
-
Konferensbidrag (refereegranskat)abstract
- While consumers value a free and easy return process, the costs to e-tailers associated with returns are substantial and increasing. Consequently, merchants are now tempted to implement stricter policies, but must balance this against the risk of losing valuable customers. With this in mind, data-driven and algorithmic approaches have been introduced to predict if a certain order is likely to result in a return. In this application paper, a novel approach, combining information about the customer and the order, is suggested and evaluated on a real-world data set from a Swedish e-tailer in men's fashion. The results show that while the predictive accuracy is rather low, a system utilizing the suggested approach could still be useful. Specifically, it is reasonable to assume that an e-tailer would only act on predicted returns where the confidence is very high, e.g., the top 1-5%. For such predictions, the obtained precision is 0.918-0.969, with an acceptable detection rate.
|
|
