Tue 19 Jun 2018 14:00 - 14:35 at Grand Ballroom C - Types and Correctness

Array algorithms where operations are applied to disjoint parts
of an array lend themselves well to parallelism, since parallel
threads can operate on the parts of the array without
synchronisation. However, implementing such algorithms requires
programmer diligence to verify that a thread does not
accidentally access an element of the array while another thread
is updating the same element. An off-by-one error can lead to
data-races and non-deterministic bugs which are notoriously hard
to track down.
Previous work on Kappa, a capability-based type system,
provides data-race freedom for concurrent, object-oriented
programs, even in the presence of concurrent mutating accesses
to the same object. In this paper we show how Kappa can be
extended to handle concurrent programming with arrays. By
defining array capabilities which grant access to (parts of) an
array, we can piggy-back on the existing type system in a
straightforward fashion.
We illustrate how split and merge operations integrate with
Kappa in practise by discussing the implementation of a
divide-and-conquer quicksort algorithm. We explore the semantics
of the Kappa extension by using a simple imperative calculus
and sketch on how it could be implemented efficiently.

Tue 19 Jun
Times are displayed in time zone: (GMT-04:00) Eastern Time (US & Canada) change

14:00 - 15:45: ARRAY 2018 - Types and Correctness at Grand Ballroom C
ARRAY-2018-papers14:00 - 14:35
Beatrice ÅkerblomStockholm University, Elias CastegrenUppsala University, Tobias WrigstadUppsala University
ARRAY-2018-papers14:35 - 15:10
Justin SlepakNortheastern University, Panagiotis ManoliosNortheastern University, Olin ShiversNortheastern University, USA
ARRAY-2018-papers15:10 - 15:45
Magne HaveraaenUniversity of Bergen, Norway