LEADER 03577nam 2200433 450 001 9910510500803321 005 20230824174006.0 024 7 $a10.1145/3323165 035 $a(CKB)5280000000243336 035 $a(NjHacI)995280000000243336 035 $a(EXLCZ)995280000000243336 100 $a20230824d2019 uy 0 101 0 $aeng 135 $aur||||||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 00$a31st ACM Symposium on Parallelism in Algorithms and Architectures /$fChristian Scheideler, Petra Berenbrink, editors 210 1$aNew York, NY :$cAssociation for Computing Machinery,$d2019. 215 $a1 online resource (410 pages) $cillustrations 225 1 $aACM international conference proceedings series 311 $a1-4503-6184-6 330 $aIt is our great pleasure to welcome you to the 31st ACM Symposium on Parallelism in Algorithms and Architectures - SPAA 2019. The goal of SPAA is to develop a deeper understanding of parallelism in all its forms, bringing together the theory and practice of parallel computing. These days the applications for parallel computing include all areas of information technology; desktops, notebook systems and smart phones have CPUs which are equipped with multiple cores. An understanding of parallel computing is becoming essential knowledge for every IT professional. Over the last several years, the study of parallelism has expanded into new areas, including new models of parallel computation, new techniques for managing parallelism, and new types of parallel systems. These increasingly important topics are also represented at SPAA this year. This year, the call for papers attracted 109 submissions. The program committee accepted 34 as regular papers (an acceptance rate of only 35%) and 11 as brief announcements. The keynote talk is given by Guy Even, Tel-Aviv University, Israel. The best paper award for SPAA 2017 is awarded to: Faith Ellen, Barun Gorain, Avery Miller and Andrej Pelc: Constant-Length Labeling Schemes for Deterministic Radio Broadcast. The authors consider broadcast in radio networks, modeled as simple undirected connected graphs with a designated source. The nodes communicate in synchronous rounds and a node receives a message from a neighbor only if the neighbor is the only one that transmits in the round. It is well known that deterministic broadcast is impossible if nodes of the network do not have any labels. On the other hand, if all nodes have distinct labels, then broadcast can be carried out trivially in a round-robin fashion. The authors ask the natural question if very short labels are sufficient for broadcast. They show that every radio network can be labeled with 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. 410 0$aACM international conference proceedings series. 606 $aComputer algorithms$vCongresses 606 $aComputer architecture$vCongresses 606 $aParallel processing (Electronic computers)$vCongresses 615 0$aComputer algorithms 615 0$aComputer architecture 615 0$aParallel processing (Electronic computers) 676 $a004.015118 702 $aScheideler$b Christian 702 $aBerenbrink$b Petra 801 0$bNjHacI 801 1$bNjHacl 906 $aBOOK 912 $a9910510500803321 996 $a31st ACM Symposium on Parallelism in Algorithms and Architectures$92436276 997 $aUNINA