Opin vísindi
Opin vísindi er varðveislusafn vísindaefnis og doktorsritgerða í opnum aðgangi á vegum íslenskra háskóla og Landsbókasafns Íslands - Háskólabókasafns.
Opinn aðgangur að rannsóknaniðurstöðum er í samræmi við 10. gr. laga nr. 3/2003 um opinberan stuðning við vísindarannsóknir sem og kröfur innlendra og erlendra rannsóknasjóða. Markmiðið með opnum aðgangi er að niðurstöður rannsókna séu aðgengilegar sem flestum óhindrað og án endurgjalds á rafrænu formi. Vistun í varðveislusafninu er varanleg og ætlað að tryggja aðgang að vísindaefni íslenskra háskóla í opnum aðgangi um ókomna tíð. Varðveislusafnið Opin vísindi er tengt við rannsóknagáttina IRIS og rannsóknaniðurstöður í opnum aðgangi sem eru skráðar í IRIS eru um leið vistaðar og gerðar aðgengilegar til framtíðar í varðveislusafninu. Með því að safna þessu efni saman í eitt safn verður aðgangur að því einfaldur og þægilegur fyrir alla sem vilja kynna sér það og geta þannig notið þess öfluga vísindastarfs sem fram fer í háskólum landsins.
Varðveislusafnið er OpenAIRE / OpenAIREplus samhæft og samrýmist kröfum sem gerðar eru um birtingu rannsóknaniðurstaðna úr verkefnum sem styrkt eru úr evrópsku rannsóknaáætlununum FP7 og H2020.
Varðveislusafnið notar opna hugbúnaðinn DSpace.
Opinn aðgangur að rannsóknaniðurstöðum er í samræmi við 10. gr. laga nr. 3/2003 um opinberan stuðning við vísindarannsóknir sem og kröfur innlendra og erlendra rannsóknasjóða. Markmiðið með opnum aðgangi er að niðurstöður rannsókna séu aðgengilegar sem flestum óhindrað og án endurgjalds á rafrænu formi. Vistun í varðveislusafninu er varanleg og ætlað að tryggja aðgang að vísindaefni íslenskra háskóla í opnum aðgangi um ókomna tíð. Varðveislusafnið Opin vísindi er tengt við rannsóknagáttina IRIS og rannsóknaniðurstöður í opnum aðgangi sem eru skráðar í IRIS eru um leið vistaðar og gerðar aðgengilegar til framtíðar í varðveislusafninu. Með því að safna þessu efni saman í eitt safn verður aðgangur að því einfaldur og þægilegur fyrir alla sem vilja kynna sér það og geta þannig notið þess öfluga vísindastarfs sem fram fer í háskólum landsins.
Varðveislusafnið er OpenAIRE / OpenAIREplus samhæft og samrýmist kröfum sem gerðar eru um birtingu rannsóknaniðurstaðna úr verkefnum sem styrkt eru úr evrópsku rannsóknaáætlununum FP7 og H2020.
Varðveislusafnið notar opna hugbúnaðinn DSpace.
Nýlega bætt við
Electric vehicles roll-out in Europe: Towards an improved regulatory regime
(2019-10) Lazarczyk Carlson, Ewa; Baldursson, Friðrik Már; von der Fehr, Nils Henrik M.; Department of Business and Economics
Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
(2019-09) Lenzen, Christoph; Rybicki, Joel; Department of Computer Science
We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f < n/3 ongoing Byzantine faults, i.e., nodes that deviate from the protocol in an arbitrary manner. Furthermore, we assume that the local clocks of the nodes may progress at different speeds (clock drift) and communication has bounded delay. In this model, we study the pulse synchronisation problem, where the task is to guarantee that eventually all correct nodes generate well-separated local pulse events (i.e., unlabelled logical clock ticks) in a synchronised manner. Compared to prior work, we achieve exponential improvements in stabilisation time and the number of communicated bits, and give the first sublinear-time algorithm for the problem: • In the deterministic setting, the state-of-the-art solutions stabilise in time Θ(f ) and have each node broadcast Θ(f log f ) bits per time unit. We exponentially reduce the number of bits broadcasted per time unit to Θ(log f ) while retaining the same stabilisation time. • In the randomised setting, the state-of-the-art solutions stabilise in time Θ(f ) and have each node broadcast O(1) bits per time unit. We exponentially reduce the stabilisation time to polylog f while each node broadcasts polylog f bits per time unit. These results are obtained by means of a recursive approach reducing the above task of self-stabilising pulse synchronisation in the bounded-delay model to non-self-stabilising binary consensus in the synchronous model. In general, our approach introduces at most logarithmic overheads in terms of stabilisation time and broadcasted bits over the underlying consensus routine.
Near-optimal self-stabilising counting and firing squads
(2019-08-01) Lenzen, Christoph; Rybicki, Joel; Department of Computer Science
Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C> 1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f< n/ 3 , asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.
On the complexity of hazard-free circuits
(2019-08) Ikenmeyer, Christian; Komarath, Balagopal; Lenzen, Christoph; Lysikov, Vladimir; Mokhov, Andrey; Sreenivasaiah, Karteek; Department of Computer Science
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result, we establish the NP-completeness of several hazard detection problems.
Distributed distance computation and routing with small messages
(2019-04-08) Lenzen, Christoph; Patt-Shamir, Boaz; Peleg, David; Department of Computer Science
We consider shortest paths computation and related tasks from the viewpoint of network algorithms, where the n-node input graph is also the computational system: nodes represent processors and edges represent communication links, which can in each time step carry an O(log n) -bit message. We identify several basic distributed distance computation tasks that are highly useful in the design of more sophisticated algorithms and provide efficient solutions. We showcase the utility of these tools by means of several applications.
Flokkar í Opnum vísindum
Veldu flokk til að skoða.
- University of Iceland
- University of Akureyri
- Bifröst University
- Hólar University College
- IRIS
- Agricultural University of Iceland
- National and University Library of Iceland
- Iceland University of the Arts