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, time, color algorithm for Complete Visibility in the asynchronous setting. This significantly improves on an -time translation of the existing time, 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.
10 March 2022 in IEEE Transactions on Parallel and Distributed Systems
We consider the distributed setting of n autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (the {\em robots with lights} model). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane. The {\sc Convex Hull Formation} problem is to relocate the $n$ robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this paper, we provide a framework for solving {\sc Convex Hull Formation}. We then provide four asynchronous algorithms under this framework. Key measures of the algorithms' performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first $O(\max\{n^2,D\})$ -time, $O({n^2})$ -perimeter, and $O({n^3})$ -area algorithm serves to introduce key ideas, where D is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in $O(\max\{n^{\frac{3}{2}},D\})$ time with a perimeter of $O(n^{\frac{3}{2}})$ and area of $O(n^{3})$ . We also prove lower bounds of $\Omega(n^{\frac{3}{2}})$ for time and perimeter and $\Omega(n^{3})$ for area, for any {\sc Convex Hull Formation} algorithm; i.e., our $O(\max\{n^{\frac{3}{2}},D\})-$ time algorithm is optimal in time, perimeter, and area.
This special session will report on the updated NSF/IEEE-TCPP Curriculum on Parallel and Distributed Computing released in Nov 2020 by the Center for Parallel and Distributed Computing Curriculum Development and Educational Resources (CDER). The purpose of the special session is to obtain SIGCSE community feedback on this curriculum in a highly interactive manner employing the hybrid modality and supported by a full-time CDER booth for the duration of SIGCSE. In this era of big data, cloud, and multi- and many-core systems, it is essential that the computer science (CS) and computer engineering (CE) graduates have basic skills in parallel and distributed computing (PDC). The topics are primarily organized into the areas of architecture, programming, and algorithms topics. A set of pervasive concepts that percolate across area boundaries are also identified. Version 1 of this curriculum was released in December 2012. That curriculum guideline has over 140 early adopter institutions worldwide and has been incorporated into the 2013 ACM/IEEE Computer Science curricula. This Version-II represents a major revision. The updates have focused on enhancing coverage related to the topical aspects of Big Data, Energy, and Distributed Computing. The session will also report on related CDER activities including a workshop series on a PDC institute conceptualization, developing a CE-oriented version of the curriculum, and identifying a minimal set of PDC topics aligned with ABET's exposure-level PDC requirements. The interested SIGCSE audience includes educators, authors, publishers, curriculum committee members, department chairs and administrators, professional societies, and the computing industry.
Reliable and efficient estimation of the size of a dynamically changing cluster in an IoT network is critical in its nominal operation. Most previous estimation schemes worked with relatively smaller frame size and large number of rounds. Here we propose a new estimator named \textquotedblleft Gaussian Estimator of Active Nodes,\textquotedblright (GEAN), that works with large enough frame size under which testing statistics is well approximated as a Gaussian variable, thereby requiring less number of frames, and thus less total number of channel slots to attain a desired accuracy in estimation. More specifically, the selection of the frame size is done according to Triangular Array Central Limit Theorem which also enables us to quantify the approximation error. Larger frame size helps the statistical average to converge faster to the ensemble mean of the estimator and the quantification of the approximation error helps to determine the number of rounds to keep up with the accuracy requirements. We present the analysis of our scheme under two different channel models i.e. $ \{0,1 \} $ and $ \{0,1,e \} $, whereas all previous schemes worked only under $ \{0,1 \} $ channel model. The overall performance of GEAN is better than the previously proposed schemes considering the number of slots required for estimation to achieve a given level of estimation accuracy.
Parallel and distributed computing (PDC) has become pervasive in all aspects of computing, so it is essential that students include parallelism and distribution in the computational thinking that they apply to problem solving, from the very beginning of their computing education. With all computing devices that students use currently having multiple cores as well as a GPU in many cases, many students' favorite applications use multiple cores and/or distributed processors. However, we are still teaching them to solve problems using only sequential thinking. Why? This hands-on workshop will demonstrate how easy it is to open students' eyes to exploiting concurrency in problem solving. You will participate in unplugged activities that will help students to recognize examples of PDC concepts and concurrency in the world around them. You will learn how freely available libraries can be used to exploit parallelism using shared memory parallel programming, using both plugged and unplugged activities that are usable in a classroom setting. No equipment or prior experience is required, but a laptop that can run C++, Java, and Python is recommended for following along with some code examples. The activities and discussion models have been used successfully to teach PDC concepts in early computing courses and will be available after the workshop. Participants will receive a stipend of 400 to defray their cost of registration and one-night hotel stay. The CDER center will also have a booth in the exhibition hall for additional support.