Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Special Issues
Distributed Computing Theory, Systems, Algorithms, and Data Structures
share announcement

Distributed Computing Theory, Systems, Algorithms, and Data Structures

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Parallel and Distributed Algorithms".

Deadline for manuscript submissions: closed (15 April 2021) | Viewed by 9619

Special Issue Editor

Dr. Gokarna Sharma

E-Mail Website
Guest Editor
Department of Computer Science, Kent State University, Kent, OH 44242, USA
Interests: distributed systems and algorithms; blockchain; network, graph, sensor, and robot coordination algorithms

Special Issue Information

Dear Colleagues,

We invite you to submit your latest research on the broad area of distributed computing to this Special Issue, “Distributed Computing Theory, Systems, Algorithms, and Data Structures”. The goal of this Special Issue is to improve understanding of the principles and practices underlying distributed computing. We solicit high-quality original research papers on problems that naturally arise in all areas of distributed computing. We welcome research papers from all viewpoints, including theory, algorithms, systems, practice, and experimentation. Potential topics include but are not limited to the following: design and analysis of distributed algorithms; lower bounds, complexity, and impossibility results; network protocols; distributed machine learning, operating systems, databases, resource management, scheduling, fault tolerance, and reliability; self-stabilization; peer-to-peer systems; concurrency, synchronization, and consistency; multicore and multiprocessor algorithms and architectures; distributed and concurrent data structures; blockchain protocols; wireless and sensor networks; mobile and robot computing; formal methods; game theory in distributed computing; high-performance, cluster, and grid computing; distributed storage and persistence; security and cryptography; coding and biological algorithms; and experimental evaluation of distributed algorithms and systems.

Dr. Gokarna Sharma
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • Blockchain protocols
  • Complexity, impossibility, and lower bounds
  • Concurrency, synchronization, and consistency
  • Design and analysis of distributed algorithms
  • Distributed and concurrent data structures
  • Distributed machine learning, operating systems, fault tolerance, and reliability
  • Distributed resource management and scheduling
  • Distributed storage and persistent memory
  • Experimental evaluation of distributed algorithms and systems
  • Formal methods for distributed computing
  • Game theory in distributed computing
  • Mobile and robot computing
  • Multicore and multiprocessor algorithms and architectures
  • Network protocols
  • Peer-to-peer systems
  • Security and cryptography
  • Self-stabilization
  • Wireless and sensor networks

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (3 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

39 pages, 32554 KiB  
Article
Adaptive Versioning in Transactional Memory Systems
by Pavan Poudel and Gokarna Sharma
Algorithms 2021, 14(6), 171; https://doi.org/10.3390/a14060171 - 31 May 2021
Viewed by 2816
Abstract
Transactional memory has been receiving much attention from both academia and industry. In transactional memory, program code is split into transactions, blocks of code that appear to execute atomically. Transactions are executed speculatively and the speculative execution is supported through data versioning [...] Read more.
Transactional memory has been receiving much attention from both academia and industry. In transactional memory, program code is split into transactions, blocks of code that appear to execute atomically. Transactions are executed speculatively and the speculative execution is supported through data versioning mechanism. Lazy versioning makes aborts fast but penalizes commits, whereas eager versioning makes commits fast but penalizes aborts. However, whether to use eager or lazy versioning to execute those transactions is still a hotly debated topic. Lazy versioning seems appropriate for write-dominated workloads and transactions in high contention scenarios whereas eager versioning seems appropriate for read-dominated workloads and transactions in low contention scenarios. This necessitates a priori knowledge on the workload and contention scenario to select an appropriate versioning method to achieve better performance. In this article, we present an adaptive versioning approach, called Adaptive, that dynamically switches between eager and lazy versioning at runtime, without the need of a priori knowledge on the workload and contention scenario but based on appropriate system parameters, so that the performance of a transactional memory system is always better than that is obtained using either eager or lazy versioning individually. We provide Adaptive for both persistent and non-persistent transactional memory systems using performance parameters appropriate for those systems. We implemented our adaptive versioning approach in the latest software transactional memory distribution TinySTM and extensively evaluated it through 5 micro-benchmarks and 8 complex benchmarks from STAMP and STAMPEDE suites. The results show significant benefits of our approach. Specifically, in persistent TM systems, our approach achieved performance improvements as much as 1.5× for execution time and as much as 240× for number of aborts, whereas our approach achieved performance improvements as much as 6.3× for execution time and as much as 170× for number of aborts in non-persistent transactional memory systems. Full article
(This article belongs to the Special Issue Distributed Computing Theory, Systems, Algorithms, and Data Structures)
►▼ Show Figures

Figure 1

35 pages, 1188 KiB  
Article
Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case
by Gokarna Sharma, Ramachandran Vaidyanathan and Jerry L. Trahan
Algorithms 2021, 14(2), 56; https://doi.org/10.3390/a14020056 - 9 Feb 2021
Cited by 7 | Viewed by 2684
Abstract
We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and use colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between [...] Read more.
We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and use colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line segment connecting them. In this paper, we consider the problem of positioning N autonomous robots on a plane so that every robot is visible to all others (this is called the Complete Visibility problem). This problem is fundamental, as it provides a basis to solve many other problems under obstructed visibility. In this paper, we provide the first, asymptotically optimal, O(1) time, O(1) color algorithm for Complete Visibility in the asynchronous setting. This significantly improves on an O(N)-time translation of the existing O(1) time, O(1) color semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free, i.e., robots do not share positions, and their paths do not cross. We also introduce a new technique for moving robots in an asynchronous setting that may be of independent interest, called Beacon-Directed Curve Positioning. Full article
(This article belongs to the Special Issue Distributed Computing Theory, Systems, Algorithms, and Data Structures)
►▼ Show Figures

Figure 1

15 pages, 497 KiB  
Article
Dynamic Ring Exploration with (H,S) View
by Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita and Toshimitsu Masuzawa
Algorithms 2020, 13(6), 141; https://doi.org/10.3390/a13060141 - 12 Jun 2020
Cited by 7 | Viewed by 3095
Abstract
The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration [...] Read more.
The researches about a mobile entity (called agent) on dynamic networks have attracted a lot of attention in recent years. Exploration which requires an agent to visit all the nodes in the network is one of the most fundamental problems. While the exploration of dynamic networks with complete information or with no information about network changes has been studied, an agent with partial information about the network changes has not been considered yet despite its practical importance. In this paper, we consider the exploration of dynamic networks by a single agent with partial information about network changes. To the best of our knowledge, this is the very first work to investigate the exploration problem with such partial information. As a first step in this research direction, we focus on 1-interval connected rings as dynamic networks in this paper. We assume that the single agent has partial information called the ( H , S ) view by which it always knows whether or not each of the links within H hops is available in each of the next S time steps. In this setting, we show that H + S ≥ n and S ≥ ⌈ n / 2 ⌉ (n is the size of the network) are necessary and sufficient conditions to explore 1-interval connected rings. Moreover, we investigate the upper and lower bounds of the exploration time. It is proven that the exploration time is O ( n 2 ) for ⌈ n / 2 ⌉ ≤ S < 2 H ′ − 1 , O ( n 2 / H + n H ) for S ≥ max ( ⌈ n / 2 ⌉ , 2 H ′ − 1 ) , O ( n 2 / H + n log H ) for S ≥ n − 1 , and Ω ( n 2 / H ) for any S where H ′ = min ( H , ⌊ n / 2 ⌋ ) . Full article
(This article belongs to the Special Issue Distributed Computing Theory, Systems, Algorithms, and Data Structures)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-3
Back to TopTop