pip3 install [your options] meson
— laudatio: http://sirocco2016.hiit.fi/award/
Yamashita will give his award lecture at SIROCCO 2016 on 20 July 2016 in Helsinki, Finland
— conference web site: http://sirocco2016.hiit.fi/
Nominations are requested for the 2017 Prize for Innovation in Distributed Computing
— deadline 30 April 2016
— call for nominations: http://sirocco2016.hiit.fi/award-call/
#SIROCCO2016 #SIROCCO2017 #distributedcomputing
Call for Papers
— Submission deadline: 6 May 2016 (Friday)
— Notification of acceptance: 9 June 2016 (Thursday)
— Conference: 19–21 July 2016 (Tuesday–Thursday)
SIROCCO is devoted to the study of the interplay between communication and knowledge in multi-processor systems from both the qualitative and quantitative viewpoints.
Original papers are solicited from all areas of study of local structural knowledge and global communication and computational complexities. Among the typical areas are distributed computing, communication networks, game theory, parallel computing, social networks, mobile computing (including autonomous robots), peer to peer systems, and communication complexity.
#sirocco2016 #distributedcomputing #parallelcomputing #communicationcomplexity #information #knowledge #callforpapers #cfp
— total reductions 980, out of which teachers & researchers 295
— layoffs 570, out of which teachers & researchers 75.
Today, Aalto University did the same:
— total reductions 316, out of which teachers & researchers 175
— layoffs 188, out of which teachers & researchers 109.
("Total reductions" includes layoffs + retirements + fixed-term contracts that are not renewed.)
Today, University of Helsinki also announced their plans for introducing tuition fees. Previously, university education in Finland was entirely free for everyone, but in the future, our universities have to introduce tuition fees for non-EU students. For University of Helsinki, the fees will be 10ke–25ke.
#aaltouniversity #universityofhelsinki #universities #funding #finland
— — —
Are parallel algorithms strictly more powerful than distributed algorithms?
More precisely, we will study graph problems in the following settings:
— parallel algorithm ≈ shared memory, multiple processors (e.g. CREW PRAM model with n processors),
— distributed algorithm ≈ computer network, message passing (e.g. LOCAL model).
In a parallel algorithm, the unknown input graph is stored in the memory, while in a distributed algorithm, the unknown input graph is encoded in the structure of the computer network.
While there are plenty of superficial differences between these two models of computing, the key fundamental difference is locality. In a distributed algorithm, whatever a node outputs after T steps can only depend on the input that is within distance T of the node in the network, while parallel algorithms do not have such limitations. In a parallel algorithm, any processor can directly read any part of the input.
It is easy to come up with some artificial graph problem that exploit this freedom. Here is a simple example: binary consensus. All nodes are labeled with an input label (0 or 1), and all nodes have to produce an output label (0 or 1). All nodes have to output the same label, and the common output label has to be equal to one of the input labels.
Now it is easy to design a parallel algorithm that solves this problem in O(1) time: for each node i, processor i reads the input of node 1, writes it as the output of node i, and stops.
It is also easy to see that this problem cannot be solved in o(n) time with any distributed algorithm. To see this, consider three possible worlds:
— a path labelled with 00...0000...00,
— a path labelled with 11...1111...11,
— a path labelled with 11...1100...00.
In the first case, all nodes have to output 0, and in the second case, all nodes have to output 1. In the third case, either output is fine, but all nodes have to produce the same output. If the common output is, e.g., 0, then nodes in the middle of the part "11...11" have to distinguish between the second case (in which they output 1) and the third case (in which they output 0), and this is not possible in o(n) time. The case of the common output 1 is analogous, we will just look at the second halves.
However, this is not a typical graph problem. For typical graph problems (graph colouring, independent sets, matchings, vertex covers, dominating sets …) it is much more difficult to have (super-exponential) separations between distributed and parallel algorithms.
In our recent work "Non-Local Probes Do Not Help with Graph Problems" (with Mika Göös, Juho Hirvonen, Reut Levi, and Moti Medina) we explain why this is the case: there is a large family of graph problems for which the existence of efficient parallel algorithms directly implies an efficient distributed algorithm. Parallel algorithms could try to access any part of the input graph directly, but this is not useful. You can find the manuscript here: http://arxiv.org/abs/1512.05411
#distributedalgorithms #parallelalgorithms #distributedcomputing #parallelcomputing #locality #aaltouniversity
see http://www.podc.org/ for more information:
Monday, 25 July 2016
— Biological Distributed Algorithms (BDA)
— Distributed Cloud Computing (DCC)
— Distributed Cryptocurrencies and Consensus Ledgers (DCCL)
— Theory of Transactional Memory (WTTM)
Friday, 29 July 2016
— Adaptive Resource Management and Scheduling for Cloud Computing (ARMS-CC)
— Distributed Computing: Mixing Systems and Theory (DeMiST)
— Realistic models for Algorithms in Wireless Networks (WRAWN)
#PODC2016Chicago #distributedcomputing #distributedalgorithms #biology #cloudcomputing #cryptocurrency #transactionalmemory #wirelessnetworks
Mika Göös will give a talk on "Communication Complexity vs. Partition Numbers".
Abstract: In communication complexity, perhaps the most basic observation is that a deterministic protocol computing a function F(x,y) partitions the communication matrix of F into 2^C monochromatic rectangles, where C is the number of bits exchanged between Alice and Bob. In other words, the logarithm of the partition number (least number of monochromatic rectangles needed to partition the communication matrix) is a lower bound on communication complexity.
We show that deterministic communication complexity can be superlogarithmic in the partition number. We also obtain near-optimal deterministic lower bounds for the related Clique vs. Independent Set problem (CIS; introduced by Yannakakis in 1988) that captures a one-sided variant of the partition number. In particular, this yields new lower bounds for the log-rank conjecture. We also provide some co-nondeterministic lower bounds for CIS, which has applications to the Alon--Saks--Seymour conjecture in graph theory.
To obtain the above results, we cheat: we study analogous questions in the easy-to-understand world of decision tree complexity, and then we "lift" these results over to communication complexity using a general simulation theorem.
Joint work with Toniann Pitassi and Thomas Watson.
#helsinki #aaltouniversity #algorithms
Why the Security of USB Is Fundamentally Broken | Threat Level | WIRED
Computer users pass around USB sticks like silicon business cards. Although we know they often carry malware infections, we depend on antivi
It happened: Git 2.0 is here and it's full of goodies - Atlassian Blogs
Git 2.0 is here and it’s full of goodies. This major release of `git` has been brewing for a long time and I am excited to go on the hunt in
Barcode / QR-Code / Bluetooth / RFID / NFC / DAQ / Label Software: Barco...
News on barcode software, 2D bar code software, Bluetooth, Auto-ID, RFID, AIDC, barcode labeling, reporting software, data acquisition and s
What can be decided locally without identifiers? | Abstract Talk
Abstract. Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context
The On-Line Encyclopedia of Integer Sequences™ (OEIS™)
The On-Line Encyclopedia of Integer Sequences™ (OEIS™). Enter a sequence, word, or sequence number: Hints. Note: Advanced searches are now m
Free online dictionary definitions for learners of English ...
Free online dictionary definitions and pronunciations for learners of English from the bestselling Oxford Advanced Learner's Dictionary.