---
_id: '2955'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on finite graphs with reachability
objectives where the first player tries to ensure a target state to be visited
almost-surely (i.e., with probability 1), or positively (i.e., with positive probability),
no matter the strategy of the second player. We classify such games according
to the information and the power of randomization available to the players. On
the basis of information, the game can be one-sided with either (a) player 1,
or (b) player 2 having partial observation (and the other player has perfect observation),
or two-sided with (c) both players having partial observation. On the basis of
randomization, the players (a) may not be allowed to use randomization (pure strategies),
or (b) may choose a probability distribution over actions but the actual random
choice is external and not visible to the player (actions invisible), or (c) may
use full randomization. Our main results for pure strategies are as follows. (1)
For one-sided games with player 1 having partial observation we show that (in
contrast to full randomized strategies) belief-based (subset-construction based)
strategies are not sufficient, and we present an exponential upper bound on memory
both for almostsure and positive winning strategies; we show that the problem
of deciding the existence of almost-sure and positive winning strategies for player
1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation
we show that non-elementary memory is both necessary and sufficient for both almost-sure
and positive winning strategies. (3) We show that for the general (two-sided)
case finite-memory strategies are sufficient for both positive and almost-sure
winning, and at least non-elementary memory is required. We establish the equivalence
of the almost-sure winning problems for pure strategies and for randomized strategies
with actions invisible. Our equivalence result exhibits serious flaws in previous
results of the literature: we show a non-elementary memory lower bound for almost-sure
winning whereas an exponential upper bound was previously claimed.'
acknowledgement: 'This work was partially supported by FWF Grant No P 23499-N23, FWF
NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award.'
article_number: '6280436'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when
belief fails. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on
Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.28'
apa: 'Chatterjee, K., & Doyen, L. (2012). Partial-observation stochastic games:
How to win when belief fails. In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.28'
chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” In Proceedings of the 2012 27th Annual
ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.28.'
ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to
win when belief fails,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, Dubrovnik, Croatia, 2012.'
ista: 'Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to
win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.'
mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, 6280436, IEEE, 2012, doi:10.1109/LICS.2012.28.'
short: K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: Dubrovnik, Croatia
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:32Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:43Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.28
ec_funded: 1
external_id:
arxiv:
- '1107.2141'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2141
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3771'
quality_controlled: '1'
related_material:
record:
- id: '2211'
relation: later_version
status: public
- id: '5381'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3341'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on a finite state space for
an infinite number of rounds. The games are concurrent: in each round, the two
players (player 1 and player 2) choose their moves independently and simultaneously;
the current state and the two moves determine a probability distribution over
the successor states. We also consider the important special case of turn-based
stochastic games where players make moves in turns, rather than concurrently.
We study concurrent games with \omega-regular winning conditions specified as
parity objectives. The value for player 1 for a parity objective is the maximal
probability with which the player can guarantee the satisfaction of the objective
against all strategies of the opponent. We study the problem of continuity and
robustness of the value function in concurrent and turn-based stochastic parity
gameswith respect to imprecision in the transition probabilities. We present quantitative
bounds on the difference of the value function (in terms of the imprecision of
the transition probabilities) and show the value continuity for structurally equivalent
concurrent games (two games are structurally equivalent if the support of the
transition function is same and the probabilities differ). We also show robustness
of optimal strategies for structurally equivalent turn-based stochastic parity
games. Finally we show that the value continuity property breaks without the structurally
equivalent assumption (even for Markov chains) and show that our quantitative
bound is asymptotically optimal. Hence our results are tight (the assumption is
both necessary and sufficient) and optimal (our quantitative bound is asymptotically
optimal).'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Robustness of structurally equivalent concurrent parity games.
In: Vol 7213. Springer; 2012:270-285. doi:10.1007/978-3-642-28729-9_18'
apa: 'Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity
games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software
Science and Computation Structures, Tallinn, Estonia: Springer. https://doi.org/10.1007/978-3-642-28729-9_18'
chicago: Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent
Parity Games,” 7213:270–85. Springer, 2012. https://doi.org/10.1007/978-3-642-28729-9_18.
ieee: 'K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,”
presented at the FoSSaCS: Foundations of Software Science and Computation Structures,
Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.'
ista: 'Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity
games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS,
vol. 7213, 270–285.'
mla: Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent
Parity Games. Vol. 7213, Springer, 2012, pp. 270–85, doi:10.1007/978-3-642-28729-9_18.
short: K. Chatterjee, in:, Springer, 2012, pp. 270–285.
conference:
end_date: 2012-04-01
location: Tallinn, Estonia
name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
start_date: 2012-03-24
date_created: 2018-12-11T12:02:46Z
date_published: 2012-03-22T00:00:00Z
date_updated: 2023-02-23T12:23:46Z
day: '22'
department:
- _id: KrCh
doi: 10.1007/978-3-642-28729-9_18
ec_funded: 1
external_id:
arxiv:
- '1107.2009'
intvolume: ' 7213'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2009
month: '03'
oa: 1
oa_version: Preprint
page: 270 - 285
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3284'
quality_controlled: '1'
related_material:
record:
- id: '5382'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Robustness of structurally equivalent concurrent parity games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7213
year: '2012'
...
---
_id: '2957'
abstract:
- lang: eng
text: 'We consider probabilistic automata on infinite words with acceptance defined
by parity conditions. We consider three qualitative decision problems: (i) the
positive decision problem asks whether there is a word that is accepted with positive
probability; (ii) the almost decision problem asks whether there is a word that
is accepted with probability 1; and (iii) the limit decision problem asks whether
words are accepted with probability arbitrarily close to 1. We unify and generalize
several decidability results for probabilistic automata over infinite words, and
identify a robust (closed under union and intersection) subclass of probabilistic
automata for which all the qualitative decision problems are decidable for parity
conditions. We also show that if the input words are restricted to lasso shape
(regular) words, then the positive and almost problems are decidable for all probabilistic
automata with parity conditions. For most decidable problems we show an optimal
PSPACE-complete complexity bound.'
article_number: '6280437'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: 'Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite
words. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic
in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.29'
apa: 'Chatterjee, K., & Tracol, M. (2012). Decidable problems for probabilistic
automata on infinite words. In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. Dubrovnik, Croatia : IEEE. https://doi.org/10.1109/LICS.2012.29'
chicago: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic
Automata on Infinite Words.” In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.29.
ieee: K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata
on infinite words,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, Dubrovnik, Croatia , 2012.
ista: 'Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata
on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic
in Computer Science. LICS: Logic in Computer Science, 6280437.'
mla: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic
Automata on Infinite Words.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, 6280437, IEEE, 2012, doi:10.1109/LICS.2012.29.
short: K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: 'Dubrovnik, Croatia '
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:33Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:51Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.29
ec_funded: 1
external_id:
arxiv:
- '1107.2091'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1107.2091
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3769'
quality_controlled: '1'
related_material:
record:
- id: '5384'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Decidable problems for probabilistic automata on infinite words
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3249'
abstract:
- lang: eng
text: Boolean notions of correctness are formalized by preorders on systems. Quantitative
measures of correctness can be formalized by real-valued distance functions between
systems, where the distance between implementation and specification provides
a measure of "fit" or "desirability". We extend the simulation
preorder to the quantitative setting by making each player of a simulation game
pay a certain price for her choices. We use the resulting games with quantitative
objectives to define three different simulation distances. The correctness distance
measures how much the specification must be changed in order to be satisfied by
the implementation. The coverage distance measures how much the implementation
restricts the degrees of freedom offered by the specification. The robustness
distance measures how much a system can deviate from the implementation description
without violating the specification. We consider these distances for safety as
well as liveness specifications. The distances can be computed in polynomial time
for safety specifications, and for liveness specifications given by weak fairness
constraints. We show that the distance functions satisfy the triangle inequality,
that the distance between two systems does not increase under parallel composition
with a third system, and that the distance between two systems can be bounded
from above and below by distances between abstractions of the two systems. These
properties suggest that our simulation distances provide an appropriate basis
for a quantitative theory of discrete systems. We also demonstrate how the robustness
distance can be used to measure how many transmission errors are tolerated by
error correcting codes.
acknowledgement: This work was partially supported by the ERC Advanced Grant QUAREM,
the FWF NFN Grant S11402-N23 (RiSE), the European Union project COMBEST and the
European Network of Excellence Artist Design.
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: Cerny P, Henzinger TA, Radhakrishna A. Simulation distances. Theoretical
Computer Science. 2012;413(1):21-35. doi:10.1016/j.tcs.2011.08.002
apa: Cerny, P., Henzinger, T. A., & Radhakrishna, A. (2012). Simulation distances.
Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2011.08.002
chicago: Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Simulation Distances.”
Theoretical Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2011.08.002.
ieee: P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Simulation distances,” Theoretical
Computer Science, vol. 413, no. 1. Elsevier, pp. 21–35, 2012.
ista: Cerny P, Henzinger TA, Radhakrishna A. 2012. Simulation distances. Theoretical
Computer Science. 413(1), 21–35.
mla: Cerny, Pavol, et al. “Simulation Distances.” Theoretical Computer Science,
vol. 413, no. 1, Elsevier, 2012, pp. 21–35, doi:10.1016/j.tcs.2011.08.002.
short: P. Cerny, T.A. Henzinger, A. Radhakrishna, Theoretical Computer Science 413
(2012) 21–35.
date_created: 2018-12-11T12:02:15Z
date_published: 2012-01-06T00:00:00Z
date_updated: 2023-02-23T12:24:04Z
day: '06'
department:
- _id: ToHe
doi: 10.1016/j.tcs.2011.08.002
ec_funded: 1
intvolume: ' 413'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 21 - 35
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '3408'
pubrep_id: '42'
quality_controlled: '1'
related_material:
record:
- id: '4393'
relation: earlier_version
status: public
- id: '5389'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Simulation distances
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 413
year: '2012'
...
---
_id: '3124'
abstract:
- lang: eng
text: "We consider the problem of inference in a graphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pairwise terms
over a discretized domain. This allows the use of techniques originally developed
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can outperform the Bethe approximation. We also establish a link between the Bethe
free energy and submodular functions.\r\n"
alternative_title:
- Inferning 2012
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy
minimization. In: ICML; 2012.'
apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. Presented at the ICML: International Conference
on Machine Learning, Edinburgh, Scotland: ICML.'
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating
Marginals Using Discrete Energy Minimization.” ICML, 2012.
ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete
energy minimization,” presented at the ICML: International Conference on Machine
Learning, Edinburgh, Scotland, 2012.'
ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization. ICML: International Conference on Machine Learning, Inferning
2012, .'
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
ICML, 2012.
short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
conference:
end_date: 2012-07-01
location: Edinburgh, Scotland
name: 'ICML: International Conference on Machine Learning'
start_date: 2012-06-26
date_created: 2018-12-11T12:01:31Z
date_published: 2012-06-30T00:00:00Z
date_updated: 2023-02-23T12:24:24Z
day: '30'
ddc:
- '000'
department:
- _id: ChLa
- _id: VlKo
file:
- access_level: open_access
checksum: 3d0d4246548c736857302aadb2ff5d15
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:34Z
date_updated: 2020-07-14T12:46:00Z
file_id: '4889'
file_name: IST-2016-565-v1+1_DM-inferning2012.pdf
file_size: 305836
relation: main_file
file_date_updated: 2020-07-14T12:46:00Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: ICML
publist_id: '3575'
pubrep_id: '565'
quality_controlled: '1'
related_material:
record:
- id: '5396'
relation: later_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5396'
abstract:
- lang: eng
text: We consider the problem of inference in agraphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pair-wise terms
over a discretized domain. This allows the use of techniques originally devel-oped
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can out-perform the Bethe approximation. We also establish a link between the
Bethe free energy and submodular functions.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete
Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003
apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating
Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.
ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete
energy minimization. IST Austria, 2012.
ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization, IST Austria, 13p.
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.
short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete
Energy Minimization, IST Austria, 2012.
date_created: 2018-12-12T11:39:06Z
date_published: 2012-07-23T00:00:00Z
date_updated: 2023-02-23T11:13:22Z
day: '23'
ddc:
- '000'
department:
- _id: VlKo
- _id: ChLa
doi: 10.15479/AT:IST-2012-0003
file:
- access_level: open_access
checksum: 7e0ba85ad123b13223aaf6cdde2d288c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:29Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5490'
file_name: IST-2012-0003_IST-2012-0003.pdf
file_size: 618744
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '13'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '36'
related_material:
record:
- id: '3124'
relation: earlier_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5398'
abstract:
- lang: eng
text: This document is created as a part of the project “Repository for Research
Data on IST Austria”. It summarises the actual state of research data at IST Austria,
based on survey results. It supports the choice of appropriate software, which
would best fit the requirements of their users, the researchers.
author:
- first_name: Jana
full_name: Porsche, Jana
id: 3252EDC2-F248-11E8-B48F-1D18A9856A87
last_name: Porsche
citation:
ama: Porsche J. Actual State of Research Data @ ISTAustria. IST Austria;
2012.
apa: Porsche, J. (2012). Actual state of research data @ ISTAustria. IST
Austria.
chicago: Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria,
2012.
ieee: J. Porsche, Actual state of research data @ ISTAustria. IST Austria,
2012.
ista: Porsche J. 2012. Actual state of research data @ ISTAustria, IST Austria,p.
mla: Porsche, Jana. Actual State of Research Data @ ISTAustria. IST Austria,
2012.
short: J. Porsche, Actual State of Research Data @ ISTAustria, IST Austria, 2012.
date_created: 2018-12-12T11:39:06Z
date_published: 2012-11-12T00:00:00Z
date_updated: 2020-07-14T23:04:49Z
day: '12'
ddc:
- '020'
department:
- _id: E-Lib
file:
- access_level: open_access
checksum: e0a7c041eea1ca4b70ab6f9ec5177f4e
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:11Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5472'
file_name: IST-2012-103-v1+1_Actual_state_of_research_data_@_IST_Austria.pdf
file_size: 238544
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
pubrep_id: '103'
status: public
title: Actual state of research data @ ISTAustria
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5839'
abstract:
- lang: eng
text: "Canny's edge detection algorithm is a classical and robust method for edge
detection in gray-scale images. The two \r\nsignificant features of this method
are introduction of NMS (Non-Maximum Suppression) and double thresholding of \r\nthe
\ gradient image. Due to poor illumination, the region boundaries in
\ an image may become vague, creating \r\nuncertainties in the gradient
\ image. In this paper, we have proposed an algorithm based on the
\ concept of type-2 fuzzy sets to handle uncertainties that automatically
\ selects the threshold values needed to segment the gradient image using
classical Canny’s edge detection algorithm. The results show that our algorithm
works significantly well on different benchmark images as well as medical images
(hand radiography images). "
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Jaya
full_name: Sil, Jaya
last_name: Sil
citation:
ama: Biswas R, Sil J. An Improved Canny Edge Detection Algorithm Based on Type-2
Fuzzy Sets. Procedia Technology. 2012;4:820-824. doi:10.1016/j.protcy.2012.05.134
apa: Biswas, R., & Sil, J. (2012). An Improved Canny Edge Detection Algorithm
Based on Type-2 Fuzzy Sets. Procedia Technology. Elsevier. https://doi.org/10.1016/j.protcy.2012.05.134
chicago: Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm
Based on Type-2 Fuzzy Sets.” Procedia Technology. Elsevier, 2012. https://doi.org/10.1016/j.protcy.2012.05.134.
ieee: R. Biswas and J. Sil, “An Improved Canny Edge Detection Algorithm Based on
Type-2 Fuzzy Sets,” Procedia Technology, vol. 4. Elsevier, pp. 820–824,
2012.
ista: Biswas R, Sil J. 2012. An Improved Canny Edge Detection Algorithm Based on
Type-2 Fuzzy Sets. Procedia Technology. 4, 820–824.
mla: Biswas, Ranita, and Jaya Sil. “An Improved Canny Edge Detection Algorithm Based
on Type-2 Fuzzy Sets.” Procedia Technology, vol. 4, Elsevier, 2012, pp.
820–24, doi:10.1016/j.protcy.2012.05.134.
short: R. Biswas, J. Sil, Procedia Technology 4 (2012) 820–824.
date_created: 2019-01-17T11:54:21Z
date_published: 2012-05-01T00:00:00Z
date_updated: 2021-01-12T08:03:43Z
day: '01'
ddc:
- '000'
doi: 10.1016/j.protcy.2012.05.134
extern: '1'
file:
- access_level: open_access
checksum: ba0185986b151d8c11201f48cd505ceb
content_type: application/pdf
creator: dernst
date_created: 2019-01-21T07:28:06Z
date_updated: 2020-07-14T12:47:12Z
file_id: '5863'
file_name: 2012_Procedia_Biswas.pdf
file_size: 305426
relation: main_file
file_date_updated: 2020-07-14T12:47:12Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '05'
oa: 1
oa_version: Published Version
page: 820-824
publication: Procedia Technology
publication_identifier:
issn:
- 2212-0173
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2012'
...
---
_id: '596'
abstract:
- lang: eng
text: The human Mediator complex controls RNA polymerase II (pol II) function in
ways that remain incompletely understood. Activator-Mediator binding alters Mediator
structure, and these activator-induced structural shifts appear to play key roles
in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed
that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly
in which Mediator was bound to the activation domain of viral protein 16 (VP16).
Whereas TFIIF was shown to be important for orienting pol II within this assembly,
the potential role of the activator was not assessed. To determine how activator
binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF
complexes in which Mediator was not bound to an activator. Cryo-EM analysis of
this assembly, coupled with pol II crystal structure docking, revealed that pol
II binds Mediator at the same general location; however, in contrast to VP16-bound
Mediator, pol II does not appear to stably orient in the absence of an activator.
Variability in pol II orientation might be important mechanistically, perhaps
to enable sense and antisense transcription at human promoters. Because Mediator
interacts extensively with pol II, these results suggest that Mediator structural
shifts induced by activator binding help stably orient pol II prior to transcription
initiation.
article_processing_charge: No
author:
- first_name: Carrie A
full_name: Bernecky, Carrie A
id: 2CB9DFE2-F248-11E8-B48F-1D18A9856A87
last_name: Bernecky
orcid: 0000-0003-0893-7036
- first_name: Dylan
full_name: Taatjes, Dylan
last_name: Taatjes
citation:
ama: Bernecky C, Taatjes D. Activator-mediator binding stabilizes RNA polymerase
II orientation within the human mediator-RNA polymerase II-TFIIF assembly. Journal
of Molecular Biology. 2012;417(5):387-394. doi:10.1016/j.jmb.2012.02.014
apa: Bernecky, C., & Taatjes, D. (2012). Activator-mediator binding stabilizes
RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF
assembly. Journal of Molecular Biology. Elsevier. https://doi.org/10.1016/j.jmb.2012.02.014
chicago: Bernecky, Carrie, and Dylan Taatjes. “Activator-Mediator Binding Stabilizes
RNA Polymerase II Orientation within the Human Mediator-RNA Polymerase II-TFIIF
Assembly.” Journal of Molecular Biology. Elsevier, 2012. https://doi.org/10.1016/j.jmb.2012.02.014.
ieee: C. Bernecky and D. Taatjes, “Activator-mediator binding stabilizes RNA polymerase
II orientation within the human mediator-RNA polymerase II-TFIIF assembly,” Journal
of Molecular Biology, vol. 417, no. 5. Elsevier, pp. 387–394, 2012.
ista: Bernecky C, Taatjes D. 2012. Activator-mediator binding stabilizes RNA polymerase
II orientation within the human mediator-RNA polymerase II-TFIIF assembly. Journal
of Molecular Biology. 417(5), 387–394.
mla: Bernecky, Carrie, and Dylan Taatjes. “Activator-Mediator Binding Stabilizes
RNA Polymerase II Orientation within the Human Mediator-RNA Polymerase II-TFIIF
Assembly.” Journal of Molecular Biology, vol. 417, no. 5, Elsevier, 2012,
pp. 387–94, doi:10.1016/j.jmb.2012.02.014.
short: C. Bernecky, D. Taatjes, Journal of Molecular Biology 417 (2012) 387–394.
date_created: 2018-12-11T11:47:24Z
date_published: 2012-04-13T00:00:00Z
date_updated: 2021-01-12T08:05:21Z
day: '13'
doi: 10.1016/j.jmb.2012.02.014
extern: '1'
intvolume: ' 417'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4582759/
month: '04'
oa: 1
oa_version: None
page: 387 - 394
publication: Journal of Molecular Biology
publication_status: published
publisher: Elsevier
publist_id: '7208'
status: public
title: Activator-mediator binding stabilizes RNA polymerase II orientation within
the human mediator-RNA polymerase II-TFIIF assembly
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 417
year: '2012'
...
---
_id: '6136'
abstract:
- lang: eng
text: Tonic receptors convey stimulus duration and intensity and are implicated
in homeostatic control. However, how tonic homeostatic signals are generated and
how they reconfigure neural circuits and modify animal behavior is poorly understood.
Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors
that continuously signal ambient [O2] to set the animal's behavioral state. Sustained
signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels,
the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked
continuous neuropeptide release, which helps elicit the enduring behavioral state
associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream
neural circuits, including the hub interneuron RMG. O2 receptors evoked similar
locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt.
However, a phasic component of the URX receptors' response to high d[O2]/dt, as
well as tonic-to-phasic transformations in downstream interneurons, enabled transient
reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic
signals can generate both transient and enduring behavioral change.
author:
- first_name: Karl Emanuel
full_name: Busch, Karl Emanuel
last_name: Busch
- first_name: Patrick
full_name: Laurent, Patrick
last_name: Laurent
- first_name: Zoltan
full_name: Soltesz, Zoltan
last_name: Soltesz
- first_name: Robin Joseph
full_name: Murphy, Robin Joseph
last_name: Murphy
- first_name: Olivier
full_name: Faivre, Olivier
last_name: Faivre
- first_name: Berthold
full_name: Hedwig, Berthold
last_name: Hedwig
- first_name: Martin
full_name: Thomas, Martin
last_name: Thomas
- first_name: Heather L
full_name: Smith, Heather L
last_name: Smith
- first_name: Mario
full_name: de Bono, Mario
id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87
last_name: de Bono
orcid: 0000-0001-8347-0443
citation:
ama: Busch KE, Laurent P, Soltesz Z, et al. Tonic signaling from O2 sensors sets
neural circuit activity and behavioral state. Nature Neuroscience. 2012;15(4):581-591.
doi:10.1038/nn.3061
apa: Busch, K. E., Laurent, P., Soltesz, Z., Murphy, R. J., Faivre, O., Hedwig,
B., … de Bono, M. (2012). Tonic signaling from O2 sensors sets neural circuit
activity and behavioral state. Nature Neuroscience. Springer Nature. https://doi.org/10.1038/nn.3061
chicago: Busch, Karl Emanuel, Patrick Laurent, Zoltan Soltesz, Robin Joseph Murphy,
Olivier Faivre, Berthold Hedwig, Martin Thomas, Heather L Smith, and Mario de
Bono. “Tonic Signaling from O2 Sensors Sets Neural Circuit Activity and Behavioral
State.” Nature Neuroscience. Springer Nature, 2012. https://doi.org/10.1038/nn.3061.
ieee: K. E. Busch et al., “Tonic signaling from O2 sensors sets neural circuit
activity and behavioral state,” Nature Neuroscience, vol. 15, no. 4. Springer
Nature, pp. 581–591, 2012.
ista: Busch KE, Laurent P, Soltesz Z, Murphy RJ, Faivre O, Hedwig B, Thomas M, Smith
HL, de Bono M. 2012. Tonic signaling from O2 sensors sets neural circuit activity
and behavioral state. Nature Neuroscience. 15(4), 581–591.
mla: Busch, Karl Emanuel, et al. “Tonic Signaling from O2 Sensors Sets Neural Circuit
Activity and Behavioral State.” Nature Neuroscience, vol. 15, no. 4, Springer
Nature, 2012, pp. 581–91, doi:10.1038/nn.3061.
short: K.E. Busch, P. Laurent, Z. Soltesz, R.J. Murphy, O. Faivre, B. Hedwig, M.
Thomas, H.L. Smith, M. de Bono, Nature Neuroscience 15 (2012) 581–591.
date_created: 2019-03-20T14:23:30Z
date_published: 2012-03-04T00:00:00Z
date_updated: 2021-01-12T08:06:17Z
day: '04'
doi: 10.1038/nn.3061
extern: '1'
external_id:
pmid:
- '22388961'
intvolume: ' 15'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3564487/
month: '03'
oa: 1
oa_version: Submitted Version
page: 581-591
pmid: 1
publication: Nature Neuroscience
publication_identifier:
issn:
- 1097-6256
- 1546-1726
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Tonic signaling from O2 sensors sets neural circuit activity and behavioral
state
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2012'
...
---
_id: '6746'
abstract:
- lang: eng
text: This paper proposes a novel cooperative approach for two-hop amplify-and-forward
(A&F) relaying that exploits both the signal forwarded by the relay and the one
directly transmitted by the source in impulse-radio ultra-wideband (IR-UWB) systems.
Specifically, we focus on a non-coherent setup employing a double-differential
encoding scheme at the source node and a single differential demodulation at the
relay and destination. The log-likelihood ratio based decision rule is derived
at the destination node. A semi-analytical power allocation strategy is presented
by evaluating a closed-form expression for the effective signal to noise ratio
(SNR) at the destination, which is maximized by exhaustive search. Numerical simulations
show that the proposed system outperforms both the direct transmission with single
differential encoding and the non-cooperative multi-hop approach in different
scenarios.
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Qi
full_name: Zhou, Qi
last_name: Zhou
- first_name: Xiaoli
full_name: Ma, Xiaoli
last_name: Ma
- first_name: Vincenzo
full_name: Lottici, Vincenzo
last_name: Lottici
citation:
ama: 'Mondelli M, Zhou Q, Ma X, Lottici V. A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems. In: 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE; 2012:2905-2908.
doi:10.1109/icassp.2012.6288524'
apa: 'Mondelli, M., Zhou, Q., Ma, X., & Lottici, V. (2012). A cooperative approach
for amplify-and-forward differential transmitted reference IR-UWB relay systems.
In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP) (pp. 2905–2908). Kyoto, Japan: IEEE. https://doi.org/10.1109/icassp.2012.6288524'
chicago: Mondelli, Marco, Qi Zhou, Xiaoli Ma, and Vincenzo Lottici. “A Cooperative
Approach for Amplify-and-Forward Differential Transmitted Reference IR-UWB Relay
Systems.” In 2012 IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP), 2905–8. IEEE, 2012. https://doi.org/10.1109/icassp.2012.6288524.
ieee: M. Mondelli, Q. Zhou, X. Ma, and V. Lottici, “A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems,” in 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP), Kyoto, Japan,
2012, pp. 2905–2908.
ista: 'Mondelli M, Zhou Q, Ma X, Lottici V. 2012. A cooperative approach for amplify-and-forward
differential transmitted reference IR-UWB relay systems. 2012 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP). ICASSP: International
Conference on Acoustics, Speech and Signal Processing, 2905–2908.'
mla: Mondelli, Marco, et al. “A Cooperative Approach for Amplify-and-Forward Differential
Transmitted Reference IR-UWB Relay Systems.” 2012 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–08,
doi:10.1109/icassp.2012.6288524.
short: M. Mondelli, Q. Zhou, X. Ma, V. Lottici, in:, 2012 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2012, pp. 2905–2908.
conference:
end_date: 2012-03-30
location: Kyoto, Japan
name: 'ICASSP: International Conference on Acoustics, Speech and Signal Processing'
start_date: 2012-03-25
date_created: 2019-07-31T09:14:48Z
date_published: 2012-07-31T00:00:00Z
date_updated: 2021-01-12T08:08:49Z
day: '31'
doi: 10.1109/icassp.2012.6288524
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 2905-2908
publication: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP)
publication_identifier:
issn:
- 1520-6149
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: A cooperative approach for amplify-and-forward differential transmitted reference
IR-UWB relay systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '7074'
abstract:
- lang: eng
text: The Seebeck coefficients, electrical resistivities, total thermal conductivities,
and magnetization are reported for temperatures between 5 and 350 K for n-type
Bi0.88Sb0.12 nano-composite alloys made by Ho-doping at the 0, 1, and 3 % atomic
levels. The alloys were prepared using a dc hot-pressing method, and are shown
to be single phase for both Ho contents with grain sizes on the average of 900
nm. We find the parent compound has a maximum of ZT = 0.28 at 231 K, while doping
1 % Ho increases the maximum ZT to 0.31 at 221 K and the 3 % doped sample suppresses
the maximum ZT = 0.24 at a temperature of 260 K.
article_processing_charge: No
article_type: original
author:
- first_name: K. C.
full_name: Lukas, K. C.
last_name: Lukas
- first_name: G.
full_name: Joshi, G.
last_name: Joshi
- first_name: Kimberly A
full_name: Modic, Kimberly A
id: 13C26AC0-EB69-11E9-87C6-5F3BE6697425
last_name: Modic
orcid: 0000-0001-9760-3147
- first_name: Z. F.
full_name: Ren, Z. F.
last_name: Ren
- first_name: C. P.
full_name: Opeil, C. P.
last_name: Opeil
citation:
ama: Lukas KC, Joshi G, Modic KA, Ren ZF, Opeil CP. Thermoelectric properties of
Ho-doped Bi0.88Sb0.12. Journal of Materials Science. 2012;47(15):5729-5734.
doi:10.1007/s10853-012-6463-6
apa: Lukas, K. C., Joshi, G., Modic, K. A., Ren, Z. F., & Opeil, C. P. (2012).
Thermoelectric properties of Ho-doped Bi0.88Sb0.12. Journal of Materials Science.
Springer Nature. https://doi.org/10.1007/s10853-012-6463-6
chicago: Lukas, K. C., G. Joshi, Kimberly A Modic, Z. F. Ren, and C. P. Opeil. “Thermoelectric
Properties of Ho-Doped Bi0.88Sb0.12.” Journal of Materials Science. Springer
Nature, 2012. https://doi.org/10.1007/s10853-012-6463-6.
ieee: K. C. Lukas, G. Joshi, K. A. Modic, Z. F. Ren, and C. P. Opeil, “Thermoelectric
properties of Ho-doped Bi0.88Sb0.12,” Journal of Materials Science, vol.
47, no. 15. Springer Nature, pp. 5729–5734, 2012.
ista: Lukas KC, Joshi G, Modic KA, Ren ZF, Opeil CP. 2012. Thermoelectric properties
of Ho-doped Bi0.88Sb0.12. Journal of Materials Science. 47(15), 5729–5734.
mla: Lukas, K. C., et al. “Thermoelectric Properties of Ho-Doped Bi0.88Sb0.12.”
Journal of Materials Science, vol. 47, no. 15, Springer Nature, 2012, pp.
5729–34, doi:10.1007/s10853-012-6463-6.
short: K.C. Lukas, G. Joshi, K.A. Modic, Z.F. Ren, C.P. Opeil, Journal of Materials
Science 47 (2012) 5729–5734.
date_created: 2019-11-19T13:36:54Z
date_published: 2012-08-01T00:00:00Z
date_updated: 2021-01-12T08:11:43Z
day: '01'
doi: 10.1007/s10853-012-6463-6
extern: '1'
intvolume: ' 47'
issue: '15'
language:
- iso: eng
month: '08'
oa_version: None
page: 5729-5734
publication: Journal of Materials Science
publication_identifier:
eissn:
- 1573-4803
issn:
- 0022-2461
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Thermoelectric properties of Ho-doped Bi0.88Sb0.12
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2012'
...
---
_id: '7308'
abstract:
- lang: eng
text: 'Carbon has been used widely as the basis of porous cathodes for nonaqueous
Li–O2 cells. However, the stability of carbon and the effect of carbon on electrolyte
decomposition in such cells are complex and depend on the hydrophobicity/hydrophilicity
of the carbon surface. Analyzing carbon cathodes, cycled in Li–O2 cells between
2 and 4 V, using acid treatment and Fenton’s reagent, and combined with differential
electrochemical mass spectrometry and FTIR, demonstrates the following: Carbon
is relatively stable below 3.5 V (vs Li/Li+) on discharge or charge, especially
so for hydrophobic carbon, but is unstable on charging above 3.5 V (in the presence
of Li2O2), oxidatively decomposing to form Li2CO3. Direct chemical reaction with
Li2O2 accounts for only a small proportion of the total carbon decomposition on
cycling. Carbon promotes electrolyte decomposition during discharge and charge
in a Li–O2 cell, giving rise to Li2CO3 and Li carboxylates (DMSO and tetraglyme
electrolytes). The Li2CO3 and Li carboxylates present at the end of discharge
and those that form on charge result in polarization on the subsequent charge.
Li2CO3 (derived from carbon and from the electrolyte) as well as the Li carboxylates
(derived from the electrolyte) decompose and form on charging. Oxidation of Li2CO3
on charging to ∼4 V is incomplete; Li2CO3 accumulates on cycling resulting in
electrode passivation and capacity fading. Hydrophilic carbon is less stable and
more catalytically active toward electrolyte decomposition than carbon with a
hydrophobic surface. If the Li–O2 cell could be charged at or below 3.5 V, then
carbon may be relatively stable, however, its ability to promote electrolyte decomposition,
presenting problems for its use in a practical Li–O2 battery. The results emphasize
that stable cycling of Li2O2 at the cathode in a Li–O2 cell depends on the synergy
between electrolyte and electrode; the stability of the electrode and the electrolyte
cannot be considered in isolation.'
article_processing_charge: No
article_type: original
author:
- first_name: Muhammed M.
full_name: Ottakam Thotiyl, Muhammed M.
last_name: Ottakam Thotiyl
- first_name: Stefan Alexander
full_name: Freunberger, Stefan Alexander
id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425
last_name: Freunberger
orcid: 0000-0003-2902-5319
- first_name: Zhangquan
full_name: Peng, Zhangquan
last_name: Peng
- first_name: Peter G.
full_name: Bruce, Peter G.
last_name: Bruce
citation:
ama: Ottakam Thotiyl MM, Freunberger SA, Peng Z, Bruce PG. The carbon electrode
in nonaqueous Li–O2 cells. Journal of the American Chemical Society. 2012;135(1):494-500.
doi:10.1021/ja310258x
apa: Ottakam Thotiyl, M. M., Freunberger, S. A., Peng, Z., & Bruce, P. G. (2012).
The carbon electrode in nonaqueous Li–O2 cells. Journal of the American Chemical
Society. ACS. https://doi.org/10.1021/ja310258x
chicago: Ottakam Thotiyl, Muhammed M., Stefan Alexander Freunberger, Zhangquan Peng,
and Peter G. Bruce. “The Carbon Electrode in Nonaqueous Li–O2 Cells.” Journal
of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja310258x.
ieee: M. M. Ottakam Thotiyl, S. A. Freunberger, Z. Peng, and P. G. Bruce, “The carbon
electrode in nonaqueous Li–O2 cells,” Journal of the American Chemical Society,
vol. 135, no. 1. ACS, pp. 494–500, 2012.
ista: Ottakam Thotiyl MM, Freunberger SA, Peng Z, Bruce PG. 2012. The carbon electrode
in nonaqueous Li–O2 cells. Journal of the American Chemical Society. 135(1), 494–500.
mla: Ottakam Thotiyl, Muhammed M., et al. “The Carbon Electrode in Nonaqueous Li–O2
Cells.” Journal of the American Chemical Society, vol. 135, no. 1, ACS,
2012, pp. 494–500, doi:10.1021/ja310258x.
short: M.M. Ottakam Thotiyl, S.A. Freunberger, Z. Peng, P.G. Bruce, Journal of the
American Chemical Society 135 (2012) 494–500.
date_created: 2020-01-15T12:18:57Z
date_published: 2012-11-28T00:00:00Z
date_updated: 2021-01-12T08:12:56Z
day: '28'
doi: 10.1021/ja310258x
extern: '1'
intvolume: ' 135'
issue: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 494-500
publication: Journal of the American Chemical Society
publication_identifier:
issn:
- 0002-7863
- 1520-5126
publication_status: published
publisher: ACS
quality_controlled: '1'
status: public
title: The carbon electrode in nonaqueous Li–O2 cells
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 135
year: '2012'
...
---
_id: '7309'
abstract:
- lang: eng
text: Energy‐storage technologies, including electrical double‐layer capacitors
and rechargeable batteries, have attracted significant attention for applications
in portable electronic devices, electric vehicles, bulk electricity storage at
power stations, and “load leveling” of renewable sources, such as solar energy
and wind power. Transforming lithium batteries and electric double‐layer capacitors
requires a step change in the science underpinning these devices, including the
discovery of new materials, new electrochemistry, and an increased understanding
of the processes on which the devices depend. The Review will consider some of
the current scientific issues underpinning lithium batteries and electric double‐layer
capacitors.
article_processing_charge: No
article_type: original
author:
- first_name: Nam-Soon
full_name: Choi, Nam-Soon
last_name: Choi
- first_name: Zonghai
full_name: Chen, Zonghai
last_name: Chen
- first_name: Stefan Alexander
full_name: Freunberger, Stefan Alexander
id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425
last_name: Freunberger
orcid: 0000-0003-2902-5319
- first_name: Xiulei
full_name: Ji, Xiulei
last_name: Ji
- first_name: Yang-Kook
full_name: Sun, Yang-Kook
last_name: Sun
- first_name: Khalil
full_name: Amine, Khalil
last_name: Amine
- first_name: Gleb
full_name: Yushin, Gleb
last_name: Yushin
- first_name: Linda F.
full_name: Nazar, Linda F.
last_name: Nazar
- first_name: Jaephil
full_name: Cho, Jaephil
last_name: Cho
- first_name: Peter G.
full_name: Bruce, Peter G.
last_name: Bruce
citation:
ama: Choi N-S, Chen Z, Freunberger SA, et al. Challenges facing Lithium batteries
and electrical double-layer capacitors. Angewandte Chemie International Edition.
2012;51(40):9994-10024. doi:10.1002/anie.201201429
apa: Choi, N.-S., Chen, Z., Freunberger, S. A., Ji, X., Sun, Y.-K., Amine, K., …
Bruce, P. G. (2012). Challenges facing Lithium batteries and electrical double-layer
capacitors. Angewandte Chemie International Edition. Wiley. https://doi.org/10.1002/anie.201201429
chicago: Choi, Nam-Soon, Zonghai Chen, Stefan Alexander Freunberger, Xiulei Ji,
Yang-Kook Sun, Khalil Amine, Gleb Yushin, Linda F. Nazar, Jaephil Cho, and Peter
G. Bruce. “Challenges Facing Lithium Batteries and Electrical Double-Layer Capacitors.”
Angewandte Chemie International Edition. Wiley, 2012. https://doi.org/10.1002/anie.201201429.
ieee: N.-S. Choi et al., “Challenges facing Lithium batteries and electrical
double-layer capacitors,” Angewandte Chemie International Edition, vol.
51, no. 40. Wiley, pp. 9994–10024, 2012.
ista: Choi N-S, Chen Z, Freunberger SA, Ji X, Sun Y-K, Amine K, Yushin G, Nazar
LF, Cho J, Bruce PG. 2012. Challenges facing Lithium batteries and electrical
double-layer capacitors. Angewandte Chemie International Edition. 51(40), 9994–10024.
mla: Choi, Nam-Soon, et al. “Challenges Facing Lithium Batteries and Electrical
Double-Layer Capacitors.” Angewandte Chemie International Edition, vol.
51, no. 40, Wiley, 2012, pp. 9994–10024, doi:10.1002/anie.201201429.
short: N.-S. Choi, Z. Chen, S.A. Freunberger, X. Ji, Y.-K. Sun, K. Amine, G. Yushin,
L.F. Nazar, J. Cho, P.G. Bruce, Angewandte Chemie International Edition 51 (2012)
9994–10024.
date_created: 2020-01-15T12:19:11Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T08:12:56Z
day: '01'
doi: 10.1002/anie.201201429
extern: '1'
intvolume: ' 51'
issue: '40'
language:
- iso: eng
month: '10'
oa_version: None
page: 9994-10024
publication: Angewandte Chemie International Edition
publication_identifier:
issn:
- 1433-7851
publication_status: published
publisher: Wiley
quality_controlled: '1'
status: public
title: Challenges facing Lithium batteries and electrical double-layer capacitors
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2012'
...
---
_id: '7310'
abstract:
- lang: eng
text: The rechargeable nonaqueous lithium-air (Li-O2) battery is receiving a great
deal of interest because, theoretically, its specific energy far exceeds the best
that can be achieved with lithium-ion cells. Operation of the rechargeable Li-O2
battery depends critically on repeated and highly reversible formation/decomposition
of lithium peroxide (Li2O2) at the cathode upon cycling. Here, we show that this
process is possible with the use of a dimethyl sulfoxide electrolyte and a porous
gold electrode (95% capacity retention from cycles 1 to 100), whereas previously
only partial Li2O2 formation/decomposition and limited cycling could occur. Furthermore,
we present data indicating that the kinetics of Li2O2 oxidation on charge is approximately
10 times faster than on carbon electrodes.
article_processing_charge: No
article_type: original
author:
- first_name: Z.
full_name: Peng, Z.
last_name: Peng
- first_name: Stefan Alexander
full_name: Freunberger, Stefan Alexander
id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425
last_name: Freunberger
orcid: 0000-0003-2902-5319
- first_name: Y.
full_name: Chen, Y.
last_name: Chen
- first_name: P. G.
full_name: Bruce, P. G.
last_name: Bruce
citation:
ama: Peng Z, Freunberger SA, Chen Y, Bruce PG. A reversible and higher-rate Li-O2
battery. Science. 2012;337(6094):563-566. doi:10.1126/science.1223985
apa: Peng, Z., Freunberger, S. A., Chen, Y., & Bruce, P. G. (2012). A reversible
and higher-rate Li-O2 battery. Science. AAAS. https://doi.org/10.1126/science.1223985
chicago: Peng, Z., Stefan Alexander Freunberger, Y. Chen, and P. G. Bruce. “A Reversible
and Higher-Rate Li-O2 Battery.” Science. AAAS, 2012. https://doi.org/10.1126/science.1223985.
ieee: Z. Peng, S. A. Freunberger, Y. Chen, and P. G. Bruce, “A reversible and higher-rate
Li-O2 battery,” Science, vol. 337, no. 6094. AAAS, pp. 563–566, 2012.
ista: Peng Z, Freunberger SA, Chen Y, Bruce PG. 2012. A reversible and higher-rate
Li-O2 battery. Science. 337(6094), 563–566.
mla: Peng, Z., et al. “A Reversible and Higher-Rate Li-O2 Battery.” Science,
vol. 337, no. 6094, AAAS, 2012, pp. 563–66, doi:10.1126/science.1223985.
short: Z. Peng, S.A. Freunberger, Y. Chen, P.G. Bruce, Science 337 (2012) 563–566.
date_created: 2020-01-15T12:19:23Z
date_published: 2012-08-03T00:00:00Z
date_updated: 2021-01-12T08:12:57Z
day: '03'
doi: 10.1126/science.1223985
extern: '1'
intvolume: ' 337'
issue: '6094'
language:
- iso: eng
month: '08'
oa_version: None
page: 563-566
publication: Science
publication_identifier:
issn:
- 0036-8075
- 1095-9203
publication_status: published
publisher: AAAS
quality_controlled: '1'
status: public
title: A reversible and higher-rate Li-O2 battery
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 337
year: '2012'
...
---
_id: '7311'
abstract:
- lang: eng
text: Stability of the electrolyte toward reduced oxygen species generated at the
cathode is a crucial challenge for the rechargeable nonaqueous Li–O2 battery.
Here, we investigate dimethylformamide as the basis of an electrolyte. Although
reactions at the O2 cathode on the first discharge–charge cycle are dominated
by reversible Li2O2 formation/decomposition, there is also electrolyte decomposition,
which increases on cycling. The products of decomposition at the cathode on discharge
are Li2O2, Li2CO3, HCO2Li, CH3CO2Li, NO, H2O, and CO2. Li2CO3 accumulates in the
electrode with cycling. The stability of dimethylformamide toward reduced oxygen
species is insufficient for its use in the rechargeable nonaqueous Li–O2 battery.
article_processing_charge: No
article_type: original
author:
- first_name: Yuhui
full_name: Chen, Yuhui
last_name: Chen
- first_name: Stefan Alexander
full_name: Freunberger, Stefan Alexander
id: A8CA28E6-CE23-11E9-AD2D-EC27E6697425
last_name: Freunberger
orcid: 0000-0003-2902-5319
- first_name: Zhangquan
full_name: Peng, Zhangquan
last_name: Peng
- first_name: Fanny
full_name: Bardé, Fanny
last_name: Bardé
- first_name: Peter G.
full_name: Bruce, Peter G.
last_name: Bruce
citation:
ama: Chen Y, Freunberger SA, Peng Z, Bardé F, Bruce PG. Li–O2 battery with a dimethylformamide
electrolyte. Journal of the American Chemical Society. 2012;134(18):7952-7957.
doi:10.1021/ja302178w
apa: Chen, Y., Freunberger, S. A., Peng, Z., Bardé, F., & Bruce, P. G. (2012).
Li–O2 battery with a dimethylformamide electrolyte. Journal of the American
Chemical Society. ACS. https://doi.org/10.1021/ja302178w
chicago: Chen, Yuhui, Stefan Alexander Freunberger, Zhangquan Peng, Fanny Bardé,
and Peter G. Bruce. “Li–O2 Battery with a Dimethylformamide Electrolyte.” Journal
of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja302178w.
ieee: Y. Chen, S. A. Freunberger, Z. Peng, F. Bardé, and P. G. Bruce, “Li–O2 battery
with a dimethylformamide electrolyte,” Journal of the American Chemical Society,
vol. 134, no. 18. ACS, pp. 7952–7957, 2012.
ista: Chen Y, Freunberger SA, Peng Z, Bardé F, Bruce PG. 2012. Li–O2 battery with
a dimethylformamide electrolyte. Journal of the American Chemical Society. 134(18),
7952–7957.
mla: Chen, Yuhui, et al. “Li–O2 Battery with a Dimethylformamide Electrolyte.” Journal
of the American Chemical Society, vol. 134, no. 18, ACS, 2012, pp. 7952–57,
doi:10.1021/ja302178w.
short: Y. Chen, S.A. Freunberger, Z. Peng, F. Bardé, P.G. Bruce, Journal of the
American Chemical Society 134 (2012) 7952–7957.
date_created: 2020-01-15T12:19:36Z
date_published: 2012-04-19T00:00:00Z
date_updated: 2021-01-12T08:12:58Z
day: '19'
doi: 10.1021/ja302178w
extern: '1'
intvolume: ' 134'
issue: '18'
language:
- iso: eng
month: '04'
oa_version: None
page: 7952-7957
publication: Journal of the American Chemical Society
publication_identifier:
issn:
- 0002-7863
- 1520-5126
publication_status: published
publisher: ACS
quality_controlled: '1'
status: public
title: Li–O2 battery with a dimethylformamide electrolyte
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 134
year: '2012'
...
---
_id: '762'
abstract:
- lang: eng
text: Decades of research in distributed computing have led to a variety of perspectives
on what it means for a concurrent algorithm to be efficient, depending on model
assumptions, progress guarantees, and complexity metrics. It is therefore natural
to ask whether one could compose algorithms that perform efficiently under different
conditions, so that the composition preserves the performance of the original
components when their conditions are met. In this paper, we evaluate the cost
of composing shared-memory algorithms. First, we formally define the notion of
safely composable algorithms and we show that every sequential type has a safely
composable implementation, as long as enough state is transferred between modules.
Since such generic implementations are inherently expensive, we present a more
general light-weight specification that allows the designer to transfer very little
state between modules, by taking advantage of the semantics of the implemented
object. Using this framework, we implement a composed longlived test-and-set object,
with the property that each of its modules is asymptotically optimal with respect
to the progress condition it ensures, while the entire implementation only uses
objects with consensus number at most two. Thus, we show that the overhead of
composition can be negligible in the case of some important shared-memory abstractions.
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- first_name: Petr
full_name: Kuznetsov, Petr
last_name: Kuznetsov
- first_name: Giuliano
full_name: Losa, Giuliano
last_name: Losa
citation:
ama: 'Alistarh D-A, Guerraoui R, Kuznetsov P, Losa G. On the cost of composing shared-memory
algorithms. In: ACM; 2012:298-307. doi:10.1145/2312005.2312057'
apa: 'Alistarh, D.-A., Guerraoui, R., Kuznetsov, P., & Losa, G. (2012). On the
cost of composing shared-memory algorithms (pp. 298–307). Presented at the SPAA:
Symposium on Parallelism in Algorithms and Architectures, ACM. https://doi.org/10.1145/2312005.2312057'
chicago: Alistarh, Dan-Adrian, Rachid Guerraoui, Petr Kuznetsov, and Giuliano Losa.
“On the Cost of Composing Shared-Memory Algorithms,” 298–307. ACM, 2012. https://doi.org/10.1145/2312005.2312057.
ieee: 'D.-A. Alistarh, R. Guerraoui, P. Kuznetsov, and G. Losa, “On the cost of
composing shared-memory algorithms,” presented at the SPAA: Symposium on Parallelism
in Algorithms and Architectures, 2012, pp. 298–307.'
ista: 'Alistarh D-A, Guerraoui R, Kuznetsov P, Losa G. 2012. On the cost of composing
shared-memory algorithms. SPAA: Symposium on Parallelism in Algorithms and Architectures,
298–307.'
mla: Alistarh, Dan-Adrian, et al. On the Cost of Composing Shared-Memory Algorithms.
ACM, 2012, pp. 298–307, doi:10.1145/2312005.2312057.
short: D.-A. Alistarh, R. Guerraoui, P. Kuznetsov, G. Losa, in:, ACM, 2012, pp.
298–307.
conference:
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
date_created: 2018-12-11T11:48:22Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T13:12:27Z
day: '01'
doi: 10.1145/2312005.2312057
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 298 - 307
publication_status: published
publisher: ACM
publist_id: '6892'
status: public
title: On the cost of composing shared-memory algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '763'
abstract:
- lang: eng
text: Renaming is a fundamental problem in distributed computing, in which a set
of n processes need to pick unique names from a namespace of limited size. In
this paper, we present the first early-deciding upper bounds for synchronous renaming,
in which the running time adapts to the actual number of failures f in the execution.
We show that, surprisingly, renaming can be solved in constant time if the number
of failures f is limited to O(√n), while for general f ≤ n - 1 renaming can always
be solved in O(log f) communication rounds. In the wait-free case, i.e. for f
= n - 1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [13].
acknowledgement: "Hagit Attiya - Supported in party by Israel Science Foundation (grant
number 1227/10).\r\nCorentin Travers - Additional supports from the ANR projects
ALADDIN and DISPLEXITY\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Hagit
full_name: Attiya, Hagit
last_name: Attiya
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: 'Alistarh D-A, Attiya H, Guerraoui R, Travers C. Early deciding synchronous
renaming in O(log f) rounds or less. In: Vol 7355 LNCS. Springer; 2012:195-206.
doi:10.1007/978-3-642-31104-8_17'
apa: 'Alistarh, D.-A., Attiya, H., Guerraoui, R., & Travers, C. (2012). Early
deciding synchronous renaming in O(log f) rounds or less (Vol. 7355 LNCS, pp.
195–206). Presented at the SIROCCO: Structural Information and Communication Complexity,
Springer. https://doi.org/10.1007/978-3-642-31104-8_17'
chicago: Alistarh, Dan-Adrian, Hagit Attiya, Rachid Guerraoui, and Corentin Travers.
“Early Deciding Synchronous Renaming in O(Log f) Rounds or Less,” 7355 LNCS:195–206.
Springer, 2012. https://doi.org/10.1007/978-3-642-31104-8_17.
ieee: 'D.-A. Alistarh, H. Attiya, R. Guerraoui, and C. Travers, “Early deciding
synchronous renaming in O(log f) rounds or less,” presented at the SIROCCO: Structural
Information and Communication Complexity, 2012, vol. 7355 LNCS, pp. 195–206.'
ista: 'Alistarh D-A, Attiya H, Guerraoui R, Travers C. 2012. Early deciding synchronous
renaming in O(log f) rounds or less. SIROCCO: Structural Information and Communication
Complexity, LNCS, vol. 7355 LNCS, 195–206.'
mla: Alistarh, Dan-Adrian, et al. Early Deciding Synchronous Renaming in O(Log
f) Rounds or Less. Vol. 7355 LNCS, Springer, 2012, pp. 195–206, doi:10.1007/978-3-642-31104-8_17.
short: D.-A. Alistarh, H. Attiya, R. Guerraoui, C. Travers, in:, Springer, 2012,
pp. 195–206.
conference:
name: 'SIROCCO: Structural Information and Communication Complexity'
date_created: 2018-12-11T11:48:22Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T13:12:41Z
day: '01'
doi: 10.1007/978-3-642-31104-8_17
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 195 - 206
publication_status: published
publisher: Springer
publist_id: '6893'
status: public
title: Early deciding synchronous renaming in O(log f) rounds or less
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7355 LNCS
year: '2012'
...
---
_id: '764'
abstract:
- lang: eng
text: Set agreement is a fundamental problem in distributed computing in which processes
collectively choose a small subset of values from a larger set of proposals. The
impossibility of fault-tolerant set agreement in asynchronous networks is one
of the seminal results in distributed computing. In synchronous networks, too,
the complexity of set agreement has been a significant research challenge that
has now been resolved. Real systems, however, are neither purely synchronous nor
purely asynchronous. Rather, they tend to alternate between periods of synchrony
and periods of asynchrony. Nothing specific is known about the complexity of set
agreement in such a "partially synchronous" setting. In this paper,
we address this challenge, presenting the first (asymptotically) tight bound on
the complexity of set agreement in such systems. We introduce a novel technique
for simulating, in a fault-prone asynchronous shared memory, executions of an
asynchronous and failure-prone message-passing system in which some fragments
appear synchronous to some processes. We use this simulation technique to derive
a lower bound on the round complexity of set agreement in a partially synchronous
system by a reduction from asynchronous wait-free set agreement. Specifically,
we show that every set agreement protocol requires at least $\lfloor\frac t k
\rfloor + 2$ synchronous rounds to decide. We present an (asymptotically) matching
algorithm that relies on a distributed asynchrony detection mechanism to decide
as soon as possible during periods of synchrony. From these two results, we derive
the size of the minimal window of synchrony needed to solve set agreement. By
relating synchronous, asynchronous and partially synchronous environments, our
simulation technique is of independent interest. In particular, it allows us to
obtain a new lower bound on the complexity of early deciding k-set agreement complementary
to that of Gafni et al. (in SIAM J. Comput. 40(1):63-78, 2011), and to re-derive
the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput.
Sci. 410(6-7):570-580, 2009) in an algorithmic way.
acknowledgement: "We would like to thank Hagit Attiya, Keren Censor-Hillel, and
the anonymous\r\nreviewers for their feedback on drafts of this paper.\r\nPart
of the work was performed as C. Travers was a Post-Doctoral Fellow at the Technion,
Haifa,\r\nsupported by the “Sam & Cecilia Neaman” Fellowship. Part of the work was
performed as S. Gilbert was\r\na Post-Doctoral Fellow at the Swiss Federal Institute
of Technology, Lausanne, Switzerland."
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: 'Alistarh D-A, Gilbert S, Guerraoui R, Travers C. Of choices, failures and
asynchrony: the many faces of set agreement. Algorithmica (New York). 2012;62(1-2):595-629.
doi:10.1007/s00453-011-9581-7'
apa: 'Alistarh, D.-A., Gilbert, S., Guerraoui, R., & Travers, C. (2012). Of
choices, failures and asynchrony: the many faces of set agreement. Algorithmica
(New York). Springer. https://doi.org/10.1007/s00453-011-9581-7'
chicago: 'Alistarh, Dan-Adrian, Seth Gilbert, Rachid Guerraoui, and Corentin Travers.
“Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.” Algorithmica
(New York). Springer, 2012. https://doi.org/10.1007/s00453-011-9581-7.'
ieee: 'D.-A. Alistarh, S. Gilbert, R. Guerraoui, and C. Travers, “Of choices, failures
and asynchrony: the many faces of set agreement,” Algorithmica (New York),
vol. 62, no. 1–2. Springer, pp. 595–629, 2012.'
ista: 'Alistarh D-A, Gilbert S, Guerraoui R, Travers C. 2012. Of choices, failures
and asynchrony: the many faces of set agreement. Algorithmica (New York). 62(1–2),
595–629.'
mla: 'Alistarh, Dan-Adrian, et al. “Of Choices, Failures and Asynchrony: The Many
Faces of Set Agreement.” Algorithmica (New York), vol. 62, no. 1–2, Springer,
2012, pp. 595–629, doi:10.1007/s00453-011-9581-7.'
short: D.-A. Alistarh, S. Gilbert, R. Guerraoui, C. Travers, Algorithmica (New York)
62 (2012) 595–629.
date_created: 2018-12-11T11:48:23Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2023-02-23T13:13:02Z
day: '01'
doi: 10.1007/s00453-011-9581-7
extern: '1'
intvolume: ' 62'
issue: 1-2
language:
- iso: eng
month: '02'
oa_version: None
page: 595 - 629
publication: Algorithmica (New York)
publication_status: published
publisher: Springer
publist_id: '6894'
status: public
title: 'Of choices, failures and asynchrony: the many faces of set agreement'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2012'
...
---
_id: '766'
abstract:
- lang: eng
text: 'Asynchronous task allocation is a fundamental problem in distributed computing
in which p asynchronous processes must execute a set of m tasks. Also known as
write-all or do-all, this problem been studied extensively, both independently
and as a key building block for various distributed algorithms. In this paper,
we break new ground on this classic problem: we introduce the To-Do Tree concurrent
data structure, which improves on the best known randomized and deterministic
upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree
algorithm has O(m + p log p log2 m) work complexity. We then show that there exists
a deterministic variant of the To-Do Tree algorithm with work complexity O(m +
p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within
log factors of the Ω(m + p log p) lower bound for this problem. The key technical
ingredient in our results is a new approach for analyzing concurrent executions
against a strong adaptive scheduler. This technique allows us to handle the complex
dependencies between the processes'' coin flips and their scheduling, and to tightly
bound the work needed to perform subsets of the tasks.'
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Michael
full_name: Bender, Michael
last_name: Bender
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Rachid
full_name: Guerraoui, Rachid
last_name: Guerraoui
citation:
ama: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. How to allocate tasks asynchronously.
In: IEEE; 2012:331-340. doi:10.1109/FOCS.2012.41'
apa: 'Alistarh, D.-A., Bender, M., Gilbert, S., & Guerraoui, R. (2012). How
to allocate tasks asynchronously (pp. 331–340). Presented at the FOCS: Foundations
of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2012.41'
chicago: Alistarh, Dan-Adrian, Michael Bender, Seth Gilbert, and Rachid Guerraoui.
“How to Allocate Tasks Asynchronously,” 331–40. IEEE, 2012. https://doi.org/10.1109/FOCS.2012.41.
ieee: 'D.-A. Alistarh, M. Bender, S. Gilbert, and R. Guerraoui, “How to allocate
tasks asynchronously,” presented at the FOCS: Foundations of Computer Science,
2012, pp. 331–340.'
ista: 'Alistarh D-A, Bender M, Gilbert S, Guerraoui R. 2012. How to allocate tasks
asynchronously. FOCS: Foundations of Computer Science, 331–340.'
mla: Alistarh, Dan-Adrian, et al. How to Allocate Tasks Asynchronously. IEEE,
2012, pp. 331–40, doi:10.1109/FOCS.2012.41.
short: D.-A. Alistarh, M. Bender, S. Gilbert, R. Guerraoui, in:, IEEE, 2012, pp.
331–340.
conference:
name: 'FOCS: Foundations of Computer Science'
date_created: 2018-12-11T11:48:23Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T13:13:27Z
day: '01'
doi: 10.1109/FOCS.2012.41
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 331 - 340
publication_status: published
publisher: IEEE
publist_id: '6890'
status: public
title: How to allocate tasks asynchronously
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...