Navigation

Contact

EMail: scare@uol.deurmg

DIRECTOR

Prof. Dr. Ernst-Rüdiger Olderog,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

oldsperovfg@im7unformatik.unrf8ji-olvehf7denburg.denp

COODINATOR

Ira Wempe,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

irafjyvq.wempe@infok6vrmatik.uniuyo/-olyjdenbkcrurgkj.de

Parameterized Verification of Asynchronous Shared-Memory Systems

Prof. Dr. Javier Esparza

Abstract:

We characterize the complexity of the safety verification problem for parameterized systems consisting of a leader process and arbitrarily many anonymous and identical contributors. Processes communicate through a shared, bounded-value register. While each operation on the register is atomic, there is no synchronization primitive to execute a sequence of operations atomically. The model is inspired by distributed algorithms implemented on sensor networks.We analyse the complexity of the safety verification problem when processes are modeled by finite-state machines, pushdown machines, and Turing machines. Our proofs use combinatorial characterizations of computations in the model, and in case of pushdown-systems, some novel language-theoretic constructions of independent interest.

(Joint work with  Rupak Majumdar and Pierre Ganty)

Olivertju Tj7rheel (olivegor.w7theel@uegn/ol.de) (Changed: 2020-01-23)