Questions tagged [distributed-systems]

Questions about the challenges of solving problems with multiple cooperating but separate agents.

Filter by
Sorted by
Tagged with
1
vote
0answers
92 views

Reduction of flow-shop scheduling to a real-world computing problem

Consider the following well known flow-shop problem: We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$. Each job $J_i$ consists of a set of operations $...
0
votes
0answers
114 views

Distributed Algorithm for Minimum Cost Maximum Matching in General Graphs

What are the fastest distributed algorithms for minimum cost maximum matching in general graphs? I found two papers that talk about approximation algorithms but I want algorithms that solve the ...
5
votes
1answer
919 views

Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent....
1
vote
0answers
31 views

Can queueing model capture insights of a system in terms of CPU utilization & service delay? [closed]

After some efforts, I'm really doubtful about the application of that queueing model in analyzing network servers (specially in my case, IP Multimedia Subsystem) as well as predicting the workload. ...
3
votes
1answer
148 views

Are vector clocks useful in centralized systems?

Vectors clocks seem to be a common way to synchronize the partial ordering of events in a distributed, peer-to-peer, system across all clients. Is there any benefit to using them in a centralized ...
1
vote
1answer
89 views

Formal way to model or describe distributed systems architecture

I've been tasked to create the systems architecture for a distributed system. One approach to designing this system is to pick systems architecture patterns, and then evaluate different technologies ...
0
votes
0answers
60 views

Explanation of pilot jobs in distributed/grid computing

I'm reading into grid systems/distributed systems and came across pilot jobs that I can't find a decent explanation for. The wikipedia page is not understandable to me. I know multi-level schemes ...
3
votes
1answer
136 views

Overflow of integer counter in distributed systems

I've just been introduced to Paxos. There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this ...
5
votes
1answer
518 views

blockchain database - why so redundant

I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database. Why can't distributed blockchain database be 'distributed' to ...
-2
votes
1answer
635 views

Both shared-memory and distributed-memory

As you see in the following picture its a shared-memory architecture which has been modeled in a form of complete graph. Why we can consider the following architecture (which is a complete graph) both ...
4
votes
2answers
3k views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
0
votes
1answer
2k views

Difference between centralized computing and distributed computing using Client-Server

I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes ...
4
votes
3answers
2k views

What is the consensus algorithm that requires an odd number of nodes?

Last week I stood up and gave a talk on the Raft Consensus Algorithm. The first question I got was: Doesn't it need an odd number of nodes? I answered "During leader election, the first node to ...
1
vote
0answers
152 views

Using consensus for atomic commits

I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus ...
0
votes
2answers
6k views

What is the difference between centralised, decentralised, distributed, fully-distributed?

What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system? Which type or topology is the system attached in the ...
3
votes
1answer
411 views

Can we say that Zookeeper updates are ACD (ACID without the I)?

Zookeeper is based on the Zab (which is slightly different to Paxos) system. We can do Atomic locks on top of a Zookeeper cluster. Zookeeper provides eventual consistency. Zookeeper provides ...
3
votes
0answers
53 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
5
votes
1answer
834 views

Vector clocks: Why is it necessary to increment my clock on receiving a message?

Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes. ...
6
votes
2answers
2k views

Why is the commit phase in PBFT necessary?

I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that PREPARE phase ensures fault-...
2
votes
1answer
35 views

How can a distributed system cooperate to determine rules of its environment?

I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm ...
1
vote
2answers
408 views

Distributed systems according to Lamport?

I need some clarification over the following quotation of Leslie Lamport: A distributed system can be described as a particular sequential state machine that is implemented with a network of ...
0
votes
3answers
890 views

Computing the intersection of N sets over an M-element universe

Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$. 1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$? 2.) I am also looking for a good parallel and a good ...
0
votes
1answer
297 views

Difference between 2f+1, 2f and 3f+1

I am currently reading the Practical Byzantine Fault Tolerance paper. I am unable to completely understand the difference between 2f and ...
1
vote
1answer
105 views

Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
3
votes
1answer
519 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
4
votes
6answers
3k views

Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
1
vote
1answer
114 views

Synchronisation and ordering in distributed systems

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages ...
3
votes
0answers
112 views

What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called "...
2
votes
1answer
270 views

Call-by-reference semantics for RPC

Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't ...
2
votes
1answer
46 views

Term for shifting work to idle machines

I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks ...
5
votes
2answers
1k views

How to resize a large, distributed hash table?

Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain ...
4
votes
1answer
2k views

Is there a difference between total-ordering consistency and linearizability?

By total-ordering I mean the following definition[0]: Total Event Ordering: Controller replicas should process events in the same order and subsequently all controller application instances ...
1
vote
0answers
106 views

Processes running in Distributed Systems (Advanced Operating System)

I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did ...
3
votes
1answer
92 views

Algorithm for executing a command against a million hosts

Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the ...
2
votes
0answers
61 views

Floating output/making a non-self stabilizing algorithm self stabilizing

So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on "...
1
vote
1answer
106 views

Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over ...
4
votes
0answers
104 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
2
votes
1answer
449 views

Working of the GHS algorithm

Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found ...
6
votes
0answers
86 views

What is 2g-precedence?

I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
1
vote
0answers
30 views

parallel computation and GPGPU question [closed]

is there a mean of creating a cluster of machines, that can be seen as an entire system, using perhaps mac OS X or mac os x server, and use parallelism and GPGPU optimisation to compute all the tasks ...
1
vote
1answer
561 views

What advantage does Tangaroa offer over PBFT?

Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should ...
2
votes
2answers
2k views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
3
votes
1answer
123 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
5
votes
1answer
417 views

Paxos consistency

I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know ...
0
votes
1answer
48 views

How can I take advantage of the capabilities of a cluster [closed]

I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that ...
2
votes
0answers
93 views

What are the prerequisites for working on multi agent systems? [closed]

I am starting to study about Multi Agent Systems and I wanted to know which sciences are most used in these systems, I am aware of game theory and Markov statistical relations (Markov Decision Process ...
2
votes
0answers
78 views

Client-Server Architecture /State Model and Process Mode [closed]

how i can define what are Client-Server Architecture for a website that suggestion courses for students after students insert the history of courses. The language will be PHP,mysql and HTML. In this ...
5
votes
2answers
454 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
1
vote
1answer
43 views

In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?

Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler. Is it possible for both parties to agree ...
4
votes
1answer
386 views

Symmetric protocols for consensus

All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any ...

1 2 3
4
5
7