Change search
Link to record
Permanent link

Direct link
Publications (10 of 104) Show all publications
Ng, H., Haridi, S. & Carbone, P. (2023). Omni-Paxos: Breaking the Barriers of Partial Connectivity. In: Proceedings of the 18th European Conference on Computer Systems, EuroSys 2023: . Paper presented at 18th European Conference on Computer Systems, EuroSys 2023, 8 May 2023 through 12 May 2023 (pp. 314-330). Association for Computing Machinery, Inc
Open this publication in new window or tab >>Omni-Paxos: Breaking the Barriers of Partial Connectivity
2023 (English)In: Proceedings of the 18th European Conference on Computer Systems, EuroSys 2023, Association for Computing Machinery, Inc , 2023, p. 314-330Conference paper, Published paper (Refereed)
Abstract [en]

Omni-Paxos is a system for state machine replication that is completely resilient to partial network partitions, a major source of service disruptions in recent years. Omni-Paxos achieves its resilience through a decoupled design that separates the execution and state of leader election from log replication. The leader election builds on the concept of quorum-connected servers, with the sole focus on connectivity. Additionally, by decoupling reconfiguration from log replication, Omni-Paxos provides flexible and parallel log migration that improves the performance and robustness of reconfiguration. Our evaluation showcases two benefits over state-of-the-art protocols: (1) guaranteed recovery in at most four election timeouts under extreme partial network partitions, and (2) up to 8x shorter reconfiguration periods with 46% less I/O at the leader.

Place, publisher, year, edition, pages
Association for Computing Machinery, Inc, 2023
Keywords
consensus, partial connectivity, reconfiguration, state machine replication, Breakings, Decouplings, Leader election, Network partitions, Service disruptions, Source of service, Distributed computer systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:ri:diva-65403 (URN)10.1145/3552326.3587441 (DOI)2-s2.0-85160212180 (Scopus ID)9781450394871 (ISBN)
Conference
18th European Conference on Computer Systems, EuroSys 2023, 8 May 2023 through 12 May 2023
Note

Funding details: BD15-0006; Funding text 1: This work has been supported by the Swedish Foundation of Strategic Research (Grant No.: BD15-0006), Google Cloud Research Credits Program, and Wallenberg AI NEST (Data-Bound Computing). Furthermore, we would like to thank Lars Kroll for early-stage contributions to the Sequence Paxos specification, as well as peer reviewers and Marios Kogias for the improvement suggestions.

Available from: 2023-06-15 Created: 2023-06-15 Last updated: 2023-06-15Bibliographically approved
Van Roy, P., Haridi, S., Schulte, C. & Smolka, G. (2020). A history of the Oz multiparadigm language. Proceedings of the ACM on Programming Languages, 4(HOPL), Article ID 83.
Open this publication in new window or tab >>A history of the Oz multiparadigm language
2020 (English)In: Proceedings of the ACM on Programming Languages, E-ISSN 2475-1421, Vol. 4, no HOPL, article id 83Article in journal (Refereed) Published
Abstract [en]

Oz is a programming language designed to support multiple programming paradigms in a clean factored way that is easy to program despite its broad coverage. It started in 1991 as a collaborative effort by the DFKI (Germany) and SICS (Sweden) and led to an influential system, Mozart, that was released in 1999 and widely used in the 2000s for practical applications and education. We give the history of Oz as it developed from its origins in logic programming, starting with Prolog, followed by concurrent logic programming and constraint logic programming, and leading to its two direct precursors, the concurrent constraint model and the Andorra Kernel Language (AKL). We give the lessons learned from the Oz effort including successes and failures and we explain the principles underlying the Oz design. Oz is defined through a kernel language, which is a formal model similar to a foundational calculus, but that is designed to be directly useful to the programmer. The kernel language is organized in a layered structure, which makes it straightforward to write programs that use different paradigms in different parts. Oz is a key enabler for the book Concepts, Techniques, and Models of Computer Programming (MIT Press, 2004). Based on the book and the implementation, Oz has been used successfully in university-level programming courses starting from 2001 to the present day.

Place, publisher, year, edition, pages
Association for Computing Machinery, 2020
Keywords
Computer programming, Concurrent programming, Dataflow, Distributed programming, Functional programming, Lazy evaluation, Logic programming, Multiparadigm programming, Programming education, Calculations, Concurrent constraint, Concurrent logic programming, Constraint Logic Programming, Foundational calculus, Layered Structures, Multi-paradigm languages, Programming course, Programming paradigms, PROLOG (programming language)
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-48928 (URN)10.1145/3386333 (DOI)2-s2.0-85091278047 (Scopus ID)
Available from: 2020-10-13 Created: 2020-10-13 Last updated: 2023-08-25Bibliographically approved
Kroll, L., Segeljakt, K., Carbone, P., Schulte, C. & Haridi, S. (2019). Arc: An IR for Batch and Stream Programming. In: Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages: . Paper presented at 17th ACM SIGPLAN International Symposium on Database Programming Languages (pp. 53-58). Association for Computing Machinery
Open this publication in new window or tab >>Arc: An IR for Batch and Stream Programming
Show others...
2019 (English)In: Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, Association for Computing Machinery , 2019, p. 53-58Conference paper, Published paper (Refereed)
Abstract [en]

In big data analytics, there is currently a large number of data programming models and their respective frontends such as relational tables, graphs, tensors, and streams. This has lead to a plethora of runtimes that typically focus on the efficient execution of just a single frontend. This fragmentation manifests itself today by highly complex pipelines that bundle multiple runtimes to support the necessary models. Hence, joint optimization and execution of such pipelines across these frontend-bound runtimes is infeasible. We propose Arc as the first unified Intermediate Representation (IR) for data analytics that incorporates stream semantics based on a modern specification of streams, windows and stream aggregation, to combine batch and stream computation models. Arc extends Weld, an IR for batch computation and adds support for partitioned, out-of-order stream and window operators which are the most fundamental building blocks in contemporary data streaming.

Place, publisher, year, edition, pages
Association for Computing Machinery, 2019
Series
DBPL 2019
Keywords
stream processing, data analytics, intermediate representation
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-49108 (URN)10.1145/3315507.3330199 (DOI)
Conference
17th ACM SIGPLAN International Symposium on Database Programming Languages
Available from: 2020-10-15 Created: 2020-10-15 Last updated: 2023-06-07Bibliographically approved
Meldrum, M., Segeljakt, K., Kroll, L., Carbone, P., Schulte, C. & Haridi, S. (2019). Arcon: Continuous and deep data stream analytics. In: ACM International Conference Proceeding Series: . Paper presented at 13th International Workshop on Real-Time Business Intelligence and Analytics, BIRTE 2019, in conjunction with the VLDB 2019 Conference, 26 August 2019. Association for Computing Machinery
Open this publication in new window or tab >>Arcon: Continuous and deep data stream analytics
Show others...
2019 (English)In: ACM International Conference Proceeding Series, Association for Computing Machinery , 2019Conference paper, Published paper (Refereed)
Abstract [en]

Contemporary end-to-end data pipelines need to combine many diverse workloads such as machine learning, relational operations, stream dataflows, tensor transformations, and graphs. For each of these workload types, there exists several frontends (e.g., SQL, Beam, Keras) based on different programming languages as well as different runtimes (e.g., Spark, Flink, Tensorflow) that optimize for a particular frontend and possibly a hardware architecture (e.g., GPUs). The resulting pipelines suffer in terms of complexity and performance due to excessive type conversions, materialization of intermediate results, and lack of cross-framework optimizations. Arcon aims to provide a unified approach to declare and execute tasks across frontend-boundaries as well as enabling their seamless integration with event-driven services at scale. In this demonstration, we present Arcon and through a series of use-case scenarios demonstrate that its execution model is powerful enough to cover existing as well as upcoming real-time computations for analytics and application-specific needs. © 2019 Copyright held by the owner/author(s).

Place, publisher, year, edition, pages
Association for Computing Machinery, 2019
Keywords
Data flow analysis, Information analysis, Object oriented programming, Program processors, Application specific, Framework optimization, Hardware architecture, Intermediate results, Real-time computations, Relational operations, Seamless integration, Tensor transformation, Pipelines
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-40454 (URN)10.1145/3350489.3350492 (DOI)2-s2.0-85072806432 (Scopus ID)9781450376600 (ISBN)
Conference
13th International Workshop on Real-Time Business Intelligence and Analytics, BIRTE 2019, in conjunction with the VLDB 2019 Conference, 26 August 2019
Available from: 2019-10-15 Created: 2019-10-15 Last updated: 2023-06-07Bibliographically approved
Rahimian, F., Payberah, A., Girdzijauskas, S., Jelasity, M. & Haridi, S. (2015). A distributed algorithm for large-scale graph partitioning. ACM Transactions on Autonomous and Adaptive Systems, 10(2), Article ID 12.
Open this publication in new window or tab >>A distributed algorithm for large-scale graph partitioning
Show others...
2015 (English)In: ACM Transactions on Autonomous and Adaptive Systems, ISSN 1556-4665, E-ISSN 1556-4703, Vol. 10, no 2, article id 12Article in journal (Refereed) Published
Abstract [en]

Balanced graph partitioning is an NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems, including the optimal storage of large sets of graph-structured data over several hosts. However, in very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable because they typically involve frequent global operations over the entire graph. In this article, we propose a fully distributed algorithm called Ja-be-Ja that uses local search and simulated annealing techniques for two types of graph partitioning: edge-cut partitioning and vertex-cut partitioning. The algorithm is massively parallel: There is no central coordination, each vertex is processed independently, and only the direct neighbors of a vertex and a small subset of random vertices in the graph need to be known locally. Strict synchronization is not required. These features allow Ja-be-Ja to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We show that the minimal edge-cut value empirically achieved by Ja-be-Ja is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks, Ja-be-Ja outperforms Metis. We also show that Ja-be-Ja computes very low vertex-cuts, which are proved significantly more effective than edge-cuts for processing most real-world graphs.

Place, publisher, year, edition, pages
Association for Computing Machinery, 2015
Keywords
Distributed algorithm, Edge-cut partitioning, Graph partitioning, Load balancing, Simulated annealing, Vertex-cut partitioning, Algorithms, Computational complexity, Data handling, Digital storage, Network management, Parallel algorithms, Resource allocation, Balanced graph partitioning, Centralized algorithms, Edge cuts, Graph structured data, Simulated annealing techniques, State-of-the-art algorithms, Vertex-cut, Graph theory
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-41882 (URN)10.1145/2714568 (DOI)2-s2.0-84930973235 (Scopus ID)
Available from: 2019-12-12 Created: 2019-12-12 Last updated: 2023-06-07Bibliographically approved
Rahimian, F., Payberah, A. H., Girdzijauskas, S. & Haridi, S. (2014). Distributed vertex-cut partitioning. In: Lecture Notes in Computer Science: . Paper presented at 3 June 2014 through 5 June 2014, Berlin (pp. 186-200). Springer Verlag
Open this publication in new window or tab >>Distributed vertex-cut partitioning
2014 (English)In: Lecture Notes in Computer Science, Springer Verlag , 2014, p. 186-200Conference paper, Published paper (Refereed)
Abstract [en]

Graph processing has become an integral part of big data analytics. With the ever increasing size of the graphs, one needs to partition them into smaller clusters, which can be managed and processed more easily on multiple machines in a distributed fashion. While there exist numerous solutions for edge-cut partitioning of graphs, very little effort has been made for vertex-cut partitioning. This is in spite of the fact that vertex-cuts are proved significantly more effective than edge-cuts for processing most real world graphs. In this paper we present Ja-be-Ja-vc, a parallel and distributed algorithm for vertex-cut partitioning of large graphs. In a nutshell, Ja-be-Ja-vc is a local search algorithm that iteratively improves upon an initial random assignment of edges to partitions. We propose several heuristics for this optimization and study their impact on the final partitioning. Moreover, we employ simulated annealing technique to escape local optima. We evaluate our solution on various graphs and with variety of settings, and compare it against two state-of-the-art solutions. We show that Ja-be-Ja-vc outperforms the existing solutions in that it not only creates partitions of any requested size, but also requires a vertex-cut that is better than its counterparts and more than 70% better than random partitioning.

Place, publisher, year, edition, pages
Springer Verlag, 2014
Keywords
Big data, Graphic methods, Interoperability, Iterative methods, Simulated annealing, Data analytics, Graph processing, Local search algorithm, Multiple machine, Parallel and distributed algorithms, Random assignment, Real-world graphs, Simulated annealing techniques, Graph theory
National Category
Engineering and Technology
Identifiers
urn:nbn:se:ri:diva-45563 (URN)10.1007/978-3-662-43352-2_15 (DOI)2-s2.0-84902593727 (Scopus ID)9783662433515 (ISBN)
Conference
3 June 2014 through 5 June 2014, Berlin
Note

Conference code: 105614

Available from: 2020-08-10 Created: 2020-08-10 Last updated: 2023-06-07Bibliographically approved
Rahimian, F., Girdzijauskas, S. & Haridi, S. (2014). Parallel Community Detection For Cross-Document Coreference (6ed.). Kista, Sweden: Swedish Institute of Computer Science
Open this publication in new window or tab >>Parallel Community Detection For Cross-Document Coreference
2014 (English)Report (Other academic)
Abstract [en]

This document presents a highly parallel solution for cross-document coreference resolution, which can deal with billions of documents that exist in the current web. At the core of our solution lies a novel algorithm for community detection in large scale graphs. We operate on graphs which we construct by representing documents' keywords as nodes and the co-location of those keywords in a document as edges. We then exploit the particular nature of such graphs where coreferent words are topologically clustered and can be efficiently discovered by our community detection algorithm. The accuracy of our technique is considerably higher than that of the state of the art, while the convergence time is by far shorter. In particular, we increase the accuracy for a baseline dataset by more than 15\% compared to the best reported result so far. Moreover, we outperform the best reported result for a dataset provided for the Word Sense Induction task in SemEval 2010.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science, 2014 Edition: 6
Series
SICS Technical Report, ISSN 1100-3154 ; 2014:01
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-24302 (URN)
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-06-07Bibliographically approved
Rahimian, F., Payberah, A., Girdzijauskas, S., Jelasity, M. & Haridi, S. (2013). Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning (7ed.). Kista, Sweden: Swedish Institute of Computer Science
Open this publication in new window or tab >>Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning
Show others...
2013 (English)Report (Other academic)
Abstract [en]

Balanced graph partitioning is a well known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems such as the optimal storage of large sets of graph-structured data over several hosts, or identifying clusters in on-line social networks. In such very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. In this paper, we propose a distributed graph partitioning algorithm, called Ja-be-Ja1. The algorithm is massively parallel: each graph node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known. Strict synchronization is not required. These features allow Ja-be-Ja to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by Ja-be-Ja is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks Ja-be-Ja outperforms Metis.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science, 2013 Edition: 7
Series
SICS Technical Report, ISSN 1100-3154 ; 2013:03
Keywords
graph partitioning, distributed algorithm, load balancing
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-24165 (URN)
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-06-07Bibliographically approved
Payberah, A. H., Kavalionak, H., Montresor, A., Dowling, J. & Haridi, S. (2013). Lightweight gossip-based distribution estimation. In: IEEE International Conference on Communications: . Paper presented at 2013 IEEE International Conference on Communications, ICC 2013, 9 June 2013 through 13 June 2013, Budapest (pp. 3439-3443). Institute of Electrical and Electronics Engineers Inc., Article ID 6655081.
Open this publication in new window or tab >>Lightweight gossip-based distribution estimation
Show others...
2013 (English)In: IEEE International Conference on Communications, Institute of Electrical and Electronics Engineers Inc. , 2013, p. 3439-3443, article id 6655081Conference paper, Published paper (Refereed)
Abstract [en]

Monitoring the global state of an overlay network is vital for the self-management of peer-to-peer (P2P) systems. Gossip-based algorithms are a well-known technique that can provide nodes locally with aggregated knowledge about the state of the overlay network. In this paper, we present a gossip-based protocol to estimate the global distribution of attribute values stored across a set of nodes in the system. Our algorithm estimates the distribution both efficiently and accurately. The key contribution of our algorithm is that it has substantially lower overhead than existing distribution estimation algorithms. We evaluated our system in simulation, and compared it against the state-of-the-art solutions. The results show similar accuracy to its counterparts, but with a communication overhead of an order of magnitude lower than them.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc., 2013
Keywords
Algorithms, Distributed computer systems, Overlay networks, Peer to peer networks, Attribute values, Communication overheads, Distribution estimation, Distribution estimation algorithms, Global distribution, Gossip-based algorithms, Gossip-based protocol, Peer-to-Peer system, Estimation
National Category
Engineering and Technology
Identifiers
urn:nbn:se:ri:diva-47633 (URN)10.1109/ICC.2013.6655081 (DOI)2-s2.0-84891358815 (Scopus ID)9781467331227 (ISBN)
Conference
2013 IEEE International Conference on Communications, ICC 2013, 9 June 2013 through 13 June 2013, Budapest
Available from: 2020-08-28 Created: 2020-08-28 Last updated: 2023-06-07Bibliographically approved
Arad, C., Shafaat, T. M. & Haridi, S. (2012). Brief Announcement: Atomic Consistency and Partition Tolerance in Scalable Key-Value Stores (10ed.). In: : . Paper presented at Proceedings of 26th International Symposium on Distributed Computing (DISC), Brazil, (pp. 445-446). Springer, 7611
Open this publication in new window or tab >>Brief Announcement: Atomic Consistency and Partition Tolerance in Scalable Key-Value Stores
2012 (English)Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2012 Edition: 10
Series
Lecture Notes in Computer Science
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-24108 (URN)
Conference
Proceedings of 26th International Symposium on Distributed Computing (DISC), Brazil,
Projects
CNS
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-06-07Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-6718-0144

Search in DiVA

Show all publications