Randomly assign n elements to n agents such that each agent only knows its own element


Problem

I’m working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn’t require a trusted intermediary.

In other terms, the task is to find a distributed algorithm that

  • uniquely assigns $ n$ agents numbers $ 1..n$
  • allows each agent to know nothing about the assignment but its own
  • when revealing the assignment, allows other players to verify the assignment

We also assume that knowing other’s assignment is an advantage for each agent, and revealing its own prematurely a disadvantage. Agents are also assumed to be able to talk with each other in a way hidden from all other agents.

Partial solution

The solution I came up with works only under the assumption that adversaries do not collaborate.

The idea is to create a set of $ n$ nonces, and assign each agent exactly one nonce. The set is then passed from agent to agent in an agreed upon order, hidden from all others, until each agent received the set exactly once. Each time an agent receives the set, it swaps its nonce with a new one, memorizes the new nonce, and confirms receival of the set to the others. This entire procedure is done twice, at which point, all agents have received the set at least once after all other agents swapped their nonces, making it impossible to recognize and hence map the nonces to the other agents.

When the last agent receives the set the second time, it shares it with everyone, and all agents confirm to the others that their nonce is contained in the set. The agents then assign a number to each nonce in the set based on an agreed upon random seed, giving us the required unique assignment.

To allow ownership verification, instead of the nonces, agents put the hash value of their nonce on the set, revealing the actual nonce only when verification is required.


The problem with this solution is that if adversaries are allowed to collaborate, each time an adversary receives the set, they can compare their versions, identify changes and potentially derive which nonce belongs to other agents, allowing them to know what number got assigned to them.

All ideas are appreciated!

I’m trying to write a randomly patrolling AI for my 2D Platformer

I’m trying to write a randomly patrolling AI for my 2D Platformer. The AI already has a ground checker function which checks if there are tiles nearby or not. What I want to do is randomize its actions and create an illusion of a somewhat "sentient" enemy. What I tried to create below is using the built in RNG to make the enemy either jump, change direction, or keep moving.

The problem is, it doesn’t seem to work properly. The enemy just jumps every second I want it to change behaviour. The change direction functions, however, don’t occur as frequently. I need to know what I’ve done wrong here. Thanks.

void Update() {          //RNG       behaviour = Random.Range(0,3);       jumpSpeed = Random.Range(1,5);         //clock       timer += Time.deltaTime; }    //time     private float waitTime = 2.0f;     private float timer = 0.0f;   void MoveRandomizer() {     if((Mathf.Round(timer%waitTime)) == 0)     {         if(behaviour == 0)         {         movingRight = false;                  }         if(behaviour == 1)         {            movingRight = true;                  }         if(behaviour == 2)         {         rb.velocity = new Vector2(rb.velocity.x, jumpSpeed);         }     }         } 

Randomly selected words converted into sentence. Did I lose passphrase strength or gain it?

I got 5 dice and opened EFF’s wordlist, and generated a random five-word passphrase (all letters small with spaces, no punctuation) for my PC.

The words were making up a meaningful scene in my mind, so I made a complete sentence out of the words by adding some more words (like of, from, a, etc.) and punctuation.

I am not able to decide which of the following thoughts is more dominant:

Benefit: I got some punctuation, a single capital letter and more words. So the "strength" of passphrase should increase.

Drawback: The virgin passphrase was quite random (nonsense), but the new sentence has got appreciable "real-world" meaning (sense) to it. It looks like a spam message generated by the method mentioned in this answer.

Website not showing mobile version properly – randomly shows desktop version!

Our website here does not show properly on mobile phones much of the time. I have spent many hours trying to fix the issue to no avail.

We’re using a plugin called WPtouch to show a responsive mobile version of the blog. It used to work fine for years. However, in recent months, quite often when I visit the blog on a mobile device it shows the desktop version. This is very detrimental as the text on the site is miniscule and impossible to read.

We’re also using Cloudflare CDN and Swift Performance Lite to try to speed up the site. We’ve tried to clear / purge this CDN and cache regularly, as well as that of the browsers we use on the mobiles we test on. Quite often after we do it starts to show the mobile version of the site, but then reverts to showing the desktop version even on mobiles.

The thing that’s making me tear my hair out is it switches between the mobile and desktop versions on the same mobile phone in the same browser while surfing the site seemingly randomly (which leads me to believe it’s probably not a CDN or cache issue).

Is there anything I may do to finally fix this confusing issue please?

Thanks in advance!

(Roll20) How to make a simple deck of magical cards that will be drawn randomly?

Sorry if the question was asked before, but i didnt find any good awnsers for me.

Im a new DM playing on Roll20 and im making a new Class that fights with magical cards,dice and coins. I need a deck of cards that you can drawn from, where all cards have different effects. But im not sure how to make it very efficient, because some cards in the deck are duplicates. Also, if you draw a card, its gone from the deck. But you should also be able to “reshuffle” the deck to put all cards back into the deck. I thought about making a rollable table on roll 20, but from what i know, you can’t make a setting to get an event only once before having to “reset” the table. Is there a better method than just writing all cards already drawn somewhere, and let the player roll the table until he gets a new card.

Thanks for your advice.

Optimization of a query to retrieve records randomly with multiple joins and filters

I have the following schema:

DB Schema

This question was posted also in StackOverflow, but I want to consult also to specialists more focused on DB administration because the nature of my project. Sorry if this is a mistake

Right now, the table Property hold more than 70K records. I’m developing an update to support more than 500 concurrent sessions. The application will support a map a to make the searches, that’s why GeoLocation declares Coordinate as geography data type. Now we have a big problem, because the response time for some queries (the most important ones) is very slow. I mean, the application has to return around 1000 records at once if there are that quantity of results for the specified parameters.

The parameters are distributed on all the tables of the schema (actually, it’s a portion of the schema). Being Features a table which holds all the principal “characteristics” of the properties (# of bedrooms, # of garages, etc).

With that on mind, the query that is taking so much time right now is the following:

DECLARE @cols NVARCHAR(MAX), @query NVARCHAR(MAX);  DECLARE @properties TABLE(     [ID] INT )  INSERT INTO @properties     SELECT p.[Id]     FROM[Property] p     INNER JOIN[GeoLocation] AS[g]          ON[p].[Id] = [g].[PropertyId]     INNER JOIN[PropertyFeature] AS[pf]          ON[pf].[PropertyId] = [p].[Id]     INNER JOIN[Feature] AS[f]          ON[pf].[FeatureId] = [f].[Id]     WHERE[g].[Address] IS NOT NULL AND(([g].[Address] <> N'') OR[g].[Address] IS NULL)         AND[pf].[FeatureId] IN(             Select ID from feature where featuretype = 1)     GROUP BY p.Id, p.ModificationDate     ORDER BY [p].ModificationDate DESC, newid()     OFFSET 0 ROWS     FETCH NEXT 1000 ROWS ONLY  DECLARE @features TABLE(     [Name] NVARCHAR(80) )  INSERT INTO @features     select Name from feature where FeatureType = 1  CREATE TABLE #temptable (     Id INT,     Url NVARCHAR(200),     Title NVARCHAR(300),     Address NVARCHAR(200),     Domain Tinyint,     Price Real,     Image NVARCHAR(150),      Name NVARCHAR(80),     Value NVARCHAR(150) )  INSERT INTO #temptable SELECT     [t].[Id],      [t].[Url],      [t].[GeneratedTitle] AS[Title],      [t].[Address],      [t].[Domain],      [t].[Price],     (SELECT TOP(1) ISNULL([m].[Resize1200x1200], [m].Resize730x532)      FROM [Multimedia] AS[m]      WHERE [t].[Id] = [m].[PropertyId]         and m.MultimediaType = 1      ORDER BY [m].[Order]) AS[Image],      [t].[Name],      [t].[Value] FROM     (SELECT         [p].[Id],         [p].[Url],         [p].[GeneratedTitle],         [g].[Address],         [p].[Domain],         [pr].[Amount] AS Price,         [p].[ModificationDate],         [f].[Name],         [pf].[Value]     FROM [Property] AS [p]     INNER JOIN [GeoLocation] AS[g]          ON [p].[Id] = [g].[PropertyId]     INNER JOIN [PropertyFeature] AS[pf]          ON [pf].[PropertyId] = [p].[Id]     INNER JOIN [Feature] AS[f]          ON [pf].[FeatureId] = [f].[Id]     INNER JOIN [Operation] AS [o]          ON [p].[Id] = [o].[PropertyId]      INNER JOIN [OperationType] AS [o0]          ON [o].[OperationTypeId] = [o0].[Id]      INNER JOIN [Price] AS [pr]          ON [pr].[OperationId] = [o].[Id]      WHERE p.Id in          (Select Id from @properties)     GROUP BY [p].[Id],               [p].[Url],              [p].[GeneratedTitle],               [g].[Address],              [p].[Domain],               [pr].[Amount],              [p].[ModificationDate],              [f].[Name],              [pf].[Value]) AS[t]     ORDER BY[t].[ModificationDate] DESC  SET @cols = STUFF(                 (                     SELECT DISTINCT                             ','+QUOTENAME(c.[Name])                     FROM @features c FOR XML PATH(''), TYPE                  ).value('.', 'nvarchar(max)'), 1, 1, ''); SET @query = 'SELECT [Id],                       [Url],                       [Title],                       [Address],                       [Domain],                       [Price],                       [Image],                       ' + @cols + '                FROM (SELECT [Id],                              [Url],                              [Title],                              [Address],                              [Domain],                              [Price],                              [Image],                              [Value] AS [value],                              [Name] AS[name]                       FROM #temptable)x                       PIVOT(max(value) for name in ('+@cols+')) p'; EXECUTE(@query);  DROP TABLE #temptable 

The execution plan and Live query statistics show me the following:

Query Execution Plan

The previous query tries to obtain randomly a X number of records IDs, holding all the filter criteria to obtain only the IDs of the records which meet that criteria. The time right now is up to 15 seconds. It’s a lot if we talk about more than 400 users using concurrently the application.

Please, help me with this. I’m three weeks trying to solve this problem with no success, but a lot of advances has been made (before it was consuming 2 minutes in avg).

If it helps, I can give you access to a “dummy” deployed version of the DB with the same quantity of records to test and see directly the problem.

Thanks in advance…

===================================================================================================== INDEXES:

the indexes that are currently on the tables are the following:

GO CREATE UNIQUE NONCLUSTERED INDEX IX_Property_ModificationDate  ON [dbo].[Property] (ModificationDate DESC)  WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON)  GO CREATE NONCLUSTERED INDEX [IX_Property_ParentId_StatusCode]  ON [dbo].[Property] ([ParentId] ASC, [StatusCode] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Property_ParentId_StatusCode_Id_ModificationDate]  ON [dbo].[Property] ([ParentId] ASC, [StatusCode] ASC, [Id] ASC, [ModificationDate] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Property_ParentId]     ON [dbo].[Property]([ParentId] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);      GO CREATE NONCLUSTERED INDEX [IX_Property_Identity_Domain_StatusCode]     ON [dbo].[Property]([Identity] ASC, [Domain] ASC, [StatusCode] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Property_Id_ModificationDate]  ON [dbo].[Property] (Id ASC, ModificationDate ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Property_PublisherId]     ON [dbo].[Property]([PublisherId] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);   GO CREATE NONCLUSTERED INDEX [IX_Property_RealEstateTypeId]     ON [dbo].[Property]([RealEstateTypeId] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON)   GO  CREATE INDEX FIX_Property_StatusCode_Online ON [dbo].[Property](StatusCode) WHERE StatusCode = 1 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE INDEX FIX_Property_StatusCode_Offline ON [dbo].[Property](StatusCode) WHERE StatusCode = 0 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE INDEX FIX_Property_Domain_Urbania ON [dbo].[Property](Domain) WHERE Domain = 1 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE INDEX FIX_Property_Domain_Adondevivir ON [dbo].[Property](Domain) WHERE Domain = 2 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  GO CREATE NONCLUSTERED INDEX [IX_GeoLocation_PropertyId_ModificationDate]  ON [dbo].[GeoLocation] (PropertyId ASC, [ModificationDate] DESC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_GeoLocation_PropertyId_Address]  ON [dbo].[GeoLocation] (PropertyId ASC, [Address] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE UNIQUE NONCLUSTERED INDEX IX_GeoLocation_ModificationDate  ON [dbo].[GeoLocation] (ModificationDate DESC)  WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE NONCLUSTERED INDEX [IX_GeoLocation_Ubigeo] ON [dbo].[GeoLocation]([Ubigeo] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON)  GO CREATE UNIQUE NONCLUSTERED INDEX [IX_GeoLocation_PropertyId]     ON [dbo].[GeoLocation]([PropertyId] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE SPATIAL INDEX SIX_GeoLocation_Coordinate ON [dbo].[GeoLocation](Coordinate) GO  CREATE INDEX FIX_GeoLocation_Domain_Urbania ON [dbo].[GeoLocation](Domain) WHERE Domain = 1 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  CREATE INDEX FIX_GeoLocation_Domain_Adondevivir ON [dbo].[GeoLocation](Domain) WHERE Domain = 2 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  GO CREATE NONCLUSTERED INDEX [IX_Multimedia_PropertyId_Order]  ON [dbo].[Multimedia] (PropertyId ASC, [Order] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Multimedia_PropertyId]     ON [dbo].[Multimedia]([PropertyId] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_Multimedia_Order]     ON [dbo].[Multimedia]([Order] ASC)     WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON); GO  CREATE NONCLUSTERED INDEX [PK_Multimedia_Property]     ON [dbo].[Multimedia]([Id] ASC, [PropertyId] ASC); GO  CREATE INDEX FIX_Multimedia_MultimediaType_Image ON [dbo].[Multimedia](MultimediaType) WHERE MultimediaType = 1 WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON) GO  GO CREATE NONCLUSTERED INDEX [IX_PropertyFeature_PropertyId_FeatureId]  ON [dbo].[PropertyFeature] (PropertyId ASC, [FeatureId] ASC) WITH( SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, FILLFACTOR = 90, ONLINE = ON);  GO CREATE NONCLUSTERED INDEX [IX_PropertyFeature_FeatureId]     ON [dbo].[PropertyFeature]([FeatureId] ASC);   GO CREATE NONCLUSTERED INDEX [IX_PropertyFeature_PropertyId]     ON [dbo].[PropertyFeature]([PropertyId] ASC);   GO CREATE NONCLUSTERED INDEX [IX_PropertyFeature-FeatureId]     ON [dbo].[PropertyFeature]([Id] ASC, [FeatureId] ASC);   GO CREATE NONCLUSTERED INDEX [IX_PropertyFeature_Property]     ON [dbo].[PropertyFeature]([Id] ASC, [PropertyId] ASC);  GO CREATE NONCLUSTERED INDEX [IX_Operation_PropertyId]     ON [dbo].[Operation]([PropertyId] ASC);  GO CREATE NONCLUSTERED INDEX [IX_Operation_OperationTypeId]     ON [dbo].[Operation]([OperationTypeId] ASC);  GO CREATE NONCLUSTERED INDEX [IX_Price_OperationId]     ON [dbo].[Price]([OperationId] ASC);  GO CREATE NONCLUSTERED INDEX [IX_Price_Operation]     ON [dbo].[Price]([Id] ASC, [OperationId] ASC); 

Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $ n$ are of depth $ O(log(n))$ and it is clear that level $ k$ has at most $ 2^{k}$ nodes (root’s level is 0).

I have an algorithm that traverses every path in the tree (beginning at the root) but stops after traversing $ k$ nodes (the parameter $ k$ is a configurable parameter which is independent of the size of the tree $ n$ ).

For any tree $ T$ with $ depth(T) > k$ , the algorithm will miss some nodes of the tree. I would like to bound the probability of my algorithm missing a large number of nodes.

Formalizing it: let $ T$ be a randomly built binary search tree of $ n$ nodes. I would like to calculate the probability for a node to have depth larger than $ k$ , as a function of $ n$ and $ k$ .

Bluetooth Randomly Stopped

I’m using a Developer, Ubuntu shipped with it pre-installed Dell Precision 7530. Today while working, my bluetooth speakers beeped indicating they disconnected, I went to reconnect and in the bluetooth settings it’s saying “No Bluetooth Found. Plug in a dongle to use Bluetooth.” – except I’ve been using bluetooth for the entire 6 months I’ve owned the laptop so there absolutely is a dongle. I’ve restarted the computer several times, including fully off/on, and nothing. I’m at a loss. Any suggestions here?

I’ve seen other chats about bluetooth not working but they tend to be people that upgraded recently etc. – I haven’t. It just STOPPED after working fine and flawlessly.

I’m on Ubuntu 18.04 LTS.

Num Lock randomly turns on, possibly only on Visual Studio Code

My situation is similar to the one posted here: Num Lock Key Randomly Turning On and Off, except, so far, I have only observed this random toggling when I am writing on Visual Studio Code. In other parts and on normal usage, I have not observed this happening.

So, in any regular writing session, I would suddenly find myself typing in numbers, when I wanted to just move around the text. Does anyone have any idea why this is happening, please?

Here’s some information that might help:

  • Lenovo Ideapad 330-15IKB
  • Ubuntu 19.04.3

About page on VS Code:

Version: 1.38.1 Commit: b37e54c98e1a74ba89e03073e5a3761284e3ffb0 Date: 2019-09-11T13:30:08.229Z Electron: 4.2.10 Chrome: 69.0.3497.128 Node.js: 10.11.0 V8: 6.9.427.31-electron.0 OS: Linux x64 5.0.0-31-generic snap 

If this isn’t the best forum for this question, please let me know and I’ll head there. I wish this problem to be solved the soonest possible because this gets really annoying.