| 181. |
- Papatriantafilou, Marina, 1966, et al.
(author)
-
Towards a Library of Distributed Algorithms and Animations
- 1998
-
In: Proceedings of the 4th International Conference on Computer Aided Learning and Instruction in Science and Engineering (CALISCE '98). ; , s. 407-410
-
Conference paper (peer-reviewed)
|
|
| 182. |
|
|
| 183. |
|
|
| 184. |
- Petig, Thomas, 1985, et al.
(author)
-
Self-stabilizing TDMA Algorithms for Wireless Ad-Hoc Networks without External Reference
- 2013
-
In: 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. - 9783319030883 ; 8255, s. 354-356
-
Conference paper (peer-reviewed)abstract
- Cooperative systems will ultimately carry out risk-related tasks and liberate mankind from mundane labor. The implementation of these systems implies the use of wireless ad hoc networks and their critical component - a medium access control (MAC) layer that satisfies severe timing requirements. Infrastructure-based wireless networks successfully provide high bandwidth utilization and bounded communication delay. They divide the radio into timeslots of uniform size, ξ, that are then combined into frames of uniform size, τ. Base-stations, or wireless network coordinators can schedule the frame in a way that enables each node to transmit during its own timeslot, and arbitrate between nearby nodes that wish to communicate concurrently.
|
|
| 185. |
- Petig, Thomas, 1985, et al.
(author)
-
Self-stabilizing TDMA algorithms for wireless ad-hoc networks without external reference
- 2014
-
In: 13th Annual Mediterranean Ad Hoc Networking Workshop, MED-HOC-NET 2014, Piran, Slovenia, 2-4 June 2014. - 9781479952588 ; , s. 87-94
-
Conference paper (peer-reviewed)abstract
- Time division multiple access (TDMA) is a method for sharing communication media. In wireless communications, TDMA algorithms often divide the radio time into timeslots of uniform size, ξ, and then combine them into frames of uniform size, b τ. We consider TDMA algorithms that allocate at least one timeslot in every frame to every node. Given a maximal node degree, δ, and no access to external references for collision detection, time or position, we consider the problem of collision-free self-stabilizing TDMA algorithms that use constant frame size. We demonstrate that this problem has no solution when the frame size is τ
|
|
| 186. |
|
|
| 187. |
- Rakundo, Adones, 1986, et al.
(author)
-
Brief announcement: 2D-stack - A scalable lock-free stack design that continuously relaxes semantics for better performance
- 2018
-
In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. - New York, NY, USA : ACM. ; , s. 407-409
-
Conference paper (peer-reviewed)abstract
- We briefly describe an efficient lock-free concurrent stack design with tunable and tenable relaxed semantics to allow for better performance. The design is tunable and allow for a continuous monotonic trade of weaker semantics for better throughput performance. Concurrent stacks have an inherent scalability bottleneck due to their single access point for both their operations. Elimination and semantics relaxation have been proposed in the literature to address this problem. Semantics relaxation has the potential to reach monotonically very high throughput by continuously trading relaxation for throughput. Previous solutions could not fully leverage this potential. We suggest a new two dimensional design that can achieve this by exploiting disjoint access parallelism in one dimension and locality in the other within tight accuracy bounds. The behaviour of the algorithm is tightly bound. We compare experimentally to previous work, with respect to throughput and relaxed behaviour observed, on different relaxation and concurrency settings. The experimental evaluation shows that our algorithm significantly outperform all other algorithms in terms of performance, also maintain better accuracy in contrast to other designs with relaxed semantics.
|
|
| 188. |
- Rodrigues, Luís, et al.
(author)
-
Topic 8 Distributed Systems and Algorithms
- 2007
-
In: Euro-Par 2007 Parallel Processing.
-
Book chapter (other academic/artistic)abstract
- Parallel computing is increasingly exposed to the development and challengesof distributed systems, such as the lack of load balancing, asynchrony, long latencies,network partitions, failures, disconnected operations, heterogeneity andprotocol standardization. Furthermore, distributed systems are becoming larger,more diverse and more dynamic. This Euro-Par topic provides a forum for researchand practice, of interest to both academia and industry, about distributedsystems, distributed computing, distributed algorithms, and parallel processingon distributed systems. Submission was encouraged across the whole area,with emphasis on the following: design and practice of distributed algorithmsand data structures, analysis of the behaviour of distributed systems and algorithms,distributed operating systems, parallel processing on distributed systems,resource and service discovery, resource sharing and in distributed systems, distributedfault tolerance, security in distributed systems, scalability, concurrencyand performance in distributed systems, middleware for parallel computations,web services, interoperability and standards, self-organised and self-adjustingdistributed systems.Thirty-two papers were submitted in this topic, eight of which have beenaccepted for publication. The accepted papers cover a wide range of aspectsin the distributed system and algorithms topic. Three papers are related withthe problem of data sharing in distributed and parallel systems, two papersaddress issues related with mobile agents in graphs, and, finally, three papersaddress fundamental distributed algorithm problems, such as failure detection,consensus, and spanning tree construction.
|
|
| 189. |
- Rukundo, Adones, 1986, et al.
(author)
-
2D-Stack: A scalable lock-free stack design that continuously relaxes semantics for better performance
- 2018
-
Reports (other academic/artistic)abstract
- In this report, we propose an efficient lock-free concurrent stack design with tunable and tenable relaxed semantics to allow for better performance. The design is materialized by a shared memory distributed stack design that allow for a continuous monotonic trade of weaker semantics for better throughput performance. Concurrent stacks have an inherent scalability bottleneck due to their single access point for both push and pop operations. Elimination and semantics relaxation have been proposed in the literature to address this problem. Semantic relaxation has the potential and flexibility to reach monotonically very high throughput. Previous solutions could not fully leverage this potential. We propose a new two-dimensional design that can achieve this by exploiting disjoint access parallelism in one dimension and locality in the other. This is achieved through distributing the stack in form of sub-stacks that are accessed independently in parallel. Load balancing is used to keep a balanced number of operations on individual sub-stacks. We also provide tight relaxation bounds for the behaviour of our algorithm. We compare experimentally to previous work, with respect to throughput and relaxed behaviour observed, on different relaxation and concurrency settings. The results show that our algorithm signicantly outperform all other algorithms in terms of performance, while maintaining better quality in contrast to other designs with relaxed semantics.
|
|
| 190. |
- Rukundo, Adones, 1986, et al.
(author)
-
Monotonically relaxing concurrent data-structure semantics for increasing performance: An efficient 2D design framework
- 2019
-
In: Leibniz International Proceedings in Informatics, LIPIcs. - 1868-8969. ; 146
-
Conference paper (peer-reviewed)abstract
- There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address this challenge in this paper. We present an efficient, lock-free, concurrent data structure design framework for out-of-order semantic relaxation. We introduce a new two dimensional algorithmic design, that uses multiple instances of a given data structure. The first dimension of our design is the number of data structure instances operations are spread to, in order to benefit from parallelism through disjoint memory access; the second dimension is the number of consecutive operations that try to use the same data structure instance in order to benefit from data locality. Our design can flexibly explore this two-dimensional space to achieve the property of monotonically relaxing concurrent data structure semantics for better performance within a tight deterministic relaxation bound, as we prove in the paper. We show how our framework can instantiate lock-free out-of-order queues, stacks, counters and dequeues. We provide implementations of these relaxed data structures and evaluate their performance and behaviour on two parallel architectures. Experimental evaluation shows that our two-dimensional design significantly outperforms the respected previous proposed designs with respect to scalability and performance. Moreover, our design increases performance monotonically as relaxation increases.
|
|
