3 Search Results for "Talmon, Nimrod"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.47
Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications

Authors: Ehud Shapiro

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Informally, a distributed system is grassroots if it is permissionless and can have autonomous, independently-deployed instances - geographically and over time - that may interoperate voluntarily once interconnected. More formally, in a grassroots system the set of all correct behaviors of a set of agents P is strictly included in the set of the correct behaviors of P when they are embedded within a larger set of agents P' ⊃ P. Grassroots systems are potentially important as they may allow communities to conduct their social, economic, civic, and political lives in the digital realm solely using their members' networked computing devices (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or rent seeking (e.g., by global digital platforms such as Facebook or Bitcoin). Client-server/cloud computing systems are not grassroots, and neither are systems designed to have a single global instance (Bitcoin/Ethereum with hardwired seed miners/bootnodes), and systems that rely on a single global data structure (IPFS, DHTs). An example grassroots system would be a serverless smartphone-based social network supporting multiple independently-budding communities that can merge when a member of one community becomes also a member of another. Here, we formalize the notion of grassroots distributed systems; describe a grassroots dissemination protocol for the model of asynchrony and argue its safety, liveness, and being grassroots; extend the implementation to mobile (address-changing) devices that communicate via an unreliable network (e.g. smartphones using UDP); and discuss how grassroots dissemination can realize grassroots social networking and grassroots cryptocurrencies. The mathematical construction employs distributed multiagent transition systems to define the notions of grassroots protocols, to specify the grassroots dissemination protocols, and to prove their correctness. The protocols use the blocklace - a distributed, partially-ordered counterpart of the replicated, totally-ordered blockchain.
Cite as

Ehud Shapiro. Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 47:1-47:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shapiro:LIPIcs.DISC.2023.47,
  author =	{Shapiro, Ehud},
  title =	{{Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{47:1--47:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.47},
  URN =		{urn:nbn:de:0030-drops-191735},
  doi =		{10.4230/LIPIcs.DISC.2023.47},
  annote =	{Keywords: Grassroots Distributed Systems, Dissemination Protocol, Multiagent Transition Systems, Blocklace, Cordial Dissemination}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.30
The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration

Authors: Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
In this article, the Program Committee of the Second Parameterized Algorithms and Computational Experiments challenge (PACE 2017) reports on the second iteration of the PACE challenge. Track A featured the Treewidth problem and Track B the Minimum Fill-In problem. Over 44 participants on 17 teams from 11 countries submitted their implementations to the competition.
Cite as

Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2017.30,
  author =	{Dell, Holger and Komusiewicz, Christian and Talmon, Nimrod and Weller, Mathias},
  title =	{{The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.30},
  URN =		{urn:nbn:de:0030-drops-85582},
  doi =		{10.4230/LIPIcs.IPEC.2017.30},
  annote =	{Keywords: treewidth, minimum fill-in, contest, implementation challenge, FPT}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.55
Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs

Authors: Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.
Cite as

Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger. Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 55-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.IPEC.2015.55,
  author =	{Hermelin, Danny and Kubitza, Judith-Madeleine and Shabtay, Dvir and Talmon, Nimrod and Woeginger, Gerhard},
  title =	{{Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.55},
  URN =		{urn:nbn:de:0030-drops-55713},
  doi =		{10.4230/LIPIcs.IPEC.2015.55},
  annote =	{Keywords: Parameterized Complexity, Multiagent Scheduling}
}
  • Refine by Author
  • 2 Talmon, Nimrod
  • 1 Dell, Holger
  • 1 Hermelin, Danny
  • 1 Komusiewicz, Christian
  • 1 Kubitza, Judith-Madeleine
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Blocklace
  • 1 Cordial Dissemination
  • 1 Dissemination Protocol
  • 1 FPT
  • 1 Grassroots Distributed Systems
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact